# Dynamic Splitting simulation

## 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.$$