arxiv: 2604.12853 · v2 · submitted 2026-04-14 · 🧮 math.PR

Recognition: unknown

Coupling Markov chains with a common image chain

Edward Crane , Alexander E. Holroyd , Erin Russell

Authors on Pith no claims yet

Pith reviewed 2026-05-10 14:12 UTC · model grok-4.3

classification 🧮 math.PR MSC 60J10

keywords Markov chain couplingcommon image chainconditional independencelumping conditionsstationary couplingcountable state spacesjoint Markov process

0 comments

The pith

Markov chains X and Y whose images under maps f and g both match the law of a Markov chain Z can be coupled so the pair evolves as a single homogeneous Markov process with f(X_t) equal to g(Y_t) at every step.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to construct a coupling of two Markov chains on countable spaces such that their joint evolution remains Markov while the images under the given maps stay identical and follow the common chain Z. The construction also makes the two original chains conditionally independent once the shared image trajectory is known. This holds for any initial distributions as long as Z is Markov, and the paper gives an explicit method to build the coupling. When X and Y are stationary, the coupling itself can be made stationary, with conditional independence extending to two-sided infinite-time versions.

Core claim

We prove that X and Y can be coupled so that (X_t, Y_t)_{t ≥ 0} is a homogeneous Markov chain with f(X_t) = g(Y_t) for all t ≥ 0. Moreover, X and Y are conditionally independent given the entire trajectory (f(X_t))_{t ≥ 0}. Under the further assumption that X and Y are stationary, we construct a coupling having the above properties that is also stationary. In this case, conditional independence holds for the corresponding two-sided chains indexed by Z (but not necessarily for the one-sided versions).

What carries the argument

The explicit coupling of the pair (X, Y) that forces the images to coincide at every time while keeping the joint process Markov and enforcing conditional independence given the common image trajectory.

If this is right

The coupling exists for arbitrary time-homogeneous Markov chains X and Y on countable spaces whenever their images share the law of a Markov chain Z.
A stationary version of the coupling exists when X and Y are stationary, and conditional independence then holds for the two-sided processes.
When f satisfies the strong lumping condition and g satisfies the exact lumping condition, the constructed coupling has the same properties as standard intertwining constructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The construction supplies a concrete way to realize joint realizations of processes that are only known to have matching marginal projections.
It may allow direct simulation of multiple chains driven by a single shared image path without losing the Markov property of the joint system.
The method clarifies when conditional independence given an observed projection can be arranged while preserving the dynamics of the hidden chains.

Load-bearing premise

The common image process must itself follow the Markov property.

What would settle it

A concrete non-Markov process Z whose law equals that of f(X) and g(Y) for some Markov X and Y, yet no joint Markov coupling exists in which the images remain equal at all times.

Figures

Figures reproduced from arXiv: 2604.12853 by Alexander E. Holroyd, Edward Crane, Erin Russell.

**Figure 1.** Figure 1: Bat-cave example from [4]. 8. Examples We give several examples which serve to illustrate key points. In Example 1, Markov chains X and Y share an image process Z that is not itself Markov, and we show that they have no weak Markovian coupling taking values in ∆pf, gq. Example 2 illustrates that when X and Y are stationary, the coupling constructed in our proof of Theorem 1 need not be stationary. Exampl… view at source ↗

