A Markov chain <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$X^i$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>X</mi> <mi>i</mi> </msup> </math></EquationSource> </InlineEquation> on a finite state space S has transition matrix P and initial state i. We may run the chains <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$(X^i: i\in S)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mi>X</mi> <mi>i</mi> </msup> <mo>:</mo> <mi>i</mi> <mo>∈</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$k(\mu )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo stretchy="false">(</mo> <mi>μ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of coalescence classes of the process, and what is the set K(P) of such numbers <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$k(\mu )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo stretchy="false">(</mo> <mi>μ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, as the coupling <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mu $</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation> 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.

Coalescence in Markov Chains

期刊论文
出版模式：

开放获取
发表日期：

2026年5月11日

查看全文

Geoffrey R. Grimmett,
Mark Holmes

摘要

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 \in 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.