Coalescence in Markov Chains

Abstract A Markov chain $$X^i$$ X i on a finite state space S has transition matrix P and initial state i . We may run the chains $$(X^i: i\in S)$$ ( X i : i ∈ S ) in parallel, while insisting that any two such chains coalesce whenever they are simultaneously at the same state. There are | S | trajectories which evolve separately, but not necessarily independently, prior to coalescence. What can be said about the number $$k(\mu )$$ k ( μ ) of coalescence classes of the process, and what is the set K ( P ) of such numbers $$k(\mu )$$ k ( μ ) , as the coupling $$\mu $$ μ of the chains ranges over couplings that are consistent with P ? We continue earlier work of Grimmett and Holmes (In: In and out of equilibrium 3, Birkhäuser/Springer, Cham, 2021) on these two fundamental questions, which have special importance for the “coupling from the past” algorithm. We concentrate partly on a family of couplings termed block measures, which may be viewed as couplings of lumpable chains with coalescing lumps. Constructions of such couplings are presented and also of non-block measure with similar properties.