Importance Sampling for Event Discovery via Guesswork

Asaf Cohen · 2026

Read Importance Sampling for Event Discovery via Guesswork by Asaf Cohen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24537.txt.

Introduction

Cohen rethinks importance sampling for searchers who want to find a rare event quickly, not measure its probability precisely. Classical importance sampling cuts estimator variance for rare event odds, an ensemble goal. Many uses instead prize discovery: generating even one path inside the rare set, fast. The relevant clock is the hitting time, the first moment a simulated path enters the rare region.

A Quality of Discovery problem defines the goal as cutting the description length, the surprisal, of the discovered trajectory. Cohen proves this equals cutting a rank exponent built from guesswork, the expected search position of the true sequence. For independent models and type defined rare sets, classical sampling targets the type minimising divergence alone. Discovery optimality adds an entropy term to that divergence. The 2026 framework exposes a fundamental rule separating finding from measuring. The best hunting distribution is not the best estimating distribution.

Catalog record

CREATORAsaf Cohen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24537

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Importance Sampling for Event Discovery via Guesswork Asaf Cohen Abstract Traditional importance sampling (IS) is designed to estimate rare-event probabilities by minimizing estimator variance. However, many applications prioritize rapid discovery: the generation of a trajectory within a rare set A n A_{n} . This requires a shift from ensemble-based estimation to a design principle focused on the hitting time τ A n := inf { t ≥ 1 : Y t n ∈ A n } \tau_{A_{n}}:=\inf\{t\geq 1:Y_{t}^{n}\in A_{n}\} . We formalize a Quality of Discovery problem as the problem of minimizing the description length (surprisal) of the discovered trajectory under the nominal model p p . We prove that minimizing this description length is equivalent to minimizing the nominal rank exponent J rank ​ ( q n ) := lim n → ∞ 1 n ​ log ⁡ G n ​ ( Y n ) J_{\mathrm{rank}}(q_{n}):=\lim_{n\to\infty}\frac{1}{n}\log G_{n}(Y^{n}) , where G n ​ ( x n ) G_{n}(x^{n}) is the guesswork of sequence x n x^{n} . For i.i.d. models and type-defined rare sets Γ \Gamma , we show that while classical IS targets the mass-dominating type Q IS ∗ ∈ arg min Q ∈ Γ D ( Q ∥ p ) Q_{\mathrm{IS}}^{*}\in\arg\min_{Q\in\Gamma}D(Q\|p) , discovery optimality is achieved by Q GW ∗ ∈ arg min Q ∈ Γ [ H ( Q ) + D ( Q ∥ p ) ] Q_{\mathrm{GW}}^{*}\in\arg\min_{Q\in\Gamma}[H(Q)+D(Q\|p)] . This framework identifies a fundamental rule: minimizing the guesswork exponent ensures the discovered sequence is the "least surprising" representative of the set relative to the nominal model’s search order. We further demonstrate that under budgetary constraints, this exponent serves as a lexicographic tie-breaker when the hitting-time minimizer is not unique. This establishes H ( Q ) + D ( Q ∥ p ) H(Q)+D(Q\|p) as a natural objective for discovery-based importance sampling, providing a formal bridge between randomized sampling and systematic search. I Introduction Importance sampling (IS) is a powerful variance-reduction technique traditionally used to estimate the probability of rare events. By introducing an alternative sampling distribution q_{n} , IS allows for the efficient representation of the probability mass of a rare set A_{n} , which would otherwise require an exponential number of samples to observe under a nominal distribution p_{n} . In many modern applications, however, the primary objective shifts from probability estimation to rapid discovery : the generation of a specific trajectory within a rare set as quickly as possible. This shift to a discovery-based goal requires a design principle focused on the hitting time \tau_{A_{n}}:=\inf\{t\geq 1:Y_{t}^{n}\in A_{n}\} , where J_{\text{hit}}(q_{n}):=\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{E}_{q_{n}}[\tau_{A_{n}}] is the hitting-time exponent. Rapid discovery necessitates a different proposal distribution Q^{*} , centered on discovery speed rather than variance minimization. We formalize this as the Quality of Discovery , which seeks to hit the target set in subexponential time (ensuring J_{\text{hit}}(q_{n})=0 ) while optimizing the qualitative nature of the discovered trajectory. Searching for a distribution that efficiently hits a target connects importance sampling to the field of guesswork . Guesswork centers on the search effort required to identify a realization of a random vector through sequential queries. The guesswork exponent, governed by the nominal rank G_{n}(x^{n}) , measures the number of queries required to identify x^{n} when searching in decreasing order of probability. Notably, this guesswork exponent is achievable not only through such a deterministic search but also through randomized guessing strategies, where samples are drawn independently according to a specified proposal distribution [ 22 ] . To refine our choice among potential discovery proposals, we introduce a minimal description length criterion. This approach seeks the trajectory that is most consistent with the nominal model: the "least surprising" representative of the rare set. We prove that minimizing the expected description length (surprisal) under the nominal model is equivalent to minimizing the guesswork exponent. This provides a concrete and new optimization problem: \displaystyle\underset{q_{n}}{\text{minimize}} \displaystyle\mathbb{E}_{q_{n}}\left[-\frac{1}{n}\log p_{n}(Y^{n})\mid Y^{n}\in A_{n}\right] (1) \displaystyle\text{subject to} \displaystyle J_{\text{hit}}(q_{n})=0. For i.i.d. models and type-defined sets \Gamma , we show that the solution is the guesswork-guided proposal Q_{\text{GW}}^{*}=\arg\min_{Q\in\Gamma}[H(Q)+D(Q\|p)] . The contributions of this paper are summarized as follows. We formalize the Quality of Discovery as a performance metric for importance sampling focused on individual trajectory properties. We prove the equivalence between minimizing the description length of a discovered trajectory and minimizing its nominal rank exponent . We derive the guesswork-guided proposal Q_{\text{GW}}^{*} as the optimal solution for discovery in i.i.d. models. Finally, we demonstrate that the guesswork exponent serves as a lexicographic tie-breaker in constrained discovery settings where multiple proposals yield identical hitting times. I-A Importance Sampling The references most relevant to this work are at the intersection of classical rare-event importance sampling, modern path-space sampling, and recent "make rare typical" constructions. While these distinct lines of research focus predominantly on optimizing estimation accuracy (minimizing variance), our approach shifts the focus toward optimizing discovery speed and the qualitative representativeness of trajectories through a guesswork criterion. Early foundations in importance sampling were primarily concerned with sequential analysis and stopping times. [ 26 ] provided a classical treatment in this area; however, this work tunes the change of measure for accurate probability estimation rather than rapid discovery. [ 4 ] is a standard reference for exponential tilting and large-deviations-based proposal design. While we utilize similar change-of-measure language, we replace this variance-efficiency metric with expected hitting time. Similarly, [ 21 ] formalized asymptotically efficient Monte Carlo estimation. While this work also studied exponential rates, our work centers on a search exponent driven by guesswork rather than a second-moment efficiency exponent. [ 3 ] further explored conditional estimators from an information-theoretic viewpoint. We maintains this proposal-design emphasis but, again, evaluates proposals based on the mass they place on the target set rather than estimator variance. The connection between importance sampling, large deviations, and control was established in [ 14 ] , viewing optimal proposals as a game between change of measure and large deviation. Similarly, [ 2 ] developed state-dependent schemes for heavy-tailed random walks. Although they target hitting events, their optimization objective remains estimator efficiency rather than direct hitting-time cost. In the realm of alternative algorithms, trajectory biasing and making the rare typical, [ 6 ] enhanced adaptive multilevel splitting, where one multiplies certain (favorable) trajectories and excludes others. Still, the focus is on estimation of (very) rare events. More recent literature has moved toward forcing rare transitions to occur more frequently. [ 15 ] modified dynamics through optimal nonequilibrium forcing to sample rare transitions efficiently. While conceptually close to our goal of making rare events visible, we derive the preferred bias from nominal-probability ranking and guesswork. The recent review [ 27 ] considered the broader landscape of variational path-sampling, also searching for a biased distribution, which minimizes the statistical distance to the true rare-event distribution, yet making the improbable events appear typical in simulation. This philosophy is shared in [ 5 ] , where an explicit construction modifies dynamics under which rare trajectories become typical. Our work expresses this same intuition within an information-theoretic, guesswork-based framework for discrete sequence models. In a similar vein [ 13 ] used variational methods to approximate Doob-transformed dynamics for rare path sampling. While their target is conditioned path sampling, ours is hitting-time optimization for discovery. Modern computational approaches

Read the complete text