A note on faithful coupling of Markov chains
Debojyoti Dey1 , Pranjal Dutta2 , and Somenath Biswas1

arXiv:1710.10026v1 [cs.DS] 27 Oct 2017

1

Department of Computer Science and Engineering, Indian Institute of Technology Kanpur,
Kanpur-208016.
2
Chennai Mathematical Institute, Chennai-603103.

October 2017

Abstract
One often needs to turn a coupling (Xi , Yi )i≥0 of a Markov chain into a sticky
coupling where once XT = YT at some T , then from then on, at each subsequent
time step T ′ ≥ T , we shall have XT ′ = YT ′ . However, not all of what are considered
couplings in literature, even Markovian couplings, can be turned into sticky couplings,
as proved by Rosenthal [Ro97] through a counter example. Rosenthal then proposed a
strengthening of the Markovian coupling notion, termed as faithful coupling, from which
a sticky coupling can indeed be obtained. We identify the reason why a sticky coupling
could not be obtained in the counter example of Rosenthal, which motivates us to define
a type of coupling which can obviously be turned into a sticky coupling. We show then
that the new type of coupling that we define, and the faithful coupling as defined by
Rosenthal [Ro97], are actually identical. Our note may be seen as a demonstration of
the naturalness of the notion of faithful coupling.

1

Introduction

First, we recall certain basic definitions and fix our notations. For a random variable X,
we denote its distribution as D(X). Let M be a finite Markov chain on the state space
Ω, and with the transition matrix P . Following [No97], we abbreviate the Markov chain
(Xi )i≥0 , with D(X0 ) = λ and D(Xi+1 ) = D(Xi )P for i ≥ 0, as Markov(λ, P ). A coupling
of the Markov chain M is a process (Xi , Yi )i≥0 , with each Xi , Yi taking values in Ω and
evolving on a common probability space, where (Xi )i≥0 satisfies the property that, for i ≥ 0,
D(Xi+1 ) = D(Xi )P and similarly, (Yi )i≥0 satisfies, for i ≥ 0, D(Yi+1 ) = D(Yi )P .
Remark A: The definition of Markov chain coupling, as given in [LPW09], says that both (Xi )i≥0
and (Yi )i≥0 are Markov chains with transition matrix P . The reason we prefer the above weaker
definition is because in literature we find processes considered as couplings that do not satisfy

1

the stronger notion of [LPW09], but do satisfy our above definition. A Markov chain (Xi )i≥0
with transition matrix P , by definition, satisfies the property (π) that for i ≥ 0, conditioned on
Xi = l, Xi+1 has the distribution P (l, ·) and is indepedent of X0 , . . . , Xi−1 . As we shall see in the
next section, there is a Markovian coupling (Xi , Yi )i≥0 , where (Xi )i≥0 does not satisfy the property
(π), although Xi ’s do evolve (under certain conditions) as per the transition matrix P .

Let D(X0 ) be µ and D(Y0 ) be ν. In the above, since each pair, Xi and Yi , i ≥ 0, is defined
on the same probability space, the two random variables, Xi , Yi , for each i ≥ 0, are coupled,
and so we have, from the above definition of Markov chain coupling, and Proposition 4.7 of
[LPW09]:
kµP i − νP i kTV = kD(Xi ) − D(Yi )kTV ≤ Pr(Xi 6= Yi )
(1)
(Here, k · kTV denotes the total variational distance between two distributions.)
Let us suppose that a coupling of M has the ‘now-equals-forever’ property ([Ro97]), namely,
if Xn = Yn for some n, then for all j ≥ n, Xj = Yj . Then, if T is defined as the random
time
def
T = inf{i|Xi = Yi }
(2)
we get from the relation (1)
|kD(Xi ) − D(Yi )kTV ≤ Pr(Xi 6= Yi ) = Pr(T > i)

(3)

