On Exact Sampling of Stochastic Perpetuities (with K. Sigman).

Summary:

This paper develops a Dominated Coupling From The Past (DCFTP) algorithm for simulation without bias (i.e. exact sampling) from the distribution of the Markov chain D_{n+1} = exp(X_{n+1})*D_{n} + B_{n+1}. We assume that the X_n’s and the B_n’s form two independent sequences of i.i.d random variables. We also assume that there exists theta > 0 such that Eexp(theta*X_{n}) < infinity (in fact, given this condition, because we of course need to assume the existence of the steady-state distribution it turns out that there is theta > 0 such that Eexp(theta*X_{n}) < 1). Finally, we also assume that B_n has a density with tails that are not too thin, (including Exponential-type tails, Pareto-type tails, etc but ruling out Gaussian-type tails). The paper also contains an algorithm to sample from the steady-state waiting time of a GI/GI/1 queue assuming the inter-arrival times and service times have finite exponential moments of some order; actually, the algorithm can be used to sample the whole system, not only the workload, in stationarity but this is not discussed in this paper.

Bibtex:

@Article{BlaSig11,

author = { J. Blanchet and K. Sigman},

title = {On exact sampling of stochastic perpetuities},

journal = {Journal of Applied Probability},

year = {To appear},

volume = {},

pages = {}

}