Backend
Importance Sampling for Event Discovery via Guesswork
arXiv math.IT0 views
arXiv:2606.24537v2 Announce Type: replace 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$. This requires a shift from ensemble-based estimation to a design principle focused on the hitting time $\tau_{A_n} := \inf\{t \ge 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$. We prove that minimizing this description length is equivalent to minimizing the nominal rank exponent $J_{\mathrm{rank}}(q_n) := \lim_{n\to\infty} \frac{1}{n} \log G_n(Y^n)$, where $G_n(x^n)$ is the guesswork of sequence $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_{\mathrm{IS}}^* \in \arg\min_{Q \in \Gamma} D(Q\|p)$, discovery optimality is achieved by $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)$ as a natural objective for discovery-based importance sampling, providing a formal bridge between randomized sampling and systematic search.
Source:https://arxiv.org/abs/2606.24537PreviousMemory Constrained Adversarial Hypothesis TestingNextEngineering Yeast Cells to Facilitate Information Exchange
Related posts

Dreame X50 Ultra: designing a Shopify buying journey around fit, bundles and payment conditions
0dev.to JavaScript
Connect Four in 86 lines: how I coded the rules for a multiplayer browser game
0dev.to JavaScript
From Prompt to Production: Architectural Deep‑Dive into MIT’s “How to Make Almost Anything” Framework
0dev.to Rust
PRISM: Preference-based Reward and Uncertainty-Integrated Synthesis Minimization for RTL PPA Optimization
0arXiv cs.SE
The $\alpha$-Limit Problem: Convergence of a Linear Degenerate Interface Transmission Problem
0arXiv cs.NA
A Spectral Proximal DC Algorithm with Nonmonotone Line Search and Extrapolation
0arXiv cs.NA