SEMINAR: Seminar

This talk deals with the problem of determining the connectivity probability of a random graph model. For even moderately sized random graphs this probability can not be computed exactly, so we apply Monte Carlo methods. If connectivity is a rare event (for example p < 10^(-5)) then simple simulation methods may require a long simulation effort; in extreme cases it may be difficult to obtain a non-zero estimate.

We apply a rare-event simulation technique known as splitting to this estimation problem. The splitting method is a way to estimate the probability that a Markov chain hits a specified state. It achieves efficiency gains by splitting sample paths that are likely to hit the target event. Although this description sounds very specific, a surprising number of problems can be reformulated in this way. The application of the splitting method to this fundamentally combinatoric problem illustrates that it can be used to solve a wide variety of problems.