pyregg 0.2.0

Rare-event simulation for random geometric graphs via importance sampling

pyregg

Rare-event simulation for random geometric graphs.

pyregg estimates the probability of rare events in Gilbert random geometric graphs using three estimators: Naïve Monte Carlo (NMC), Conditional Monte Carlo (CMC), and Importance Sampling (IS).

Installation

pip install pyregg

Rare Events

Module	Rare Event
pyregg.ec	Edge count ≤ ℓ
pyregg.md	Maximum degree ≤ ℓ
pyregg.mcc	Maximum connected component size ≤ ℓ
pyregg.ntg	Number of triangles ≤ ℓ
pyregg.mcs	Maximum clique size ≤ ℓ
pyregg.planar	Graph is planar

Quick Start

Each module exposes three functions: naive_mc, conditional_mc, and importance_sampling. All return (probability, rel_variance, n_samples).

import pyregg.ec as ec

# Estimate P(EC(G(X)) ≤ 15) on [0,10]² with κ=0.3, r=1
Z, RV, n = ec.importance_sampling(wind_len=10, kappa=0.3, int_range=1.0, level=15)
print(f"P ≈ {Z:.4e}  (relative variance {RV:.2f},  {n} samples)")

import pyregg.planar as planar

# Estimate P(G(X) is planar) on [0,10]² with κ=1.2, r=1
Z, RV, n = planar.importance_sampling(wind_len=10, kappa=1.2, int_range=1.0)
print(f"P ≈ {Z:.4e}  (relative variance {RV:.2f},  {n} samples)")

API

Common parameters

Parameter	Description
wind_len	Side length of the square window [0, wind_len]²
kappa	Intensity of the Poisson point process (points per unit area)
int_range	Connection radius — two points are connected if their distance ≤ int_range
level	Threshold ℓ (not used for planar)
grid_res	IS grid resolution: grid_res × grid_res cells (IS only, default 100)
max_iter	Maximum number of samples (default 10⁸)
warm_up	Minimum samples before checking convergence
tol	Stop when relative variance / n < tol (default 0.001)
seed	Integer random seed for reproducibility

Estimators

naive_mc(...) — Independent realisations; fraction satisfying the rare event.

conditional_mc(...) — Sequential point addition with analytic conditioning at each step.

importance_sampling(...) — Sequential point addition with cells that would violate the rare event blocked; likelihood-ratio correction ensures unbiasedness.

Performance

The relative variance (RV) measures estimation efficiency — smaller RV means fewer samples for the same precision. The table below compares CMC and IS at a precision target of RV/m < 0.01, with window [0,10]², r = 1, and a 100×100 IS grid. Probabilities are approximately 10⁻⁴.

Example	Z	RV (CMC)	Time CMC	RV (IS)	Time IS	Speedup
EC ℓ=15	1.15×10⁻⁴	17.6	1.4 s	9.11	0.02 s	~70×
MD ℓ=2	9.38×10⁻⁴	51.4	0.7 s	6.82	0.02 s	~35×
MCC ℓ=2	2.48×10⁻⁴	211	2.4 s	19.9	0.02 s	~120×
NTG ℓ=0	1.91×10⁻⁴	189	2.0 s	5.65	0.01 s	~200×
MCS ℓ=1	1.91×10⁻⁴	189	2.0 s	5.65	0.01 s	~200×
Planarity	1.42×10⁻⁴	192	498 s†	11.4	66.0 s	~8×

† Extrapolated from a pilot run. CMC is effectively infeasible at this probability level.

Examples

Ready-to-run scripts are in the examples/ directory:

Script	Description
examples/edge_count.py	EC: P(EC ≤ 15), κ=0.3
examples/max_degree.py	MD: P(MD ≤ 2), κ=0.65
examples/max_connected_component.py	MCC: P(MCC ≤ 2), κ=0.65
examples/num_triangles.py	NTG: P(NTG ≤ 0), κ=0.65
examples/max_clique_size.py	MCS: P(MCS ≤ 1), κ=0.65
examples/planarity.py	Planarity: P(planar), κ=1.2

Dependencies

Python  >= 3.10
NumPy   >= 1.24
SciPy   >= 1.10
Numba   >= 0.57
NetworkX >= 3.0

References

• S. Moka, C. Hirsch, V. Schmidt & D. P. Kroese (2025). Efficient Rare-Event Simulation for Random Geometric Graphs via Importance Sampling. arXiv:2504.10530. https://arxiv.org/abs/2504.10530

• C. Hirsch, S. B. Moka, T. Taimre & D. P. Kroese (2022). Rare Events in Random Geometric Graphs. Methodology and Computing in Applied Probability, 24, 1367–1383. https://link.springer.com/article/10.1007/s11009-021-09857-7