Coalescence in Markov Chains

Abstract A Markov chain $$X^i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>X</mml:mi> <mml:mi>i</mml:mi> </mml:msup> </mml:math> on a finite state space S has transition matrix P and initial state i . We may run the chains $$(X^i: i\in S)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>X</mml:mi> <mml:mi>i</mml:mi> </mml:msup> <mml:mo>:</mml:mo> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>(</mml:mo> <mml:mi>μ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of coalescence classes of the process, and what is the set K ( P ) of such numbers $$k(\mu )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>(</mml:mo> <mml:mi>μ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , as the coupling $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> 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.