as the two events (Xi 6= Yi ) and (T > i) imply each other, making use of the ‘now-equalsforever’propery.
As such, the applicability of the inequality (3) is limited as most couplings of Markov chains
will not have the ‘now-equals-forever’ property. The way that is often resorted to to tackle
this problem is to define a new process (Zi )i≥0 as follows: ([Ro97])

Xi if i ≤ T
Zi =
(4)
Yi
otherwise
where T is as in (2) above. If it so happens that (Zi )i≥0 = Markov(µ, P ) then, since
(Zi , Yi )i≥0 is a coupling of the Markov chain satisfying ‘now-equals-forever’ property, we
have
kµP i − νP i kTV = kD(Zi ) − D(Yi )kTV ≤ Pr(T > i)
The construction of (Zi ) has been evocatively termed as sticking and the resultant new
coupling as a sticky coupling [HM17].
Definition 1 (Markovian coupling of a Markov chain) A coupling (Xi , Yi )i≥0 of a Markov
chain M on state space Ω, and with its transition matrix as P , where D(X0 ) = µ and
def

D(Y0 ) = ν, for given µ and ν, is said to be a Markovian coupling if (Wi )i≥0 , with Wi =
(Xi , Yi ) is itself a Markov chain on state space Ω × Ω, with a specified joint distribution
of D(X0 ) and D(Y0 ) as the distribution D(W0 ). In other words, there is a (Ω × Ω, Ω × Ω)
2

transition matrix, say Q, such that for some distribution θ0 on Ω × Ω, satisfying that its
def
marginals are µ = D(X0 ) and ν = D(Y0 ), we will have, for i ≥ 1, with θi = θi−1 Q, the two
marginals of θi will be µP i , that is, D(Xi ) and νP i , that is D(Yi ).
Remark B: We note that the defintion above is specific to a joint distribution of (X0 , Y0 ). The
reason for the specificity is that in the example given by Rosenthal ([Ro97]) of a Markovian coupling
for which sticking fails, as we note in the next section, the ability to evolve the two copies as per
the transition matrix P crucially depends on the initial coupling of X0 and Y0 .

As noted in [HM17], it has been stated at times that sticking will work for all Markovian
couplings. However, this is not correct, Rosenthal [Ro97] provides a counter example. He
then provides a stronger version of Markovian couplings, termed as faithful couplings, for
which it is proved that sticking will provably result in a coupling of M where (Zi )i≥0 , as
defined in (4) above, will indeed be Markov(µ, P ). We discuss Rosenthal’s counterexample
in Section 2 and identify what we consider to be the reason why the sticking operation fails
there. This reason then motivates us in defining a stronger version of Markovian coupling
(Section 3) for which it is easy to see that the sticking will indeed work. We then prove that
the new notion of coupling that we define is actually equivalent to the notion of faithful
coupling.

2

Rosenthal’s counterexample

In his example, Rosenthal [Ro97] considers the Markov chain M with state space Ω = {0, 1},
and with the transition matrix P defined as:
0
1
P = 0 1/2 1/2
1 1/2 1/2
(Xi ), (Yi ), i ≥ 0 are defined as follows:
1. Each of D(X0 ), D(Y0 ) is the uniform distribution on the state space {0, 1},
def

2. Each D(Yi ), i > 0 is also the uniform distribution, whereas for i ≥ 0, Xi+1 = Xi ⊕ Yi ,
⊕ being the exclusive-or operation.
Thus, the joint evolution of the two copies (Xi , Yi ) of the chain, on the state space Ω × Ω,
that is, {(0, 0), (0, 1), (1, 0), (1, 1)} is governed by the following transition matrix Q:
(0, 0)
Q = (0, 1)
(1, 0)
(1, 1)

(0, 0) (0, 1) (1, 0) (1, 1)
1/2
1/2
0
0
0
0
1/2
1/2
0
0
1/2
1/2
1/2
1/2
0
0
3

Convention: The distribtion of a random variable X on Ω = {0, 1} is specified as the
vector
[Pr(X = 0) Pr(X = 1)]
and similarly, the distribution of a random variable W on Ω × Ω as the vector
[Pr(W = (0, 0))

Pr(W = (0, 1))

Pr(W = (1, 0))

Pr(W = (1, 1))]

