2019/07/12 by Geoffrey Grimmett, Grimmett, Geoffrey R., Mark J. Holmes +1 · 1 citation
Mathematics · #60J10 #60J22 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1907.05605
openalex publication_date 2019/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
The method of 'coupling from the past' permits exact sampling from the invariant distribution of a Markov chain on a finite state space. The coupling is successful whenever the stochastic dynamics are such that there is coalescence of all trajectories. The issue of the coalescence or non-coalescence of trajectories of a finite state space Markov chain is investigated in this note. The notion of the 'coalescence number' k(μ) of a Markovian coupling μ is introduced, and results are presented concerning the set K(P) of coalescence numbers of couplings corresponding to a given transition matrix P. Note: This is a revision of the original published version, in which part of Theorem 6 has been removed. A correction may be found in Thm 5.3 of arXiv:2510.13572.