# Exact Simulation of the Stationary Distribution of Multi-Server Queues

## Karl Sigman

### Résumé:

The ability to exactly/perfectly simulate independent, identically distributed (iid) copies of random objects (random variables with a pre-specified distribution (or partly pre-specified), stationary distributions of stochastic processes, etc.) is fundamental for carrying out rigorous stochastic simulations in engineering and mathematical sciences. But it is not always possible to do so. Even the Markov Chain Monte Carlo Method (MCMC) does not yield exact copies, only approximations. We discuss here the general notion of exact simulation, and then offer some new results in the context of queueing theory. We start by giving an elementary overview of the method coupling from the past (CFTP) introduced by Propp and Wilson (1996) for exactly simulating the stationary distribution of finite state Markov chains, with some simple examples to gain intuition. One example involves stochastic perpetuities, that is, the stationary distribution of the Markov chain Zn+1 = An Zn + Bn where {An} and {Bn} are iid sequences; how to exactly simulate from the distribution of Z satisfying the fixed point equation (in distribution) Z = AZ + B.

 Karl Sigman Columbia University