def

We note that for any distribution σ = [p 1 − p], Ω = {0, 1}, σP will be the uniform
distribution. We also note that for the trivial coupling θ, of [1/2 1/2] and [1/2 1/2],
which is [1/4 1/4 1/4 1/4], θQ will again be θ. Therefore, with the joint distribution θ
of D(X0 ) and D(Y0 ), Q indeed defines a Markovian coupling of the Markov chain M .
Remark C: We also note that there are other joint distributions of the same D(X0 ) and D(Y0 ),
def

for which Q will not be a Markovian coupling: consider θ′ = [3/8 1/8 1/8 3/8), θ′ Q =
[3/8 3/8 1/8 1/8]. The marginals of the latter distributions are [3/4 1/4] and [1/2 1/2]
respectively. Thus, if we use the joint distribution θ′ of the same two initial distributions, while Q
evolves Yi ’s (understandably) as per P , it does not evolve Xi ’s as per P . Hence with the initial joint
distribution θ′ , Q fails to be a Markovian coupling of M . This is why we felt that it is necessary
to make explicit the initial joint distribution in the definition of Markovian coupling of a Markov
chain.

Rosenthal proves that although Q is a Markovian coupling of M with θ as the initial joint
distribution, the result of the sticking operation will fail to evolve M correctly: with T
defined as in (2) and Zi ’s as defined in (4),
Pr(Z0 = 1, Z1 = 0)
= Pr(T = 0, Y0 = 1, Y1 = 0, X0 = 1) + Pr(T > 0, X0 = 1, Y0 = 0, X1 = 0)
= 1/8 + 0
= 1/8
However, had Zi ’s been evolving as per P with the same initial distribution as the uniform
distribution, the probability above would have been 1/4, and not 1/8. Hence, sticking fails.
We see that sticking failed with T = 0. As it happens, sticking will fail here for every value
of T (except, of course, for T = ∞). The reason is provided by the Proposition below. We
need the following definition:
Definition 2 For a state space Ω with s an element in it, δs denotes the distribution on Ω
in which the probability of s is 1, and (therefore,) all the other states have probability 0.
Proposition 3 Let M be a Markov chain with Ω as its state space and P as its transition
matrix, and let Q be a transition matrix for the state space Ω × Ω that defines a Markovian
4

coupling (Wi = (Xi , Yi ))i≥0 of M where D(X0 ) = µ and D(Y0 ) = ν, where the initial
joint distribution used is θ0 . This Markovian coupling of M can be turned into a sticky
coupling using the sticking operation if the following condition holds: for every s ∈ Ω,
defining η0 as the unique joint distribution on Ω × Ω with δs and δs as its two marginals,
and further defining ηi+1 as ηi Q, for each i ≥ 0, we have that for each ηi , i ≥ 0, will be a
joint distribution that has δs P i and δs P i as its marginals. On the other hand, if Q does not
satisfy the condition, then the Q-defined Markovian coupling, in general, cannot be turned
into a sticky coupling.
Proof Sketch.
The condition ensures that both (Xi )i≥0 and (Yi )i≥0 of the Markovian
coupling of M satisfy the strong Markov property (Theorem 1.4.2, [No97]) with respect to
the stopping time T , as defined in (2). Therefore, conditioned on T = m and XT = YT = s,
each of (XT +n )n≥0 and (YT +n )n≥0 will be Markov(δs , P ) and the former will be independent
of X0 , X1 , . . . , XT and the latter will be independent of Y0 , Y1 , . . . , YT . Thus, (XT +n )n≥0
and (YT +n )n≥0 can replace each other. Because of this, sticking is guaranteed to work as
(Xi )i≥0 and (X0 , X1 , . . . , XT , YT +1 , . . .) will be indistinguishable.
We now show that the counter example of Rosenthal does not satify the condition as stated
in the statement of the proposition. As we have seen that the Markovian coupling there
cannot be turned into a sticky coupling, the counter example proves the second part of
the Proposition. Let us suppose that T = m and XT = YT = 0. Conditioned on these
events, D(XT ) = D(YT ) = [1 0]. The only joint distribution with these two distributions
as marginals is [1 0 0 0]. The joint distribution of XT +1 and YT +1 will be given by
[1 0 0 0]Q, which is [1/2 1/2 0 0]. This gives D(XT +1 ) as [1 0], which is not
[1/2 1/2] = D(XT )P . Thus, Q fails to ensure that, conditioned as above, D(XT +1 ) = δ0 P .
On the other hand, D(YT +1 ) = δ0 P , and so (XT +n )n≥0 and (YT +n )n≥0 are different and
cannot replace each other, as required for the sticking operation to work.


