Efficient Importance Sampling for Wrong Exit Probabilities over Combinatorially Many Rare Regions
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912591459123200 |
|---|---|
| author | Song, Yanglei Fellouris, Georgios |
| author_facet | Song, Yanglei Fellouris, Georgios |
| contents | We consider importance sampling for estimating the probability that a light-tailed $d$-dimensional random walk exits through one of many disjoint rare-event regions before reaching an anticipated target. This problem arises in sequential multiple hypothesis testing, where the number of such regions may grow combinatorially and in some cases exponentially with the dimension. While mixtures over all associated exponential tilts are asymptotically efficient, they become computationally infeasible even for moderate values of $d$. We develop a method for constructing asymptotically efficient mixtures with substantially fewer components by combining optimal tilts for a small number of regions with additional proposals that control variance across a large collection of regions. The approach is applied to the estimation of three probabilities that arise in sequential multiple testing, including a multidimensional extension of Siegmund's classical exit problem, and is supported by both theoretical analysis and numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14596 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Importance Sampling for Wrong Exit Probabilities over Combinatorially Many Rare Regions Song, Yanglei Fellouris, Georgios Probability Computation 65C05, 60F10, 62L10 We consider importance sampling for estimating the probability that a light-tailed $d$-dimensional random walk exits through one of many disjoint rare-event regions before reaching an anticipated target. This problem arises in sequential multiple hypothesis testing, where the number of such regions may grow combinatorially and in some cases exponentially with the dimension. While mixtures over all associated exponential tilts are asymptotically efficient, they become computationally infeasible even for moderate values of $d$. We develop a method for constructing asymptotically efficient mixtures with substantially fewer components by combining optimal tilts for a small number of regions with additional proposals that control variance across a large collection of regions. The approach is applied to the estimation of three probabilities that arise in sequential multiple testing, including a multidimensional extension of Siegmund's classical exit problem, and is supported by both theoretical analysis and numerical experiments. |
| title | Efficient Importance Sampling for Wrong Exit Probabilities over Combinatorially Many Rare Regions |
| topic | Probability Computation 65C05, 60F10, 62L10 |
| url | https://arxiv.org/abs/2509.14596 |