## 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 and importance function over state space . We will assume for the moment that

Suppose is *quasi-monotone* in its vector argument – that is, that

Further, take, wlog,

We assume that for any threshold that the entry times to the sets and are well-defined stopping times.

We wish to estimate the probability where is the event

Now consider a sequence of thresholds The process must reach to reach for , and so we have a nested series of events and thus

where

## Splitting for static problems

We have a density on and a quasi-monotone importance function We wish to simulate from a conditional

where

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