3

Strong Markovian coupling

We saw in Section 2 that sticking fails for Q because it does not evolve (Xi )i≥0 as per P
for certain joint distributions. Therefore, the following definition of a type of coupling of
Markov chains immediately suggests itself to correct the defect:
Definition 4 (Strong Markovian coupling) A coupling of a finite Markov chain M
with state space Ω and transition matrix P is a strong Markovian coupling if there is a
transition matrix Q from Ω × Ω to Ω × Ω such that for every pair of distributions µ and ν,
each on Ω, and for every joint distribution θ of µ and ν, θQ will be a joint distribution of
µP and νP .
From this definition it follows that:
5

Claim 5 Let Q be a strong Markovian coupling of a finite Markov chain M with state space
Ω and transition matrix P , and for two random variables X0 and Y0 on Ω let D(X0 ), D(Y0 )
be µ and ν respectively, and let θ0 be any joint distribution of µ and ν. If we define θi+1
as θi Q, for i ≥ 0, and Xi+1 and Yi+1 as two random variables whose distributions are
respectively the two marginals of θi+1 then
1. (Xi )i≥0 will be Markov(µ, P ) and (Yi )i≥0 will be Markov(ν, P ). Consequently,
2. D(Xi ) = µP i and D(Yi ) = νP i , for i ≥ 0,
3. Both (Xi )i≥0 and (Yi )i≥0 will satisfy the strong Markov property, and therefore, the
coupling Q of M can be turned into a valid sticky coupling through sticking.
We see next that the strong Markovian coupling is actually equivalent to the familiar notion
of faithful coupling which is defined as:
Definition 6 (Faithful coupling [Ro97]) A Markov coupling of a finite Markov chain
M , with Ω as its state space and P as its transition matrix, is a faithful coupling given by
a Markov chain (Wi )i≥0 = (Xi , Yi )i≥0 , on state space Ω × Ω, with transition matrix Q, if Q
satisfies, for all i, j, i′ , j ′ ∈ Ω, the following
X
Q((i, j), (i′ , j ′ )) = P (i, i′ ), and
j ′ ∈Ω

X

Q((i, j), (i′ , j ′ )) = P (j, j ′ )

i′ ∈Ω

Equivalently, for all t ≥ 0 and all i, j, i′ , j ′ ∈ Ω
Pr(Xt+1 = i′ |Xt = i, Yt = j) = P (i, i′ ), and
Pr(Yt+1 = j ′ |Xt = i, Yt = j) = P (j, j ′ )
Remark D: This kind of coupling has been termed in [LPW09], as well as in [MU05], as Markovian
coupling; however, we follow the terminology of [HM17] for reasons given therein. It is to be noted
that most coupling constructions of Markov chains turn out to be faithful couplings, as the various
coupling examples in [LPW09] demonstrate.

Proposition 7 A Markov chain coupling is faithful if and only if it is a strong Markovian
coupling.
The two lemmas below prove the two directions of the above proposition.

6

