An efficient multilevel splitting scheme

D.I. Miretskiy, Willem R.W. Scheinhardt, M.R.H. Mandjes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Downloads (Pure)


Rare event analysis has been attracting continuous and growing attention over the past decades. It has many possible applications in different areas, e.g., queueing theory, insurance, engineering etc. As explicit expressions are hard to obtain, and asymptotic approximations often lack error bounds, one often applies simulation methods to obtain performance measures of interest. Obviously, the use of standard Monte Carlo simulation for estimating rare event probabilities has an inherent problem: it is extremely time consuming to obtain reliable estimates since the number of samples needed to obtain an estimate of a certain predefined accuracy is inversely proportional to the probability of interest. Two important techniques to speed up simulations are Importance Sampling (IS) and Multilevel Splitting (MS). IS prescribes to simulate the system under a new probability measure such that the event of interest occurs more frequently, and corrects the simulation output by means of likelihood ratios to retain unbiasedness. The likelihood ratios essentially capture the likelihood of the realization under the old measure with respect to the new measure. The choice of a ‘good’ new measure is rather delicate; in fact only measures that are asymptotically efficient are worthwile to consider. We refer to [3] for more background on IS and its pitfalls. The other technique, multilevel splitting (MS), is conceptually easier, in the sense that one can simulate under the normal probability measure. When a sample path of the process is simulated, this is viewed as the path of a ‘particle’. When the particle approaches the target set to a certain distance, the particle splits into a number of new particles, each of which is then simulated independently of each other. This process may repeat itself several times, hence the term multilevel splitting. Typically, the states where particles should be split are determined by selecting a number of level sets of an importance function f. Every time a particle (sample path) crosses the next level set of the importance function f, it is split. The splitting factor (i.e. the number of particles that replaces the original particle) may depend on the current level. The challenge is to choose an importance function that will ensure that the probability of reaching the target set is roughly the same for all states that belong to the same level. Moreover, choosing the splitting factors appropriately is also important, see [1, 2]. Sample paths will hardly ever end up in the rare set if this factor is too small, while the number of particles (and consequently the simulation effort) will grow fast if this factor is too large. For an overview of the MS method see [5]. There are not many examples of asymptotically efficient MS schemes for estimating general types of rare events in the present literature. Most articles deal either with effective heuristics for particular (queueing) models, usually providing good estimates without rigorous analysis, see e.g. [6]; or with restrictive models, see e.g. [2]. The recent work in [1] does enable one to construct an asymptotically efficient MS scheme for estimating the probability of first entrance to a rare set, when the decay rate of the probability is known for all starting states. The authors used control-theoretic techniques to derive and prove their results. In this work we also provide a simple and asymptotically efficient MS scheme for estimating the probability of first entrance to some rare set. The scheme can be seen as part of the class of asymptotically efficient MS schemes developed in [1]. However, since we are only interested in easy-to-implement (but still efficient) schemes, we use a fixed, pre-specified splitting factor R, to be used for all levels. This is in contrast to the setting in [1] where the splitting factor may vary between levels and is usually noninteger (which is then implemented by using a randomization procedure). We accompany the scheme with a proof of its asymptotic efficiency which is relatively easy, in the sense that it only uses probabilistic arguments and some simple bounds, thereby giving insight into why the scheme works so well. The rest of the paper’s structure is as follows. In Section 2 we first describe the model of interest and, after a brief review of the MS method, we provide the MS scheme itself. A sketch of the proof of asymptotic efficiency of the scheme is given in Section 3. Supporting numerical results for a two-node tandem model are presented in Section 4 and compared with results from IS on the same model; in fact it turns out that MS can be a good alternative to IS for certain parameter settings.
Original languageUndefined
Title of host publicationProceedings of the 6th St. Petersburg Workshop on Simulation
EditorsS.M. Ermakov, V.B. Melas, A.N. Pepelyshev
Place of PublicationSt. Petersburg, Russia
PublisherSt. Petersburg State University
Number of pages6
ISBN (Print)not assigned
Publication statusPublished - 2009
Event6th St. Petersburg Workshop on Simulation - St. Petersburg, Russia
Duration: 28 Jun 20094 Jul 2009

Publication series

PublisherSt. Petersburg State University


Workshop6th St. Petersburg Workshop on Simulation
Other28 June - 4 July 2009


  • IR-69812
  • EWI-17327
  • METIS-264505

Cite this