pyregg — Rare-Event Simulation for Random Geometric Graphs

pyregg estimates the probability of rare events in Gilbert random geometric graphs using three Monte Carlo estimators:

  • Naïve Monte Carlo (NMC) — independent realisations of the graph

  • Conditional Monte Carlo (CMC) — sequential point addition with analytic conditioning

  • Importance Sampling (IS) — sequential point addition with cell blocking and likelihood-ratio correction

IS achieves substantially lower variance than CMC, which in turn outperforms NMC, enabling estimation of probabilities as small as 10⁻⁶ and beyond.

Installation

pip install pyregg

Modules

Module

Rare event

pyregg.ec

P(edge count ≤ ℓ)

pyregg.md

P(maximum degree ≤ ℓ)

pyregg.mcc

P(maximum connected component size ≤ ℓ)

pyregg.ntg

P(number of triangles ≤ ℓ)

pyregg.mcs

P(maximum clique size ≤ ℓ)

pyregg.planar

P(graph is planar)

pyregg.forest

P(graph is a forest / acyclic)

Quick Start

Each module is directly callable with an optional method argument ('ismc' by default). All calls return (probability, rel_variance, n_samples).

import pyregg.ec as ec

# P(EC(G(X)) ≤ 15) on [0,10]² with κ = 0.3, r = 1  [Importance Sampling, default]
Z, RV, n = ec(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

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

import pyregg.forest as forest

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

Choosing an estimator

Pass method='ismc' (default), 'cmc', or 'nmc' to select the estimator. Any additional keyword arguments are forwarded to the chosen function.

import pyregg.ec as ec

Z, RV, n = ec(wind_len=10, kappa=0.3, int_range=1.0, level=15)              # IS (default)
Z, RV, n = ec(wind_len=10, kappa=0.3, int_range=1.0, level=15, method='cmc')  # CMC
Z, RV, n = ec(wind_len=10, kappa=0.3, int_range=1.0, level=15, method='nmc')  # NMC

The three estimators are also available as named functions on each module:

Z, RV, n = ec.importance_sampling(wind_len=10, kappa=0.3, int_range=1.0, level=15)
Z, RV, n = ec.conditional_mc(wind_len=10, kappa=0.3, int_range=1.0, level=15)
Z, RV, n = ec.naive_mc(wind_len=10, kappa=0.3, int_range=1.0, level=15)

API Reference

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

  • 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. doi:10.1007/s11009-021-09857-7