Lemma 8 Every faithful coupling of a Markov chain M is a strong Markovian coupling.
Proof. Let M be a Markov chain with state space Ω and transition matrix P . Let the
transition matrix Q, giving transition probabilities from Ω × Ω to Ω × Ω, define a faithful
coupling of the Markov chain M . Let µ and ν be two distributions on Ω, and let θ be a
joint distribution of µ and ν. We need to prove that µP and νP are the two marginals of
θQ. In particular, we need to show:
X
For all x ∈ Ω,
(θQ)(x, y) = (µP )(x)
(5)
y∈Ω

and,
For all y ∈ Ω,

X

(θQ)(x, y) = (νP )(y)

(6)

x∈Ω

We prove (5) as follows:
X
(θQ)(x, y)
y∈Ω

=

X

X

θ(u, v)Q((u, v), (x, y))

y∈Ω (u,v)∈Ω×Ω

=

X

θ(u, v)

X

θ(u, v)P (u, x), because Q defines a faithful coupling

Q((u, v), (x, y))

y∈Ω

(u,v)∈Ω×Ω

=

X

(u,v)∈Ω×Ω

=

X

P (u, x)

X

P (u, x)µ(u), θ being the joint ditribution of µ and ν

u∈Ω

=

X

θ(u, v)

v∈Ω

u∈Ω

= (µP )(x)
In a similar manner we can prove (6).



For the other direction, we prove
Lemma 9 Every strong Markovian coupling of a Markov chain M is a faithful coupling of
M.
Proof. Let M be a Markov chain with state space Ω and transition matrix P . Let the
transition matrix Q, giving transition probabilities from Ω × Ω to Ω × Ω, define a strong
Markovian coupling of the Markov of M . For any (u, v) ∈ Ω × Ω, consider the probabilty
7

distribution δ(u,v) . This distribution is the joint distribution δu and δv , both defined on Ω.
(The definition of δx as in Definition 2.) δu P is the uth row of P , namely, P (u, ·). Similarly,
δv P will be the vth row of P , namely, P (v, ·), and δ(u,v) Q will be the (u, v)th row of Q, that
is, Q((u, v), ·). As Q defines a strong Markovian coupling of M , we have that Q((u, v), ·)
will be the joint distribution of P (u, ·) and P (v, ·). From this condition, we get for any
x, u, v ∈ Ω:
X
Q((u, v), (x, y)) = P (u, x)
(7)
y∈Ω

Similarly, for any y, u, v ∈ Ω, we get
X
Q((u, v), (x, y)) = P (v, y)

(8)

x∈Ω

As (7) and (8) are precisely the conditions to be met by Q to be a faithful coupling, we
conclude that Q defines a faithful coupling of M .


4

Concluding remarks

We have seen that it is sufficient for a Markovian coupling to have the faithfulness property
in order to be turned to a sticky coupling. Is the faithfulness property also a necessary
property? It may be that there is a Markovian coupling of a Markov chain M which evolves
two copies of the chain correctly for a pair of initial distributions µ, ν of M , using a joint
distribution of the pair, and satisfies the condition in the statement of Proposition 3, but it
either does not work for some other joint distribution of the same pair µ and ν, or, does not
satisfy the condition for some other pair of initial distributions of M . Such a Markovian
coupling can be turned into a sticky coupling for the µ, ν pair, but will not be strongly
Markovian, and hence will not be a faithful coupling of M . One feels that even if such
an example exists, it is unlikely to be a natural example. Faithfulness appears to be the
only natural strengthening of the Markovian coupling notion that ensures that the sticking
operation will work.

References
[HM17] Hirscher, Timo and Anders Martinsson, Segregating Markov chains, manuscript,
arXiv:1510.036661v2 [math.PR], 2017.
[MU05] Mitzenmacher, Michael and Eli Upfal, Probability and Computing: Randomized
Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
[No97] Norris, J.R., Markov Chains, Cambridge University Press, 1997. Paperbackk edition
1998, 15th printing 2009.
8

[LPW09] Levin, David A., Yuval Peres and Elizabeth L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2009.
[Ro97] Rosenthal, Jeffrey S., Faithful Couplings of Markov Chains: Now Equals Forever,
Advances in Applied Mathematics, Vol. 18, pp. 372–381, 1997.

9

