An efficient multilevel splitting scheme


Miretskiy, D.I. and Scheinhardt, W.R.W. and Mandjes, M.R.H. (2009) An efficient multilevel splitting scheme. In: 6th St. Petersburg Workshop on Simulation, 28 June - 4 July 2009, St. Petersburg, Russia (pp. pp. 909-914).

open access
Abstract: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.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Organisation URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page