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
Splitting for static problems
We have a density on and a quasi-monotone importance function We wish to simulate from a conditional
- 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