Efficient Importance Sampling of Brownian Motion Avoiding Poissonian Obstacles for Long Time
Abstract
We design and analyze an efficient importance sampling estimator of the probability that, over a long time horizon, a Brownian particle avoids obstacles of a fixed radius placed according to an independent Poisson random field. Donsker and Varadhan identify the exponential decay rate of this probability as the optimal balance between the volume cleared of obstacles and the spectral cost of confinement, and the confinement results of Sznitman and Povel show that the particle survives by localizing its path in a ball of (roughly) deterministic radius but with a random center. This strategy makes direct Monte Carlo exponentially ineffective over long horizons, and makes a practical yet asymptotically optimal sampler non-trivial to design, since the sampler must track the random region swept out by the path. For every fixed dimension d≥2 and every fixed obstacle radius, we construct a sequential importance sampler that is unbiased and asymptotically optimal. The full algorithm has finite expected total work at every fixed horizon, and both its expected work and the coefficient of variation grow at most subexponentially with the time horizon. The method avoids repeatedly solving eigenvalue problems on the evolving explored regions and suits parallel implementation. Numerical experiments illustrate the efficiency of the method.
Related
- On the maximum visibility in a ball through the vacant set of Poissonian obstacles
- PERSISTENCE OF THE WIENER SAUSAGE: SAMPLING STABILITY AND LIMIT THEOREMS FOR BETTI-CURVE FUNCTIONALS OF DRIFTED PLANAR BROWNIAN MOTION
- Multiple Importance Sampling for Guided Speculative Inference
- Post-stratified importance sampling
- Repulsive normalizing flow mixtures for adaptive importance sampling: reliability analysis of complex systems
BibTeX
@misc{blanchet2026efficient,
title = {{Efficient Importance Sampling of Brownian Motion Avoiding Poissonian Obstacles for Long Time}},
author = {Jose Blanchet and Paul Dupuis and Hao Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41234},
eprint = {2610.41234},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41234},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient Importance Sampling of Brownian Motion Avoiding Poissonian Obstacles for Long Time
AU - Jose Blanchet
AU - Paul Dupuis
AU - Hao Liu
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41234
UR - https://arxiv.org/abs/2610.41234
AB - We design and analyze an efficient importance sampling estimator of the probability that, over a long time horizon, a Brownian particle avoids obstacles of a fixed radius placed according to an independent Poisson random field. Donsker and Varadhan identify the exponential decay rate of this probability as the optimal balance between the volume cleared of obstacles and the spectral cost of confinement, and the confinement results of Sznitman and Povel show that the particle survives by localizing its path in a ball of (roughly) deterministic radius but with a random center. This strategy makes direct Monte Carlo exponentially ineffective over long horizons, and makes a practical yet asymptotically optimal sampler non-trivial to design, since the sampler must track the random region swept out by the path. For every fixed dimension d≥2 and every fixed obstacle radius, we construct a sequential importance sampler that is unbiased and asymptotically optimal. The full algorithm has finite expected total work at every fixed horizon, and both its expected work and the coefficient of variation grow at most subexponentially with the time horizon. The method avoids repeatedly solving eigenvalue problems on the evolving explored regions and suits parallel implementation. Numerical experiments illustrate the efficiency of the method.
ER -