Overview
Traditional importance sampling (IS) is typically designed to estimate the probabilities of rare events with minimal estimator variance. However, certain applications prioritize the rapid discovery of a trajectory within a rare set $A_n$. This focus necessitates a shift in design principle from ensemble-based estimation to one centered on minimizing the hitting time, defined as $\tau_{A_n} := \inf\{t \ge 1 : Y_t^n \in A_n\}$.
Research Context
The study addresses the common objective in various applications to generate a specific trajectory that belongs to a rare set, rather than merely estimating the probability of encountering such an event. This objective, termed a Quality of Discovery problem, requires an alternative framework to traditional variance minimization in importance sampling.
Approach
The authors formalize the Quality of Discovery problem as the minimization of the description length (or surprisal) of the discovered trajectory under the nominal model $p$. They investigate the equivalence between minimizing this description length and minimizing the nominal rank exponent. The nominal rank exponent is defined as $J_{\mathrm{rank}}(q_n) := \lim_{n\to\infty} \frac{1}{n} \log G_n(Y^n)$, where $G_n(x^n)$ represents the guesswork of sequence $x^n$. The analysis specifically considers independent and identically distributed (i.i.d.) models and rare sets defined by type ($\Gamma$).
Findings
- Minimizing the description length of a discovered trajectory is mathematically equivalent to minimizing the nominal rank exponent, $J_{\mathrm{rank}}(q_n)$.
- For i.i.d. models and type-defined rare sets, while classical importance sampling targets a mass-dominating type $Q_{\mathrm{IS}}^* \in \arg\min_{Q \in \Gamma} D(Q\|p)$, discovery optimality is achieved by minimizing a different objective function.
- The optimal type for discovery, $Q_{\mathrm{GW}}^*$, is found by $Q_{\mathrm{GW}}^* \in \arg\min_{Q \in \Gamma} [H(Q) + D(Q\|p)]$. Here, $H(Q)$ represents the entropy of type $Q$, and $D(Q\|p)$ is the Kullback-Leibler divergence between type $Q$ and the nominal model $p$.
- This framework establishes that minimizing the guesswork exponent ensures the discovered sequence is the 'least surprising' representative of the set when ordered according to the nominal model's search process.
- Under budgetary constraints, this exponent serves as a lexicographic tie-breaker when multiple hitting-time minimizers exist.
- The quantity $H(Q) + D(Q\|p)$ is identified as a natural objective for discovery-based importance sampling, providing a formal connection between randomized sampling and systematic search methodologies.
Why This Matters
This research offers a theoretical foundation for designing importance sampling schemes that prioritize the discovery of rare events rather than their probability estimation. By introducing surprisal and guesswork as key metrics, it reorients the optimization objective in specific applications where generating a representative instance of a rare event is the primary goal, formalizing a bridge between randomized and systematic search techniques.