## Splitting for Markov processes

A particular method for simulation-based estimation for rare events about which I am learning. The original Dynamic splitting algorithm (KaHa51) works for rare states in Markov chains.

Consider a Markov process \(\{\vv X(t)\}_{t\geq 0}\) and importance function \(S\) over state space \(\cc X\). We will assume for the moment that \(\cc X=\bb R^d.\)

Suppose \(S\) is *quasi-monotone* in its vector argument – that is, that

\[ x_i \leq x'_i i \in [1, \dots, d] \Rightarrow S(\vv x)\leq S(\vv x') \]

Further, take, wlog, \(S(\vv X(0))=0.\)

We assume that for any threshold \(\gamma\gt 0\) that the entry times to the sets \(\{S(\vv X(t))\geq \gamma\}\) and \(\{S(\vv X(t))\lt 0\}\) are well-defined stopping times.

\[ \tau_\gamma =\min\{t:S(\vv X(t))\geq \gamma \} \]

\[ \tau_0 =\min\{t:S(\vv X(t))\leq 0 ,\, t \gt 0\} \]

We wish to estimate the probability \(\bb P[\tau_\gamma\lt\tau_0]=\bb P[E_{\gamma}]\) where \(E_{\gamma}\) is the event \(E_{\gamma}=\{\tau_\gamma \lt \tau_0\}.\)

Now consider a sequence of thresholds \(\gamma_0\leq\gamma_1\leq\dots\gamma_L=\gamma.\) The process must reach \(\gamma_i\) to reach \(\gamma_j\) for \(i<j\), and so we have a nested series of events \(E_{\gamma_0}\supseteq E_{\gamma_0}\supseteq\dots E_{\gamma_L},\) and thus

\[ \begin{aligned} \ell&=\bb P(E_{\gamma_L}|E_{\gamma_{L-1}})\dots\bb P(E_{\gamma_2}|E_{\gamma_1})\bb P(E_{\gamma_1})\\ &=\prod_{i=1}^Lc_i \end{aligned} \]

where \(c_i=P(E_{\gamma_i}|E_{\gamma_{y-1}}).\)

## Splitting for static problems

We have a density \(f\) on \(\bb R^d\) and a quasi-monotone importance function \(S: \bb R^d\rightarrow\bb R.\) We wish to simulate from a conditional

\[ \begin{aligned} f^*(\vv x) &:=f(\vv x|S(\vv x)\geq\gamma)\\ &=\frac{1}{\ell(\gamma)}f(\vv x)\bb I\{S(\vv x)\geq\gamma)\} \end{aligned} \]

where \(\ell(\gamma)=\bb P[S(\vv X)\geq\gamma)],\quad \vv X \sim f.\)

## Refs

- BoKr08: (2008) An Efficient Algorithm for Rare-event Probability Estimation, Combinatorial Optimization, and Counting.
*Methodology and Computing in Applied Probability*, 10(4), 471–505. DOI - BoKr12: (2012) Efficient Monte Carlo simulation via the generalized splitting method.
*Statistics and Computing*, 22(1), 1–16. DOI - KaHa51: (1951) Estimation of particle transmission by random sampling.
*National Bureau of Standards Applied Mathematics Series*, 12, 27–30. - AuBe01: (2001) Estimation of small failure probabilities in high dimensions by subset simulation.
*Probabilistic Engineering Mechanics*, 16(4), 263–277. DOI