# 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

..math:

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.

\begin{equation*} \tau_\gamma =\min\{t:S(\vv X(t))\geq \gamma \} \end{equation*}
\begin{equation*} \tau_0 =\min\{t:S(\vv X(t))\leq 0 ,\, t \gt 0\} \end{equation*}

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{equation*} \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} \end{equation*}

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{equation*} \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} \end{equation*}

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

## Refs

AuBe01
Au, S.-K., & Beck, J. L.(2001) Estimation of small failure probabilities in high dimensions by subset simulation. Probabilistic Engineering Mechanics, 16(4), 263–277. DOI.
BoKr08
Botev, Z. I., & Kroese, D. P.(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
Botev, Z. I., & Kroese, D. P.(2012) Efficient Monte Carlo simulation via the generalized splitting method. Statistics and Computing, 22(1), 1–16. DOI.
KaHa51
Kahn, H., & Harris, T. E.(1951) Estimation of particle transmission by random sampling. National Bureau of Standards Applied Mathematics Series, 12, 27–30.
LaBo15
Lam, K., & Botev, Z. (2015, November 1) The Dynamic Splitting Method with an application to portfolio credit risk.