**Figure 2.** Figure 2: Chains X¯ (above) and Y¯ (below) in Example 1. Let A “ B “ t1, 2, 3, 4u and C “ t0, 1u. Define f : A Ñ C and g : B Ñ C by fp2q “ 0, gp1q “ 0, and fpiq “ gpjq “ 1 in all other cases. Let PX “ ¨ ˚˚˝ 0 1 0 0 1{3 0 2{3 0 0 1{4 0 3{4 0 0 1 0 ˛ ‹ ‹‚ and PY “ ¨ ˚˚˝ 0 1 0 0 1{2 0 1{2 0 0 1{2 0 1{2 0 0 1 0 ˛ ‹ ‹‚. The marked states in [PITH_FULL_IMAGE:figures/full_fig_p032_2.png] view at source ↗

**Figure 3.** Figure 3: Transition probabilities of W from time t to time t ` 1 in Example 1 times t, and these are completely determined by the marginal constraints. The transition probabilities out of states whose first coordinate is odd are defined only for odd t. For every odd t ě 1, PpXt´1 “ 2, Xt “ 3q ą 0, so PpWt “ p3, 2qq ą 0, and hence we may define the time-dependent transition probability pt “ PpWt`1 “ p4, 3q | Wt “ p3… view at source ↗

**Figure 4.** Figure 4: The Markov chains and maps in Example 3. p0, 0 1 q p1, 1 1 p1, 2 q 1 q p2, 2 1 q 1{6 1{3 1{2 1{4 3{4 1 1 W P “ ¨ ˚˚˝ 0 1{3 1{6 1{2 0 0 1{4 3{4 0 1 0 0 1 0 0 0 ˛ ‹ ‹‚ [PITH_FULL_IMAGE:figures/full_fig_p035_4.png] view at source ↗

**Figure 5.** Figure 5: WMC of X and Y in Example 3. This allows us to calculate the values of φ, using φpa, bq “ πpa, bqπZpfpaqq πXpaqπY pbq as follows. pa, bq p0, 0 1 q p1, 1 1 q p1, 2 1 q p2, 1 1 q p2, 2 1 q φpa, bq 1 2 1{2 0 3{2 Note that in this case, ∆1 ‰ ∆. Using φ we may compute the transition matrix P described immediately after Theorem 1, obtaining the WMC MCpπ, Pq illustrated in [PITH_FULL_IMAGE:figures/full_fig_p035_5.png] view at source ↗

**Figure 6.** Figure 6: Exact Markovian coupling of two biased simple random walks in which the absolute values coincide. Perhaps surprisingly, p|Xt |qtě0 is also a homogeneous Markov chain. Its transition matrix is defined as follows for z, z1 P N. PZpz, z1 q “ $ ’’’’’’& ’’’’’’% 1, z “ 0, z1 “ 1, p z`1 ` q z`1 p z ` q z , z ě 1, z1 “ z ` 1, p z q ` q z p p z ` q z , z ě 1, z1 “ z ´ 1, 0, otherwise. To verify this, for each n ě 0… view at source ↗

**Figure 6.** Figure 6: Proposition 10 tells us that this coupling is an EMC, and the reader may enjoy verifying this directly. To check that proj2 is an exact lumping, consider the family of probability measures pµyqyPZ on ∆ given by µy “ $ ’’’& ’’’% 1 2 δpy,yq ` 1 2 δp´y,yq if y ă 0, δp0,0q if y “ 0, q y 2p y δp´y,yq ` ´ 1 ´ q y 2p y ¯ δpy,yq if y ą 0. We remark that the behaviour of W given Z is easy to describe: for each fini… view at source ↗

read the original abstract

Consider time-homogeneous discrete-time Markov chains $X$, $Y$, and $Z$ on countable state spaces, considered as stochastic processes with specified initial distributions. Suppose for maps $f$ and $g$ that $(f(X_t))_{t \ge 0}$ and $(g(Y_t))_{t \ge 0}$ are both equal in law to $Z$. We prove that $X$ and $Y$ can be coupled so that $(X_t, Y_t)_{t \ge 0}$ is a homogeneous Markov chain with $f(X_t) = g(Y_t)$ for all $t \ge 0$. Without the assumption that $Z$ is Markov, no such Markov coupling exists in general, even an inhomogeneous one. Moreover, we give an explicit construction of such a coupling, with the additional property that $X$ and $Y$ are conditionally independent given the entire trajectory $(f(X_t))_{t \ge 0}$. Under the further assumption that $X$ and $Y$ are stationary, we construct a coupling having the above properties that is also stationary. In this case, conditional independence holds for the corresponding two-sided chains indexed by $\mathbb{Z}$ (but not necessarily for the one-sided versions). We prove further properties of our couplings in special cases where $f$ or $g$ satisfies the strong lumping condition (also known as Dynkin's condition) or the exact lumping condition (also known as the Pitman-Rogers condition). When $f$ is a strong lumping and $g$ is an exact lumping, we show that our coupling coincides with an intertwining of Markov chains as constructed by Diaconis and Fill.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an explicit construction for a homogeneous Markov coupling of two chains that share a common image process Z, with X and Y conditionally independent given Z's trajectory, and shows this requires Z to be Markov.

read the letter

The main takeaway is that the authors construct a joint process on pairs (X_t, Y_t) that stays Markov and homogeneous while forcing f(X_t) = g(Y_t) for all t, and they make X and Y independent once the image path is fixed. They also extend it to the stationary case and recover the Diaconis-Fill intertwining when the maps satisfy strong or exact lumping. The construction is straightforward once you define the image kernel Q and the conditional kernels K and L that divide the original transitions by Q; the marginals recover correctly and the conditional independence follows from independent draws given Z. This is new as an explicit, homogeneous version with the independence property, beyond what was already in the coupling and lumping literature. The necessity of Z being Markov is shown by a counterexample when it is not, which keeps the claim sharp. The work is clean on countable discrete-time spaces and uses only standard coupling ideas, so there is no circularity or hidden fitting. The main limitation is the narrow setting: everything is discrete-time and countable, so extensions to continuous time or uncountable spaces would need separate arguments. The stationary two-sided version is handled, but the one-sided conditional independence does not always hold, which is noted but not a flaw. This is a technical paper aimed at people who work on Markov couplings, lumpings, and intertwining. A reader who needs to simulate or analyze lumped chains would get a usable construction from it. The result is grounded enough and the construction explicit enough that it deserves a serious referee rather than a desk reject.

Referee Report

0 major / 3 minor

Summary. The paper proves that for time-homogeneous Markov chains X and Y on countable state spaces whose images under maps f and g are equal in law to a Markov chain Z, there exists a coupling such that the joint process (X_t, Y_t) is itself a time-homogeneous Markov chain with f(X_t) = g(Y_t) for all t, and with X and Y conditionally independent given the full trajectory of Z. An explicit construction is provided via the common image transition kernel Q and the conditional kernels K and L. The paper also constructs a stationary version of the coupling under stationarity assumptions (with two-sided conditional independence), proves that Z must be Markov for such a coupling to exist (even inhomogeneous), and shows that the coupling coincides with a Diaconis-Fill intertwining when f is a strong lumping and g an exact lumping.

Significance. If the central claims hold, the result supplies a constructive and explicit method for coupling Markov chains that share a common image process while preserving the Markov property of the pair and delivering conditional independence given the image trajectory. This has clear value for coupling-based analyses, simulation, and comparison of processes. The explicit kernel construction (factoring the joint transition as Q · K · L) and the verification that marginals recover the original chains are strengths, as is the necessity argument for Z being Markov and the analysis of lumping cases linking to existing intertwining theory.

minor comments (3)

[Construction section] In the construction of the joint kernel (around the definition of K and L), a brief remark on how the normalization by Q(z, z') behaves when Q(z, z') = 0 would help readers confirm the kernel is well-defined on the support.
[Stationary case] The stationary coupling section could include a short note on whether the two-sided conditional independence extends to the one-sided chains or requires the bi-infinite indexing explicitly.
[Abstract and §1] A minor typographical inconsistency appears in the abstract and introduction regarding the phrasing of 'even an inhomogeneous one'; ensure uniform terminology for the non-existence claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper, for highlighting its contributions to constructive couplings and connections to intertwining theory, and for the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is a pure existence proof that supplies an explicit probabilistic construction of the desired coupling. It defines the common-image transition kernel Q from the given Markov chain Z, then constructs conditional kernels K and L from the original transitions of X and Y normalized by Q. The joint kernel on the constrained state space is written as the product Q · K · L; direct summation verifies that the X and Y marginals recover the prescribed time-homogeneous transitions independently of the other chain. Conditional independence given the Z trajectory follows immediately from the independent draws from K and L. All steps are standard coupling arguments on countable spaces; no parameter is fitted to data, no quantity is defined in terms of the target object, and no load-bearing claim rests on a self-citation. The necessity of Z being Markov is shown by a separate counter-example argument. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard measure-theoretic foundations for defining stochastic processes and couplings on countable spaces; no free parameters, new entities, or ad-hoc axioms are introduced beyond the problem setup.

axioms (2)

standard math Existence of a probability space supporting the joint process and the given marginal laws
Implicit in any coupling construction for stochastic processes on countable spaces.
domain assumption Time-homogeneous Markov property for X, Y, and Z
Stated explicitly in the problem setup for discrete-time chains.

pith-pipeline@v0.9.0 · 5613 in / 1384 out tokens · 49795 ms · 2026-05-10T14:12:00.454956+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

37 extracted references · 2 canonical work pages

[1]

Avoidance coupling.Electronic Communications in Probability, 18(58):1–13, 2013

Omer Angel, Alexander Holroyd, James Martin, Peter Winkler, and David Wilson. Avoidance coupling.Electronic Communications in Probability, 18(58):1–13, 2013

2013
[2]

On Markov inter- twiningrelationsandprimalconditioning.Journal of Theoretical Probability, 37:2425– 2456, 2024

Marc Arnaudon, Koléhè Coulibaly-Pasquier, and Laurent Miclo. On Markov inter- twiningrelationsandprimalconditioning.Journal of Theoretical Probability, 37:2425– 2456, 2024

2024
[3]

Frank Ball and Geoffrey F. Yeo. Lumpability and marginalisability for continuous- time Markov chains.J. Appl. Probab., 30(3):518–528, Sep. 1993

1993
[4]

Waiting for a bat to fly by (in polynomial time).Combinatorics, Probability and Computing, 15(5):673–683, 2006

Itai Benjamini, Gady Kozma, Lászlo Lovász, Dan Romik, and Gabor Tardos. Waiting for a bat to fly by (in polynomial time).Combinatorics, Probability and Computing, 15(5):673–683, 2006

2006
[5]

Cambridge University Press, 2020

Tomasz Bielecki, Jacek Jakubowski, and Mariusz Niew¸ egłowski.Structured depen- dence between stochastic processes, volume 175 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press, 2020

2020
[6]

Intricacies of depen- dence between components of multivariate Markov chains: weak Markov consistency and weak Markov copulae.Electronic Journal of Probability, 18(45):1–21, 2013

Tomasz Bielecki, Jacek Jakubowski, and Mariusz Niewęgłowski. Intricacies of depen- dence between components of multivariate Markov chains: weak Markov consistency and weak Markov copulae.Electronic Journal of Probability, 18(45):1–21, 2013

2013
[7]

Bossaller and Sergio R

Daniel P. Bossaller and Sergio R. López-Permouth. On the associativity of infinite matrix multiplication.The American Mathematical Monthly, 126(1):41–52, 2019

2019
[8]

Markovian maximal coupling of Markov processes

Björn Böttcher. Markovian maximal coupling of Markov processes. arXiv:1710.09654, 2017

work page arXiv 2017
[9]

Exact and ordinary lumpability in finite Markov chains.Journal of Applied Probability, 31(1):59–75, 1994

Peter Buchholz. Exact and ordinary lumpability in finite Markov chains.Journal of Applied Probability, 31(1):59–75, 1994

1994
[10]

Krzysztof Burdzy and Wilfrid S. Kendall. Efficient Markovian couplings: examples and counterexamples.The Annals of Probability, 10(2):362–409, 2000

2000
[11]

PhD thesis, Illinois Institute of Technology, 2017

Yu-Sin Chang.Markov chain structures with applications to systemic risk. PhD thesis, Illinois Institute of Technology, 2017

2017
[12]

Coupling for jump processes.Acta Math

MuFa Chen. Coupling for jump processes.Acta Math. Sinica, New Series, 2(2):123– 136, 1986

1986
[13]

Optimal co-adapted coupling for a random walk on the hyper- complete-graph.Journal of Applied Probability, 50(4):1117–1130, 2014

Stephen Connor. Optimal co-adapted coupling for a random walk on the hyper- complete-graph.Journal of Applied Probability, 50(4):1117–1130, 2014

2014
[14]

Optimal co-adapted coupling for the symmetric random walk on the hypercube.Journal of Applied Probability, 45(1):703–713, 2008

Stephen Connor and Saul Jacka. Optimal co-adapted coupling for the symmetric random walk on the hypercube.Journal of Applied Probability, 45(1):703–713, 2008

2008
[15]

Coupling Markov chains with a common image chain II

Edward Crane, Alexander Holroyd, and Erin Russell. Coupling Markov chains with a common image chain II. To appear
[16]

Coupling homogeneous Markov chains by a homo- geneous Markov chain, with constraints

Edward Crane and Erin Russell. Coupling homogeneous Markov chains by a homo- geneous Markov chain, with constraints. To appear
[17]

Weak lumping of left-invariant random walks on left cosets of finite groups, 2024

Edward Crane, Álvaro Gutiérrez, Erin Russell, and Mark Wildon. Weak lumping of left-invariant random walks on left cosets of finite groups, 2024. https://arxiv.org/abs/2412.19742

work page arXiv 2024
[18]

Bisimulation for labelled Markov processes.Information and Computation, 179(2):163–193, 2002

Josée Desharnais, Abbas Edalat, and Prakash Panangaden. Bisimulation for labelled Markov processes.Information and Computation, 179(2):163–193, 2002

2002
[19]

Strong stationary times via a new form of duality

Persi Diaconis and James Allen Fill. Strong stationary times via a new form of duality. The Annals of Probability, 18(4):1483–1522, 1990

1990
[20]

Semi-pullbacks and bisimulation in categories of Markov processes

Abbas Edalat. Semi-pullbacks and bisimulation in categories of Markov processes. Mathematical Structures in Computer Science, 9(5):523—-543, 1999

1999
[21]

Markov property for a function of a Markov chain: A linear algebra approach.Linear algebra and its applications, 404:85–117, 2005

Leonid Gurvits and James Ledoux. Markov property for a function of a Markov chain: A linear algebra approach.Linear algebra and its applications, 404:85–117, 2005. COUPLING MARKOV CHAINS WITH A COMMON IMAGE CHAIN 39

2005
[22]

Probability Theory and Stochastic Modelling

Erich Häusler and Harald Luschgy.Stable convergence and stable limit theorems. Probability Theory and Stochastic Modelling. Springer, 2015

2015
[23]

Kemeny and J

John G. Kemeny and J. Laurie Snell.Finite Markov chains. Springer, 1976

1976
[24]

Total variation convergence preserves conditional independence

Steffen Lauritzen. Total variation convergence preserves conditional independence. Statistics & Probability Letters, 214:110200, 2024

2024
[25]

Levin, Yuval Peres, and Elizabeth L

David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times.American Mathematical Soc., Providence, 2009

2009
[26]

Javier López and Gerardo Sanz

F. Javier López and Gerardo Sanz. Markovian couplings staying in arbitrary subsets of the state space.Journal of Applied Probability, 39(1):197–212, 2002

2002
[27]

On the relations between Markov chain lumpability and reversibility.Acta Informatica, 54(5):447–485, 08 2017

Andrea Marin and Sabina Rossi. On the relations between Markov chain lumpability and reversibility.Acta Informatica, 54(5):447–485, 08 2017

2017
[28]

A strong version of the Skorohod representation the- orem.Journal of Theoretical Probability, 36(1):372–389, 2023

Luca Pratelli and Pietro Rigo. A strong version of the Skorohod representation the- orem.Journal of Theoretical Probability, 36(1):372–389, 2023

2023
[29]

L. Chris G. Rogers and Jim W. Pitman. Markov functions.The Annals of Probability, 9(4):573–582, 1981

1981
[30]

A finite characterization of weak lumpable Markov processes

Gerardo Rubino and Bruno Sericola. A finite characterization of weak lumpable Markov processes. Part I: The discrete time case.Stochastic Proc. Appl., 38(2):195– 204, 1991

1991
[31]

Cam- bridge University Press, 2014

Gerardo Rubino and Bruno Sericola.Markov chains and dependability theory. Cam- bridge University Press, 2014

2014
[32]

An introduction to joinings in ergodic theory.Discrete and Con- tinuous Dynamical Systems, 15(1):121–142, 2006

Thierry de la Rue. An introduction to joinings in ergodic theory.Discrete and Con- tinuous Dynamical Systems, 15(1):121–142, 2006

2006
[33]

Russell.Coupling Markov chains with Markov chains

Erin G. Russell.Coupling Markov chains with Markov chains. PhD thesis, University of Bristol, 2025

2025
[34]

Schweitzer

Paul J. Schweitzer. Aggregation methods for large Markov chains. In G. Iazeolla, editor,Mathematical Computer Performance and Reliability, pages 275–286. Elsevier- North-Holland, 1984

1984
[35]

Jan M. Swart. Duality and intertwining of Markov chains. Lecture notes from ALÉA in Europe School, CIRM, Luminy, 2013 https://staff.utia.cas.cz/swart/lecture_notes/dualtwine.pdf, retrieved 4 Dec 2025

2013
[36]

Jan M. Swart. Intertwining of birth-and-death processes.Kybernetika, 47(1):1–14, 2011

2011
[37]

American Mathematical Soc., 2021

Cédric Villani.Topics in optimal transportation, volume 58 ofGraduate Studies in Mathematics. American Mathematical Soc., 2021. University of Bristol, UK Email address:edward.crane@bristol.ac.uk Email address:a.e.holroyd@bristol.ac.uk Email address:erin.russell@bristol.ac.uk

2021