2003, Volume 65, Pt. 4 , 763--777

PERFECT SAMPLING FOR DOEBLIN CHAINS

By

KRISHNA B. ATHREYA, Cornell University, Ithaca, USA and Iowa State University, Ames, USA and \"ORJAN STENFLO, Stockholm University, Stockholm, Sweden

SUMMARY. For Markov chains that can be generated by iteration of i.i.d.\ random maps from the state space $X$ into itself (this holds if $X$ is Polish) it is shown that the Doeblin minorization condition is necessary and sufficient for the method by Propp and Wilson for  ``perfect'' sampling from the stationary distribution $\pi$ to be  successful. Using only the transition probability ${\bf P}$ we produce in a geometrically distributed random number of steps $N$ a ``perfect'' sample from $\pi$ of size $N!$.

AMS (1991) subject classification. 65C05.

Key words and phrases. Exact sampling, perfect sampling, iterated function systems, Markov chains.

Full paper (PDF)