SCS

Abstract

We shall discuss several importance sampling techniques for efficient estimation of overfow probabilities or sampling conditional paths in stochastic networks. We are interested in a wide class of environments including light-tailed and heavy-tailed networks. Our discussion includes algorithms that are optimal in the sense of achieving the best possible rate of convergence as the associated large deviations parameter increases. For instance, in the case of arbitrary Jackson networks our estimators are strongly efficient and we can generate exact conditional overflow paths in linear time (as a function of the overflow level). This talk is based on joint work with Peter Glynn, Henry Lam, Kevin Leder, Chenxin Li and Jingchen Liu.