Designing Importance Sampling Schemes for Simulating Rare Events in Reflected SDEs and Random Graphs

Understanding rare events in stochastic systems and random networks is important in various applications, such as those where understanding the reliability and failure mechanisms of the system are of interest. In reflected SDEs, the exit of the stochastic process from a given set represents an overflow of a queue buffer in a queuing network; in an Erdos-Renyi random graph, we consider rare graphs that contain an excessively large number of triangles – or, three-way connections in a social network. How can we compute the probability of the rare event, and what is the most likely way that the rare event occurs? In this talk, we will study importance sampling schemes which draw samples from a different probability measure, aka tilted measure, where the rare event occurs less rarely. One common feature of the two applications we consider is the availability of a large deviations principle, which we use to guide our choice of tilted measure, and we will show that the resulting scheme not only outperforms direct Monte Carlo sampling, but is also the most efficient in an asymptotic sense.