Invariant Measures for Queueing and Spatial Markov Processes: Algorithms and Analysis

As is well known, Monte Carlo methods are ubiquitous in many applied domains. One of the main uses of these methods is to study the long-time behavior of stochastic systems of interest. Under some ergodicity conditions, the long-time behavior of a system can be specified by the invariant measure (or the steady-state distribution) of the Markov process that describes the system. In this talk, we provide and analyze Monte Carlo algorithms associated with invariant measures of queueing and spatial Markov processes. In particular, we propose and analyze an implementable regenerative simulation scheme to estimate the steady-state parameters of queueing networks where the inter-arrival times are generally distributed but have exponential or heavier tails.  We then consider Gibbs point processes (that is, the family of spatial point processes that are absolutely continuous with respect to some Poisson point process; examples include Area-interaction processes, Strauss processes, Ising models, Loss systems). A key feature of such a point process is that its distribution can be realized as an invariant measure of a spatial birth-and-death process. We analyze a simple acceptance-rejection based sampling algorithm for generating exact samples from Gibbs point processes. We further develop and analyze importance sampling and infinite series based representations that are seen to provide unbiased estimators for functions of these point processes. The proof of their effectiveness for certain loss systems depends on our large deviations analysis of no overlap probability of spheres when their centers are distributed as a homogeneous Poisson point process; this analysis may also be of independent interest.