Metadata-Version: 2.4
Name: pyregg
Version: 0.2.2
Summary: Rare-event simulation for random geometric graphs via importance sampling
Author: Christian Hirsch, Volker Schmidt, Dirk Kroese
Author-email: Sarat Moka <s.moka@unsw.edu.au>
License-Expression: MIT
Project-URL: Homepage, https://github.com/saratmoka/RareEvents-RandGeoGraphs
Project-URL: Paper, https://arxiv.org/abs/2504.10530
Project-URL: Bug Tracker, https://github.com/saratmoka/RareEvents-RandGeoGraphs/issues
Keywords: rare events,random geometric graphs,Gilbert graph,importance sampling,Monte Carlo
Classifier: Programming Language :: Python :: 3
Classifier: Operating System :: OS Independent
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Intended Audience :: Science/Research
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24
Requires-Dist: scipy>=1.10
Requires-Dist: numba>=0.57
Requires-Dist: networkx>=3.0
Dynamic: license-file

# 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

```bash
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)`.

```python
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)")
```

```python
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 cells per interaction-range interval; total cells = `(wind_len / int_range × grid_res)²` (IS only, default 10) |
| `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 (included in the source distribution):

| 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
