Metropolis–Hastings transition kernel couplings

John O'LearyDepartment of Statistics, Harvard University, Cambridge, USA. Email<EMAIL_ADDRESS>Guanyang WangDepartment of Statistics, Rutgers University, New Brunswick,  USA. Email<EMAIL_ADDRESS>
Couplings play a central role in the analysis of Markov chain convergence and in the construction of
new Markov chain Monte Carlo estimators, diagnostics, and variance reduction techniques. Tight
bounds and efficient methods require an appropriate choice of coupling, which can be hard to find
when the set of possible couplings is intractable. To address this challenge for the
Metropolis–Hastings (MH) family of algorithms, we establish a simple characterization of the set of
all MH transition kernel couplings. We then extend this result to describe the set of maximal
couplings of the MH kernel, resolving an open question of O'Leary et al., 2021. We conclude with a
series of examples to build intuition. Our results represent an advance in understanding the MH
kernel and a step forward for coupling this popular class of algorithms.

§ INTRODUCTION

From early results on Markov chain ergodicity [Doeblin, 1938, Harris, 1955] to the
present day, couplings have played an important role in the analysis of convergence to stationarity.
In recent years couplings have also gained prominence as a basis for sampling
[Propp and Wilson, 1996, Fill, 1997, Neal, 1999, Flegal and Herbei, 2012], convergence
diagnosis [Johnson, 1996, Johnson, 1998, Biswas et al., 2019], variance reduction
[Neal and Pinto, 2001, Goodman and Lin, 2009, Piponi et al., 2020], and unbiased estimation
[Glynn and Rhee, 2014, Jacob et al., 2020, Heng and Jacob, 2019, Middleton et al., 2019, Middleton et al., 2020]. Across these
applications, couplings that deliver smaller meeting times are associated with better results.

Given a pair of Markov chains, the distribution of meeting times that a coupling can produce is
constrained by the total variation distance between the marginal distributions of the chains at each
iteration [Aldous, 1983, Lindvall, 1992]. Couplings that achieve the fastest meeting
times allowed by this bound are said to be efficient or maximal and exist in some generality
[Griffeath, 1975, Pitman, 1976, Goldstein, 1979]. Unfortunately these couplings
are rarely Markovian, while this is a requirement in many of the applications above. Efficient
Markovian couplings are known to exist – or not to exist – in special cases, but they remain
elusive for discrete-time MCMC algorithms [Burdzy and Kendall, 2000, Connor and Jacka, 2008, Kuwada, 2009, Hsu and Sturm, 2013, Kendall, 2015, Böttcher, 2017, Banerjee and Kendall, 2017]. For techniques like the Metropolis–Hastings (MH) algorithm
[Metropolis et al., 1953, Hastings, 1970], it is difficult to even characterize the set of possible
Markovian couplings, much less to differentiate among them by their implications for meeting times.

In this paper, we consider transition kernel couplings for the MH family of algorithms. These
couplings depend only on the current state of each chain and form a natural starting point for
inquiry into more general Markovian couplings. We fully characterize the set of kernel couplings for
such chains and prove that every such coupling can be expressed as a coupled proposal step followed
by a coupled acceptance step. This two-step representation is easy to implement computationally and
amenable to theoretical analysis, following e.g. Bou-Rabee et al., 2020. It should clarify the task
of coupling design for applied work and support the search for more efficient couplings for this
important class of algorithms.

So far, two approaches to coupling the MH kernel appear in the literature. In one method a coupling
is defined directly in terms of the probability density or mass function of the marginal transition
kernel  [Rosenthal, 1996, Rosenthal, 2002, Qin and Hobert, 2021, O'Leary et al., 2021].
This approach recalls the $\gamma$-coupling of <cit.> and relies on
few properties of the underlying transition kernel. The other method is to define one coupling at
the MH proposal step followed by a second coupling at the acceptance step, subject to certain
conditions [Johnson, 1998, Bou-Rabee et al., 2020, Jacob et al., 2020]. It has been unclear if one
strategy is preferable to the other, or if there exist kernel couplings beyond the scope of either
approach. In this paper we resolve this question, showing that every MH transition kernel coupling
has a two-step representation.

With these results in hand, we turn to the maximal couplings of the MH transition kernel, which are
sometimes called greedy couplings [Aldous and Fill, 1995, Hayes and Sinclair, 2005], one-step maximal
couplings [Reutter and Johnson, 1995, Hayes and Vigoda, 2003, Kartashov and Golomozyi, 2013], or step-by-step maximal
couplings [Pillai and Smith, 2019] of the associated Markov chains. These couplings do not usually
achieve the fastest meeting times allowed by the coupling inequality, but they provide a valuable
reference point for further analysis. Extending the results described above, we fully characterize such
couplings in terms of the properties of the associated proposal and acceptance couplings. We also
resolve an open question of O'Leary et al., 2021 on the structure of maximal transition kernel
couplings and their relationship with maximal couplings of the proposal distributions.

We note that all of our results hold for simple MH algorithms as well as refinements such as
Hamiltonian Monte Carlo [Duane et al., 1987, Neal, 1993, Neal, 2011], the Metropolis-adjusted Langevin
algorithm [Roberts and Tweedie, 1996], and particle MCMC [Andrieu et al., 2010].
They also hold on both continuous and discrete state spaces, `lazy' implementations where the
proposal distribution is not absolutely continuous with respect to the base measure, and methods
like Barker's algorithm [Barker, 1965] where the acceptance rate function differs from the usual
MH form. Thus, our characterization of kernel couplings and maximal kernel couplings applies to most
Markov chains which involve a sequence of proposal and acceptance steps.

The rest of this paper is organized as follows. In Section <ref>, we describe our
notation and setting, state our main result on transition kernel couplings, and set out a series of
definitions and lemmas to prove it. We introduce a running example on a two-point state space and
return to it to illustrate concepts and questions along the way. In Section <ref>, we
highlight a few important properties of maximal couplings, consider the relationship between maximal
proposal and transition kernel couplings, and prove our main result on the structure of maximal
couplings of the MH transition kernel. In Section <ref>, we analyze the kernel couplings
of several widely used MH algorithms such as the random-walk Metropolis-Hastings algorithm and the
Metropolis-adjusted Langevin algorithm. Finally, in Section <ref> we discuss our
results, highlighting open questions and paths forward.

§ METROPOLIS–HASTINGS KERNEL COUPLINGS

In this section we show that every MH-like transition kernel coupling can be represented as a
proposal coupling followed by an acceptance indicator coupling (Theorem <ref>). After
establishing our setting and notation, we build up to this proof through several auxiliary results
(Lemmas <ref>-<ref>). The key step is Lemma <ref>,
in which we show how to map from an arbitrary coupling of MH-like transition kernels to a proposal
coupling and a structure we call a `coupled acceptance mechanism.' The representation of transition kernel
couplings in terms of coupled proposal and acceptance steps follows from this result.

§.§ Notation and setting

Let $(\calZ, \scrG)$ be any measurable space. We say $\Theta: \calZ \times \scrG \to [0, 1]$ is a
Markov kernel if $\Theta(z, \cdot)$ is a probability measure on $(\calZ, \scrG)$ for each $z \in
\calZ$ and if $\Theta(\cdot, A) : \calZ \to [0,1]$ is measurable for each $A \in \scrG$. We say that
$\Theta$ is a sub-probability kernel if it satisfies the same conditions but where $\Theta(z,\cdot)$ is
a sub-probability measure for each $z \in \calZ$ rather than a probability measure. Let $2^S$ denote
the power set of a set $S$, let $\Bern(\alpha)$ denote the Bernoulli distribution on $\{0,1\}$ with
$\P(\Bern(\alpha)=1) = \alpha$ for $\alpha \in [0,1]$, and let $a \wedge b := \min(a,b)$ for any
$a,b \in \R$.

Suppose that $(\calX, \scrF)$ is a Polish space with base measure $\lambda$. We take $\calX$ to be
our state space. Fix a Markov kernel $Q: \calX \times \scrF \to [0,1]$, which we call the proposal
kernel, and a function $a: \calX \times \calX \to [0,1]$, which we call the acceptance rate
function. To be an acceptance rate function, we require that $a(x,\cd)$ is $Q(x,\cd)$-measurable and
$a(x,x)=1$ for all $x \in \calX$. The second condition simplifies many proofs and involves no loss
of generality, as we discuss below. Given a current state $x \in \calX$ and a measurable set $A \in
\scrF$, we think of $Q(x, A)$ as the probability of proposing a move from $x$ to $x' \in A$ and
$a(x,x')$ as the probability of accepting this proposal. We call $B(x,x') := \Bern(a(x,x'))$ the
acceptance indicator distribution associated with the acceptance rate function $a$.

In this paper we consider transition kernels which generalize the Metropolis–Hastings algorithm
according to the following property:

(MH-like transition kernel)
We say a Markov kernel $P : \calX \times \scrF \to [0,1]$ is generated by $Q$ and $a$ if
for all $x \in \calX$, $x' \sim Q(x,\cdot)$ and $b_x \sim B(x,x') = \Bern(a(x,x'))$ imply $X := b_x
x' + (1 - b_x) x \sim P(x,\cdot)$. We say $P$ is generated by $Q$ and $B$ if $P$ is generated by $Q$
and $a$ and if $B$ is the acceptance indicator distribution associated with $a$. Finally, we say that a
Markov transition kernel $P$ is MH-like if there exists a Markov kernel $Q: \calX \times
\scrF \to [0,1]$ and an acceptance rate function $a: \calX \times \calX \to [0,1]$ such that $P$ is
generated by $Q$ and $a$.

Most MCMC algorithms that involve alternating proposal and acceptance steps are MH-like. The MH
case arises when we fix a target distribution $\pi \ll \lambda$, assume $Q(x, \cdot) \ll
\lambda$ for all $x \in \calX$, and set ${a(x,x') := 1 \wedge \frac{\pi(x') q(x',x)}{\pi(x) q(x,x')}
}$ with $\pi( \cd ) := \diff \pi / \diff \lambda$ and $q(x, \cd) := \diff Q(x,\cd) / \diff \lambda$.
Our analysis also holds for alternative forms of $a(x,x')$ and for proposal kernels which are not
absolutely continuous with respect to $\lambda$. The requirement that $a(x,x) = 1$ for all $x \in
\calX$ involves no loss of generality because any transition kernel $P$ that can be expressed in
terms of some $\tilde a$ without this property can also be expressed in terms of another acceptance
function $a$ which has it. Thus our analysis applies to continuous and discrete state
spaces, lazy algorithms in which $Q(x, \sx) > 0$, and the transition kernel of Barker's algorithm
[Barker, 1965]. We refer the reader to Andrieu et al., 2020 for a general framework for
understanding MH-like transition kernels.

Next, let $\mu$ and $\nu$ be any finite measures on $(\calX, \scrF)$. A measure
$\gamma$ on $(\calXp, \scrFp)$ is called a coupling of $\mu$ and $\nu$ if $\gamma(A \times \calX) =
\mu(A)$ and $\gamma(\calX \times A) = \nu(A)$ for all $A \in \scrF$. We write $\Gamma(\mu, \nu)$ for
the set of couplings of $\mu$ and $\nu$, sometimes called the Fréchet class of these measures
[Kendall, 2017]. When $\mu$ and $\nu$ are probability measures, the coupling inequality
states that ${\P(X = Y) \leq 1 - \lVert \mu - \nu \rVert_\TV}$ for $(X,Y) \sim \gamma \in
\Gamma(\mu, \nu)$. Here $\lVert \mu - \nu \rVert_\TV = \sup_{A \in \scrF} | \mu(A) - \nu(A) |$ is
the total variation distance. See e.g. <cit.> or <cit.> for a further discussion of this important inequality. A coupling $\gamma$ that
achieves the coupling inequality bound is said to be maximal, and we write $\Gmax(\mu, \nu)$ for the
set of these.

Suppose that $\Theta$ is a Markov kernel on $(\calZ,\scrG)$. We follow
<cit.> in calling $\bar \Theta : (\calZ \times \calZ) \times (\scrG
\otimes \scrG) \to [0,1]$ a kernel coupling based on $\Theta$ if $\bar \Theta$ is a Markov kernel on
$(\calZ \times \calZ, \scrG \otimes \scrG)$ and if $\bar \Theta((z_1,z_2),\cd) \in
\Gamma(\Theta(z_1,\cd),\Theta(z_2,\cd))$ for all $z_1,z_2 \in \calZ$. We write
$\Gamma(\Theta,\Theta)$ for the set of all such kernel couplings. Likewise we say that $\bar \Theta$
is a maximal kernel coupling if each $\bar \Theta((z_1,z_2), \cd)$ is a maximal coupling of
$\Theta(z_1,\cd)$ and $\Theta(z_2,\cd)$, and we write $\Gmax(\Theta, \Theta)$ for the set of these.
It is important to remember that a maximal kernel coupling $\bp \in \Gmax(P,P)$ does not usually
correspond to a maximal coupling of Markov chains in the sense of Aldous, 1983;
the former produces the highest probability of meeting at each individual step, while the latter
produces the smallest meeting times allowed by the coupling inequality.

Suppose that an MH-like kernel $P$ is generated by a proposal kernel $Q$ and an acceptance rate
function $a$. Then we call any $\bp \in \Gamma(P,P)$ a transition kernel coupling and any $\bq \in
\Gamma(Q,Q)$ a proposal kernel coupling. Let $\mathcal{B}$ be the power set of $\{0,1\}^2$. We call
$\bb: \calX^2 \times \calX^2 \times \mathcal{B} \to [0,1]$ an acceptance indicator coupling if
$\bb(\xy, \xyp, \cdot)$ is a measure on $\{0,1\}^2$ for all $x,y,x',y' \in \calX$ and if $\bb(\cdot,
\cdot, S): \calX^2 \times \calX^2 \to [0,1]$ is measurable for all $S \in \mathcal{B}$. Abusing
notation, we usually drop the third argument of $\bb$ and write $(b_x, b_y) \sim \bb(\xy,
\xyp)$ whenever a pair of random variables $(b_x, b_y) \in \{0,1\}^2$ follows the acceptance
indicator coupling $\bb$. Thus we say that a proposal coupling $\bq$ and an acceptance indicator
coupling $\bb$ generate a kernel coupling $\bp$ if for all $x,y \in \calX$, ${ \xyp \sim
\bq(\xy,\cdot) }$ and ${ (b_x, b_y) \sim \bb(\xy, \xyp) }$ imply that $ (X,Y) := (b_x x' + (1 - b_x) x,
b_y y' + (1 - b_y) y) \sim \bp(\xy, \cdot). $ The key challenges before us are to show that every
$\bp \in \Gamma(P,P)$ arises in this way and to determine conditions on $\bb$ such that pairs
$(X,Y)$ defined as above follow a kernel coupling $\bp \in \Gamma(P,P)$.

We now introduce a simple example that we will return to over the course of this section.

Let $\calX = \{1,2\}$ and $\scrF = 2^\calX$, and assume a current state pair of $\xy = (1,2)$.
For a finite state-space like this, it is convenient to represent kernels $\Theta : \calX \times \scrF \to [0,1]$ as
$\Theta(z, \cd) = \big( \Theta(z,\{1\}), \Theta(z,\{2\}) \big)$
and couplings $\bar \Theta: (\calXp) \times (\scrFp) \to [0,1]$
by a matrix like the following:

3.5pt $ \bar \Theta(\xy, \cd)  = $

r |c|c| l
1      Θ(, (1,1) )     Θ(, (2,1))

2     Θ(, (1,2) )     Θ(, (2,2))      ←y

1     2

The columns of this matrix represent the destination values for the $x$ chain (e.g. values of $X$
or $x'$) while the rows represent the equivalent for the $y$ chain. The small `$x$' and `$y$' serve
as a reminder of the current state pair.

For this example, we assume a uniform proposal distribution and a MH acceptance rate function $a$
based on a target distribution $\pi = (\sfrac{1}{3}, \sfrac{2}{3})$, so that
$a(1, \cd) = (1,1)$ and $a(2,\cd) = (\h, 1)$.
Together these imply a transition kernel $P$ with
$P(1,\cd) = (\h,\h)$ and $P(2,\cd) = (\sfrac{1}{4}, \sfrac{3}{4})$.
Simple algebra shows that any proposal and transition coupling based on the kernels above must take the following forms, for some
$\rho \in [0,\h]$ and $\lambda \in [0, \sfrac{1}{4}]$:

3.5pt $ \bq((1,2), \cd) = $

r |c|c| l
1      ρ    - ρ

2    -ρ    ρ     ←y

1     2

3pt $ \bp((1,2), \cd) = $

r |c|c| l
1      λ    14 -λ

2    - λ    λ+ 14      ←y

1     2

We return to this example to illustrate the concepts below.

§.§ Main result

Johnson, 1998 showed that one can start with a proposal coupling $\bq \in \Gamma(Q,Q)$
and construct an acceptance indicator coupling $\bb$ such that $\bq$ and $\bb$ generate a valid
transition kernel coupling $\bp \in \Gamma(P,P)$. There and in subsequent work such as
Jacob et al., 2020, $\bb$ is taken to be a coupling of $\Bern(a(x,x'))$ and $\Bern(a(y,y'))$, so that
proposals from $x$ to $x'$ and from $y$ to $y'$ are each accepted at the MH rate. O'Leary et al., 2021
used a conditional form of $\bb$ to produce a maximal transition kernel coupling $\bp$ from any
maximal proposal kernel coupling $\bq$. In this paper we have a more general goal, which is to
characterize the set of all possible transition kernel couplings $\Gamma(P,P)$ in terms of proposal and
acceptance indicator couplings. In particular, we prove the following result:

Let $P$ be the MH-like transition kernel on $(\calX, \scrF)$ generated by a
proposal kernel $Q$ and an acceptance rate function $a$. A joint kernel $\bp \in \Gamma(P,P)$ if
and only if it is generated by $\bq \in \Gamma(Q,Q)$ and an acceptance indicator coupling $\bb$
such that for any $x, y \in \calX$ and $\bxy \sim \bb(\xy,\xyp)$, we have

* $\P(b_x=1 \g x,y,x') = a(x,x')$ for $Q(x,\cdot)$-almost all $x'$, and

* $\P(b_y=1 \g x,y,y')= a(y,y')$ for $Q(y,\cdot)$-almost all $y'$.

This result shows that all MH-like transition kernel couplings $\bp$ are `natural' in the sense that
they arise from coupled proposals $\xyp \sim \bq(\xy, \cdot)$ that are accepted or rejected
according to coupled acceptance indicators $(b_x, b_y) \sim \bb(\xy, \xyp)$. The $\bb$
conditions say that from any starting point $\xy$, the $x'$ and $y'$ proposals are marginally
accepted at the rate given by $a$, potentially with complicated joint behavior. Theorem
<ref> also confirms that simple conditions on the joint proposal and acceptance steps are
enough to yield a kernel coupling $\bp$ in $\Gamma(P,P)$.

It is not hard to show that $\bp \in \Gamma(P,P)$ when $\bp$ is generated by a proposal
coupling $\bq$ and an acceptance indicator coupling $\bb$ with the properties given above. However,
the converse requires a detailed understanding of the structure of transition kernel couplings. One
challenge is as follows: a transition from a state pair $\xy$ to a measurable rectangle $A_x \times
A_y$ with $x \not \in A_x$ and $y \not \in A_y$ can only occur if points $x' \neq x$ and $y' \neq y$
are proposed and accepted. This makes it simple to work out the behavior of a hypothetical $\bq$ and
$\bb$ on these sets. However, transitions to sets like $A_x \times \sy, \sx \times A_y, \sas \sx
\times \sy$ can arise from the partial or full rejection of proposed moves to sets like $A_x \times
\calX$, $\calX \times A_y$, and $\calX \times \calX$. It is more challenging to associate these
transition probabilities with joint proposal and acceptance probabilities in a consistent way.

Nevertheless, we prove our Theorem <ref> by constructing a mapping from an arbitrary kernel
$\bp \in \Gamma(P,P)$ to a joint distribution $\bq$ on proposals $(x', y')$ and a coupling $\bb$ on
acceptance indicators $\bxy$, such these reproduce $\bp$ and agree with the original proposal kernel
$Q$ and acceptance rate function $a$. The first step of this procedure involves defining a
collection of joint measures $\Phi$ on $\xyp$ and $\bxy$ with certain adding-up properties. A
proposal coupling $\bq$ follows directly from $\Phi$, and a Radon–Nikodym argument shows that we
can also extract an acceptance indicator coupling $\bb$ with the desired properties.

§.§ Coupled acceptance mechanisms

To begin, we define a relationship that can exist between an MH-like transition kernel coupling $\bp$ and
an arbitrary proposal coupling $\bq$:

We say that a proposal coupling $\bq \in \Gamma(Q,Q)$ and a transition kernel coupling $\bp \in \Gamma(P,P)$ are
related by a coupled acceptance mechanism $\Phi = (\Phi_{11}, \Phi_{10},\Phi_{01}, \Phi_{00})$
if each $\Phi_{ij}(\xy, \cdot)$ is a sub-probability on $(\calXp, \scrFp)$,
and for all $x,y \in \calX$, $A_x, A_y \in \scrF$ we have

1.     (, ) =
(Φ_11+Φ_10+Φ_01+Φ_00) ( , )

2.      (, ) = Φ_11(, ) + Φ_10(, A_x ×) 1(y ∈A_y)

+ Φ_01(, ×A_y) 1(x ∈A_x)
+ Φ_00(, ×) 1(x ∈A_x) 1(y ∈A_y)

3.      Q(x,) = (Φ_11+Φ_10)(, ×)  and
Q(y, ) = (Φ_11+Φ_01)(, ×).

As we will see, the existence of a coupled acceptance mechanism $\Phi$ relating $\bq$ and $\bp$ is
equivalent to the existence of an acceptance indicator coupling $\bb$ such that $\bq$ and $\bb$
generate $\bp$. In Lemma <ref> we show that if $(X,Y) \sim \bp(\xy,
\cdot)$ is generated by $\xyp \sim \bq(\xy, \cdot)$ and $(b_x, b_y) \sim \bb(\xy, \xyp)$, then a
coupled acceptance mechanism $\Phi$ relating $\bq$ and $\bp$ exists and can be defined by
$\Phi_{ij}(\xy, \cd) := \P(\xyp \in \cd, b_x = i, b_y = j)$ for $i,j \in \{0,1\}$.
Conversely, in Lemma <ref>, we show that if a coupled acceptance mechanism $\Phi$
relates $\bq$ and $\bp$, then there exists an acceptance indicator coupling $\bb$ such that $\bq$
and $\bb$ generate $\bp$.

Thus Definition <ref> captures a set of relationships that must exist between a proposal coupling $\bq$
and a transition kernel coupling $\bp$ for the former to generate the latter. We think of $\Phi$ as
subdividing the probability in $\bq(\xy,\cd)$ into four acceptance scenarios, depending on whether one,
both, or neither proposal is accepted. See Figure <ref> for an illustration of this.
Condition 1 requires that the probability assigned to these scenarios must add up to $\bq$
on all measurable subsets of $\calXp$. Condition 2 says that the resulting distribution over transitions must agree
with $\bp$.
Condition 3 concerns proposals with $x' = x$ or $y'=y$, and says that $\Phi$ must agree with the
marginal assumption that such proposals are always accepted.

Schematic diagram of
a coupled acceptance mechanism $\Phi$
relating a proposal coupling $\bq$ and a transition kernel coupling $\bp$.
Here $(x,y)$ represents the current state and
$\axy$ is a measurable rectangle in $\calXp$.
$\bq(\xy, \axy)$ gives the probability of a proposal $\xyp \in \axy$. The coupled acceptance mechanism
$\Phi = (\Phi_{11},\Phi_{10}, \Phi_{01}, \Phi_{00})$ distributes this probability into contributions to the
probability $\bp(\xy, \cd)$ of a transition from $(x,y)$ to the sets $\axy$, $A_x \times \sy$, $\sx \times A_y$, and $\sx \times \sy$. The conditions of Definition <ref> ensure that $\Phi$ agrees with both $\bq$ and $\bp$.

The crux of Theorem <ref> is to prove that every coupling of MH-like transition kernels $\bp$ arises
from a proposal and acceptance coupling. Thus we begin by looking for coupled acceptance mechanisms $\Phi$
that distribute the probability $\bq(\xy, \axy)$ of a proposal from $\xy$ to $\xyp \in \axy$
into contributions to the probability of a transition from $\xy$ to
$\XY \in \axy$, $A_x \times \sy, \sx \times A_y$, and $\sx \times \sy$, in a consistent way.
The following result establishes the necessity of the conditions in Definition <ref> for this task.

Let $\bp \in \Gamma(P,P)$ be a coupling of MH-like transition kernels.
If a proposal coupling $\bq$ and an acceptance indicator coupling $\bb$ generate $\bp$,
then there exists a coupled acceptance mechanism $\Phi$
relating $\bq$ and $\bp$.

Fix $\xy$, let $(x', y') \sim \bq(\xy, \cdot)$, and let $(b_x, b_y) \sim \bb(\xy, \xyp)$.
For $A \in \scrFp$ and $i, j \in \{0,1\}$, define $\Phi_{ij}(\xy, A) := \P( \xyp \in A, b_x = i, b_y = j \mid x,y)$.
This $\Phi$ satisfies Condition 1, since $\bq(\xy, \axy) = \P(\xyp \in \axy \, | \, x,y)$.
It also satisfies Condition 2, since for all $A_x, A_y \in \scrF$ we have

(, ) = (X ∈A_x, Y ∈A_y |x,y)

= (x' ∈A_x, y' ∈A_y, b_x=1, b_y=1 |x,y)
+ (x' ∈A_x, y ∈A_y, b_x=1, b_y=0 |x,y)

+ (x ∈A_x, y' ∈A_y, b_x=0, b_y=1 |x,y)
+ (x ∈A_x, y ∈A_y, b_x=0, b_y=0 |x,y)

= Φ_11(, )
+ Φ_10(, A_x ×) 1(y ∈A_y)

+ Φ_01(, ×A_y) 1(x ∈A_x)
+ Φ_00(, ) 1(x ∈A_x) 1(y ∈A_y).

For Condition 3, we have

( Φ_11 + Φ_10)(, ×)    = (x' = x, b_x = 1) = a(x,x) Q(x, ) = Q(x,)

( Φ_11 + Φ_01)(, ×)    = (y' = y, b_y = 1) = a(y,y) Q(y, ) = Q(y,).

Thus $\Phi$ is a coupled acceptance mechanism relating $\bq$ and $\bp$.

The $\bp$ condition of Definition <ref> takes a more intuitive (if less compact) form when we express it in terms of measurable sets $A_x, A_y \in \scrF$ where $x \not \in A_x$ and $y \not \in A_y$:

Let $\bp \in \Gamma(P,P)$ and suppose $\Phi = (\Phi_{11},\Phi_{10}, \Phi_{01}, \Phi_{00})$ are a collection of measures on $(\calXp, \scrFp)$.
Then Condition 2 of Definition <ref> holds if and only if for all $A_x, A_y \in \scrF$ with $x \not \in A_x$ and $y \not \in A_y$, we have

1.      (, ) = Φ_11(, )

2.      (, A_x ×) = Φ_11(, A_x ×) + Φ_10(, A_x ×)

3.      (, ×A_y) = Φ_11(, ×A_y) + Φ_01(, ×A_y)

4.      (, ×) = Φ_11(, ×) + Φ_10(, ×)

+ Φ_01(, ×) + Φ_00(, ×).

The conditions above follow from Condition 2 of Definition <ref> by evaluating that condition at $\sx, A_x \sm \sx$ and $\sy, A_y \sm \sy$.
For the converse, for any $A_x, A_y \in \scrF$ we have

(, )

= (, ×)
+ (, ×) 1(y ∈A_y)

+ (, ×) 1(x ∈A_x)
+ (, ×) 1(x ∈A_x) 1(y ∈A_y).

Replacing these terms with Conditions 1-4 above yields Condition 2 of Definition <ref>.

Condition 1 of Lemma <ref> corresponds to the intuition that the only way to transition from $\xy$ to a point $\XY \in \axy$ with $x \not \in A_x$ and $y \not \in A_y$ is to propose and accept $\xyp = \XY$. Similarly, Condition 2 says that the probability of transitioning to a point $\XY \in A_x \times \sy$ must come from the combined probability of accepting a proposal to such a point
or by proposing a move $\xyp \in A_x \times \calX$,
with $x'$ accepted and $y'$ rejected. The other two conditions follow a similar intuition.

Definition <ref> raises two questions.
First, we may ask if Condition 3 is actually independent of Conditions 1 and 2.
Second, we may ask whether a given $\bp \in \Gamma(P,P)$ can be related to more than one $\bq \in \Gamma(Q,Q)$ by coupled acceptance mechanisms. The next example answers both of these questions.

We return to the setup of Example <ref>, in which $\calX = \{1,2\}, \scrF = 2^\calX, \xy = (1,2)$, $Q(1, \cd) = Q(2, \cd) = (\h,\h)$, $P(1,\cd) = (\h,\h)$, and $P(2,\cd) = (\sfrac{1}{4}, \sfrac{3}{4})$. Suppose that we have the following proposal and transition kernel couplings:

3pt $ \bq((1,2), \cd) = $

r |c|c| l
1      14     14

2    14     14      ←y

1     2

3pt $ \bp((1,2), \cd) = $

r |c|c| l
1      0     14

2        14      ←y

1     2

Using Lemma <ref>, the first two conditions of Definition <ref> imply that any coupled acceptance mechanism $\Phi$ relating $\bq$ and $\bp$ must take the following form:

3pt $ \Phi_{11}((1,2), \cd) = $

r |c|c|
1       0     14

2     a     b

1     2

3pt $ \Phi_{10}((1,2), \cd) = $

r |c|c|
1      d     0

2     c     1/4	- b

1     2

3pt $ \Phi_{01}((1,2), \cd) = $

r |c|c|
1      0     0

2     e     0

1     2

3pt $ \Phi_{00}((1,2), \cd) = $

r |c|c|
1      14-d     0

2     14-a-c-e     0

1     2

Thus $(\Phi_{11} + \Phi_{10})(\xy, \sx \times \calX) = a + c + d$,
and  $(\Phi_{11} + \Phi_{01})(\xy, \calX \times \sy) = a + b + e$.
Note however that $a + c + d = Q(x, \sx) = \h$
and $a + b + e = Q(y, \sy) = \h$ do not automatically hold without imposing the third condition of Definition <ref>.
Also observe that even with that condition, any choice of $a,b,c$ with $0 \leq c \leq b \leq \sfrac{1}{4}$ and $0 \leq a \leq \sfrac{1}{4} - b \vee c$ will produce a valid $\Phi$ relating $\bq$ and $\bp$. Thus we see that coupled acceptance mechanisms do not have to be unique.

§.§ Existence of a coupled acceptance mechanism

To prove Theorem <ref> we must show that any MH-like transition kernel coupling $\bp \in
\Gamma(P,P)$ arises from a proposal coupling $\bq \in \Gamma(Q,Q)$ and an acceptance indicator
coupling $\bb$ with certain properties. In this subsection we
show that for any $\bp \in \Gamma(P,P)$, there exists a kernel coupling $\bq \in \Gamma(Q,Q)$ and a
coupled acceptance mechanism $\Phi$ relating $\bq$ and $\bp$. In the next subsection we show that we
can transform this $\Phi$ into an acceptance coupling $\bb$. Finally, we use these results to prove
our main theorem.
Along the way we use the following objects, which are defined for $x \in \calX$ and $A \in \scrF$:

α_0(x, A)     := Q(x, A ∖) - P(x, A ∖)
α_1(x, A)        := Q(x, A ∩) + P(x, A ∖)

β(x)     :=
Q(x,)/P(x,)     if  P(x,) > 0

1     otherwise

μ(x,A)        :=
α_0(x,A)/α_0(x,)     if  α_0(x,) > 0

1(x ∈A)     otherwise.

Note that these definitions depend only on the marginal kernels $Q$ and $P$. These objects have a simple
interpretation in terms of the underlying chains:

Let $x \in \calX$, $A \in \scrF$, $x' \sim Q(x, \cdot)$, $b_x \sim B(x,x') = \Bern(a(x,x'))$,
and so $X := b_x x' + (1-b_x) x \sim P(x, \cdot)$. Then $\alpha_i(x, A) = \P(x' \in A, b_x=i \g x)$ for
$i \in \zo$; $\beta(x) = \P(b_x = 1 \g x, X=x)$ whenever $P(x, \sx) > 0$; and $\mu(x, A) = \P(x' \in
A \g b_x = 0, x)$ whenever $\alpha_0(x,\calX)>0$.

We have assumed that the acceptance rate function $a$ has $a(x,x)=1$ for all $x$.
Thus $\P(x' \in A \cap \sx, b_x = 0 \g x) = 0$ and so

= Q(x, A ) - P(x, A )
= (x' ∈A x) - (X ∈A x)

= (x' ∈A x ) - (x' ∈A, b_x=1 x)
= (x' ∈A, b_x=0 x).

= Q(x, A ∩) + P(x, A )
= (x' ∈A ∩x ) + (X ∈A x)

= (x' ∈A ∩, b_x=1 x ) + (x' ∈A , b_x=1 x)
= (x' ∈A, b_x=1 x ).

Suppose $P(x, \sx) > 0$. Then since $Q(x, \sx) = \alpha_x(x,\sx)$, we have

= Q(x, )/P(x, )
= (b_x = 1, x'=x x ) /(X = x x)
= (b_x = 1, X=x x) /(X = x x)
= (b_x = 1 x, X=x).

Finally, say $\alpha_0(x, \calX) = \P(b_x = 0 \g x) > 0$. Then

= α_0(x, A)/α_0(x, )
=  (x' ∈A, b_x = 0 x)/ (b_x = 0 x) = (x' ∈A b_x = 0, x).

Thus each of $\alpha_0, \alpha_1, \beta, \sas \mu$ has a simple interpretation in terms of the joint probability of $x'$ and $b_x$ induced by $Q$ and $B$.

We will also need the following properties:

Let $x \in \calX$ and $A \in \scrF$.
Then $\beta(x) \in [0,1]$,
$\mu(x, \cdot)$ is a measure on $(\calX, \scrF)$,
$Q(x, A \cap \sx) = P(x, A \cap \sx) \beta(x)$, and
$Q(x, A) = \alpha_1(x, A) + \mu(x, A) \alpha_0(x, \calX)$.

When $P(x, \sx) > 0$, $\beta(x) \in [0,1]$ by Lemma <ref>. Otherwise $\beta(x) = 1$,
so in either case $\beta(x) \in [0,1]$. Also by Lemma <ref>, we observe that $\mu(x, \cdot)$
is the indicator of a measurable set or a well-defined conditional probability, and so in either
case it defines a measure on $(\calX, \scrF)$.

For the first $Q$ equality, if $x \not \in A$, then the $Q(x, A \cap \sx) = 0 = P(x, A \cap \sx)
\beta(x)$. If $x \in A$ then we want to show $Q(x, \sx) = P(x, \sx)
\beta(x)$. This holds by the definition of $\beta(x)$ when $P(x, \sx) > 0$.
Since $a(x,x) = 1$ for all $x \in \calX$, $P(x, \sx) = 0$ implies $Q(x, \sx) = 0$, so
the result also holds in this case.

The second $Q$ equality holds by the definitions of $\mu, \alpha_0, \sas \alpha_1$ when $\alpha_0(x,
\calX) > 0$. This leaves the $\alpha_0(x, \calX)=0$ case. In general, $\alpha_0(x, \calX) =
Q(x, \sx^c) - P(x, \sx^c) = \int (1 - a(x,x')) Q(x, \diff x')$, since $a(x,x)=1$ for all $x
\in \calX$. Thus $\alpha_0(x, \calX)=0$ implies $a(x,x')=1$ for $Q(x, \cdot)$-almost all $x'$, and
so $\alpha_1(x,A) = Q(x, A \cap \sx) + \int_{A \setminus \sx} a(x,x') Q(x, \diff x') = Q(x, A)$.
Thus the second equality also holds when $\alpha_0(x, \calX) = 0$.

We now describe the main lemma used in our proof of Theorem <ref>.

For any coupling $\bp \in \Gamma(P,P)$ of MH-like transition kernels, there exists a proposal coupling $\bq \in \Gamma(Q,Q)$ and a coupled acceptance mechanism $\Phi$ relating $\bq$ and $\bp$.

The proof proceeds in three steps. First we use $\bp$ to define a collection of sub-probability kernels $\Phi =
(\Phi_{11}, \Phi_{10}, \Phi_{01}, \Phi_{00})$. Then we use $\Phi$ to define a
kernel coupling $\bq \in \Gamma(Q,Q)$. Finally we show that $\Phi$ satisfies the
conditions of Definition <ref>, making it a coupled acceptance mechanism relating $\bq$ and

We begin with an explicit formula for $\Phi_{11}$ in terms of $\bp$. For $x, y \in \calX$ and
$A \in \scrFp$, let

Φ_11(, A)
:=      ( , A ∩(^c ×^c) )
+ ( , A ∩(×^c) )   β(x)

+     ( , A ∩(^c ×) )   β(y)
+ ( , A ∩(×) )  β(x)   β(y).

Here $\Phi_{11}$ is a sub-probability kernel, since $\beta(\cdot) \in [0,1]$ by
Lemma <ref>. We define the other three components of $\Phi$ by a product measure
construction. For $x,y \in \calX$ and $A_x, A_y \in \scrF$, let

Ψ_10(, A_x) := α_1(x,A_x) - Φ_11(, A_x ×)

Ψ_01(, A_y) := α_1(y,A_y) - Φ_11(, ×A_y).

We claim that $\Psi_{10}(\xy,\cd)$ and $\Psi_{01}(\xy,\cd)$ are sub-probabilities on $(\calX,
\scrF)$. Indeed, by Lemma <ref> and the fact that $\bp \in \Gamma(P,P)$, we have

α_1(x, A_x)
= P(x, A_x ) + P(x, A_x ∩) β(x)

= ((x,y), ×^c)
+ ((x,y), ×^c) β(x)

+ ((x,y), ×) +
((x,y), ×) β(x).

Plugging $A_x \times \calX$ into the definition of $\Phi_{11}$ yields analogous terms:

Φ_11((x,y), A_x ×)      =
((x,y), ×^c) +
((x,y), ×^c) β(x)

+((x,y), ×)β(y)  +
((x,y), ×) β(x)β(y).

Thus $\Psi_{10}(\xy, A_x) = \big( \bp( \xy, \axm \times \sy) + \bp( \xy, \axs \times \sy ) \beta(x)
\big) (1-\beta(y))$, and similarly for $\Psi_{01}(\xy, A_y)$. It follows that $\Psi_{10}(\xy,
\cdot)$ and $\Psi_{01}(\xy, \cdot)$ are sub-probabilities. We also set $\Psi_{00}(x,y) := 1 -
\alpha_1(x,\calX) - \alpha_1(y, \calX) + \Phi_{11} (\xy, \calXp)$. Algebraic manipulations
show that $\Psi_{00}(x,y) =  \bp(\xy, \sx \times \sy) (1 - \beta(x)) (1-\beta(y)) \in [0,1]$.

With these results in hand, we define $\Phi_{10}(\xy, \cdot), \Phi_{01}(\xy, \cdot), \sas
\Phi_{00}(\xy, \cdot)$ as the product measures extending the following equalities to $(\calX \times
\calX, \scrF \otimes \scrF)$:

Φ_10(, A_x ×A_y) = Ψ_10(,  A_x) μ(y, A_y)

Φ_01(, A_x ×A_y) = μ(x, A_x) Ψ_01(, A_y)

Φ_00(, ) = μ(x, A_x) μ(y, A_y) Ψ_00(x,y).

Thus each component of $\Phi = (\Phi_{11}, \Phi_{10}, \Phi_{01}, \Phi_{00})$ is a sub-probability kernel.

Next, we define $\bq(\xy, A) := (\Phi_{11}+\Phi_{10}+\Phi_{01}+\Phi_{00})\big(\xy, A \big)$ for all $A
\in \scrFp$. To see that $\bq \in \Gamma(Q,Q)$, observe that for any $x,y \in \calX$ and $A_x \in \scrF$ we have

(, A_x ×)
= (Φ_11+Φ_10+Φ_01+Φ_00)(, A_x ×)

= (Φ_11 + Φ_10)(A_x ×) + μ(x, A_x) (Φ_01 + Φ_00)()

= α_1(x,A_x) + μ(x, A_x) α_0(x, ) = Q(x, A_x).

The second-to-last equality follows from the definitions of $\Psi_{10}$, $\Psi_{01}$ and
$\Psi_{00}$, while the last equality is due to Lemma <ref>. A similar argument shows $\bq(\xy,
\calX \times A_y) = Q(y, A_y)$ for any $x,y \in \calX$ and $A_y \in \scrF$. Thus $\bq \in
\Gamma(Q,Q)$.

Finally, we show that $\Phi$ satisfies the conditions of Definition <ref>. The $\bq$
condition is automatically satisfied given the definitions above. For the $\bp$ condition, we check
the four cases described in Lemma <ref>. For the $\axym$ case, we have

Φ_11(, ) = (, ).

For the $\axm \times \sy$ case,

Φ_11(, ×) + Φ_10(, ×)

= P(x, A_x ) - (, ×^c)
= (, ×).

We use the definitions of $\Phi_{11}$ and $\Phi_{10}$ and the fact that $\alpha_1(x, A \sm \sx) = P(x, A \sm \sx)$
for the first equality. The second equality follows from the definition of $\bp \in \Gamma(P,P)$.
By a similar argument, we have
$\Phi_{11}(\xy, \sx \times \aym) + \Phi_{10}(\xy, \calX \times \aym) = \bp(\xy, \sx \times \aym)$.
For the $\sx \times \sy$ case we have

Φ_11(, ×) + Φ_10(, ×) + Φ_01(, ×) + Φ_00(, )

= Φ_11(, ×) + Ψ_10(, ) + Ψ_01(, ) + Ψ_00(x,y)

= 1 + Φ_11(, ^c ×^c) - α_1(x, ^c) - α_1(y, ^c)
= (, ×).

For the last condition of Definition <ref>, note that by the definitions of $\Phi$ and
$\alpha_1$ we have

(Φ_11 + Φ_10) (, ×)     = α_1(x, ) = Q(x, )

(Φ_11 + Φ_01) (, ×)     = α_1(y, ) = Q(y ,).

We conclude that $\Phi$ is a coupled acceptance mechanism relating $\bp$ and $\bq$.

We return to the setup of Example <ref> to construct $\Phi$ and $\bq$ as in the proof of Lemma <ref>.
We continue to assume
$\calX = \{1,2\}, \scrF = 2^\calX, Q(1, \cd) = Q(2, \cd) = (\h,\h)$,
$a(1,\cd) = (1,1)$, $a(2,\cd) = (\h,1)$,
$P(1,\cd) = (\h,\h)$, and $P(2,\cd) = (\sfrac{1}{4}, \sfrac{3}{4})$.
Thus  $\alpha_0$, $\alpha_1$, $\beta$, $\mu$ work out to

α_0(1,) = (0,0)            α_1(1,) = (,)            μ(1,) = (1,0)

α_0(2,) = (14,0)            α_1(2,) = (14,)            μ(2,) = (1,0)

β() = (1, 23).

As in Example <ref>, we consider a kernel coupling $\bp$ with the following transition probabilities:

3pt $ \bp((1,2), \cd) = $

r |c|c| l
1      0     14

2        14      ←y

1     2

Following the construction in the proof of Lemma <ref> and the values of $\alpha_0, \alpha_1, \mu, \sas \beta$ given above, we have

10pt $ \Phi_{11}((1,2), \cd) = $
r |c|c|
1      0     14

2    13     16

1     2

10pt $ \Phi_{10}((1,2), \cd) = $
r |c|c|
1      16     112

2    0    0

1     2

Similar calculations show that both $\Phi_{01}((1,2), \cd)$ and $\Phi_{00}((1,2),\cd)$ consist entirely of zeros.
Finally, since $\bq(\xy, \cd) = (\Phi_{11}+\Phi_{10}+\Phi_{01}+\Phi_{00})(\xy,\cd)$, we have

3pt $ \bq((1,2), \cd) = $

r |c|c| l
1      16     13

2    13    16     ←y

1     2

We see that this proposal coupling has the marginal distributions $Q(1, \cd) = Q(2, \cd) = (\h,\h)$.

§.§ Existence of an acceptance indicator coupling

Next, we show that if we have a coupled acceptance mechanism $\Phi$ relating $\bq$ and $\bp$, then there exists an acceptance indicator coupling $\bb$ such that $\bq$ and $\bb$ generate $\bp$. In the following, we write $\Delta^{n-1}$ for the set of multinomial distributions on a set with $n$ elements.

Suppose $\bp \in \Gamma(P,P)$, $\bq \in \Gamma(Q,Q)$, and $\Phi$ is a coupled acceptance mechanism relating $\bp$ and $\bq$.
Then there exist $\bq(\xy,\cdot)$-measurable functions
$\phi_{ij}(\xy, \cdot)$ for $i,j \in \{0,1\}$
such that $\phi = (\phi_{11}, \phi_{10}, \phi_{01}, \phi_{00})\big(\xy, \xyp \big) \in \Delta^3$
for $\bq(\xy,\cdot)$-almost all $\xyp$.
If we define $\bb$ such that $\P ( b_x = i, b_y = j \g x,y,x',y') = \phi_{ij}\big( \xy, \xyp \big)$
when $(b_x, b_y) \sim \bb(\xy, \xyp)$,
then $\bq$ and $\bb$ generate $\bp$.

For each $i,j \in \{0,1\}$, the $\bq$ condition in Definition <ref> implies $\Phi_{ij}(\xy, \cdot) \ll \bq(\xy, \cdot)$.
Thus we can form the Radon–Nikodym derivative $\phi_{ij}(\xy, \cdot) := \mathrm{d} \Phi_{ij}(\xy, \cdot) / \mathrm{d} \bq(\xy, \cdot)$.
The Radon–Nikodym derivative is linear and $\mathrm{d} \bq (\xy, \cdot) / \mathrm{d} \bq(\xy, \cdot) = 1$, so
for $\bq(\xy, \cdot)$-almost all $\xyp$ we have
$\sum_{i,j \in \{0,1\} } \phi_{ij}(\xy,\xyp) = 1$.
Since $\phi_{ij} \geq 0$,
this implies that each $\phi_{ij} \leq 1$.
Thus $\phi(\xy, \xyp) \in \Delta^3$ for $\bq(\xy, \cdot)$-almost all $\xyp$.

For points $\xyp$ where the above holds, let $\bxy \sim \bb(\xy, \xyp)$ be the multinomial random variable on $\{0,1\}^2$ with
$\P\big( b_x = i, b_y = j \g x,y,x',y' \big) = \phi_{ij}\big( \xy, \xyp \big)$
for $i,j \in \{0,1\}$.
Suppose that $\xyp \sim \bq(\xy, \cdot)$ and let $(X,Y) := (x' b_x + x (1-b_x), y' b_y + y (1-b_y))$.
Then for any $A_y, A_y \in \scrF$ we have

((X,Y) ∈, b_x=1, b_y=1 x,y)	   = Φ_11(, )

((X,Y) ∈, b_x=1, b_y=0 x,y)    = Φ_10(, A_x ×) 1(y ∈A_y)

((X,Y) ∈, b_x=0, b_y=1 x,y)    = Φ_01(, ×A_y) 1(x ∈A_x)

((X,Y) ∈, b_x=0, b_y= 0 x,y)    = Φ_00(, ×) 1(x ∈A_x)1(y ∈A_y).

It follows from these expressions and the definition of a coupled acceptance mechanism $\Phi$ that
$\P((X,Y) \in \axy) = \bp(\xy, \axy)$ on all measurable rectangles $\axy$, and hence that
$\P((X,Y) \in A) = \bp(\xy, A)$ for all $A \in \scrFp$. We conclude that $\bq$ and $\bb$ generate $\bp$.

Let $\Phi$ be a coupled acceptance mechanism relating $\bp \in \Gamma(P,P)$ and $\bq \in \Gamma(Q,Q)$,
and define $\phi$ and $\bb$ as in the proof of Lemma <ref>.
If $\bxy \sim \bb(\xy, \xyp)$, then

* $\P(b_x=1 \g x,y,x') = a(x,x')$ for $Q(x,\cdot)$-almost all $x'$, and

* $\P(b_y=1 \g x,y,y')= a(y,y')$ for $Q(y,\cdot)$-almost all $y'$.

Let $a_x :=  \phi_{11} + \phi_{10}$.
$\P(b_x = 1 \g x, y, x') = \E_{\bar Q((x,y),\cdot)}[a_x(\xy, \xyp) \g x, y, x']$,
and $a_x(\xy, \cdot)$ is $\bq(\xy, \cdot)$-measurable.
For all $A \in \scrF$, we have

∫1(x' ∈A) (b_x = 1 x, y, x') (, )

= ∫1(x' ∈A) a_x(, ) (, )
= (Φ_11+Φ_10)(, A ×)

= Q(x, ∩A) + P(x, A ∖)
= ∫_A a(x,x') Q(x, x')

= ∫1(x' ∈A) a(x,x') (, ).

The first equality follows from the defining property of conditional expectations.
Definition <ref>, Condition 2 implies $(\Phi_{11}+\Phi_{10})(\xy, (A \sm \sx) \times \calX) = \bp(\xy, (A \sm \sx) \times \calX)$, while
Condition 3 implies $(\Phi_{11}+\Phi_{10})(\xy, (A \cap \sx) \times \calX) = Q(x, A \cap \sx)$.
These combine to yield the third equality, above.

By the essential uniqueness of the Radon–Nikodym derivative,
$\P(b_x = 1 \g x, y, x') = a(x, x')$
for all $x'$ in a measurable set $\tilde A \in \scrF$
with $\bq(\xy, \tilde A \times \calX) = Q(x, \tilde A) = 1$.
Thus this equality holds for $Q(x,\cdot)$-almost all $x' \in \calX$.
A similar argument shows that $\P(b_y=1 \g x, y, y') = a(y,y')$ for $Q(y,\cdot)$-almost all $y' \in \calX$.

§.§ Main result

Having established the lemmas above, we can now prove our main result.

For the `only if' case, assume $\bq \in \Gamma(Q,Q)$ and $\bxy \sim \bb(\xy,\xyp)$, an acceptance
indicator coupling with $\P(b_x=1 \g x,y,x') = a(x,x')$ for $Q(x,\cdot)$-almost all $x'$ and
$\P(b_y=1 \g x,y,y')= a(y,y')$ for $Q(y,\cdot)$-almost all $y'$. Let $\bp(\xy, \cdot)$ be the law of
$(X,Y) := (b_x x' + (1-b_x) x, b_y y' + (1 - b_y) y)$. Then for any $A \in \scrF$,

(, A ×)
= (X ∈A x,y) = (x' ∈A, b_x=1 x,y) + (x ∈A, b_x=0 x,y)

= ∫1(x' ∈A) a(x,x')  (, ) + 1(x ∈A) ∫(1-a(x,x'))  (, )

= ∫1(x' ∈A) a(x,x') Q(x, x') + 1(x ∈A) ∫(1-a(x,x')) Q(x, x')
= P(x, A).

A similar argument shows that $\bp(\xy, \calX \times A) = P(y, A)$ for any $A \in \scrF$. Thus $\bp
\in \Gamma(P,P)$.

For the `if' case, take any $\bp \in \Gamma(P,P)$. By Lemma <ref>, there exists a
proposal coupling $\bq \in \Gamma(Q,Q)$ and a coupled acceptance mechanism $\Phi$ relating $\bq$ and
$\bp$. Then by Lemma <ref>, there exists an acceptance indicator coupling $\bb$ such
that $\bq$ and $\bb$ generate $\bp$. Finally by Lemma <ref>, this $\bb$ will be
such that if $\bxy \sim \bb(\xy,\xyp)$, then $\P(b_x=1 \g x,y,x') = a(x,x')$ for $Q(x,\cdot)$-almost
all $x'$ and $\P(b_y=1 \g x,y,y')= a(y,y')$ for $Q(y,\cdot)$-almost all $y'$. Thus we conclude that
$\bp$ is generated by a proposal coupling $\bq$ and an acceptance indicator coupling $\bb$ with the
desired properties.

Returning once more to our running example,
we most recently showed that the transition kernel coupling $\bp$ was related to the proposal coupling $\bq$ by a coupled acceptance mechanism $\Phi$ with the following properties:

10pt $ \bp((1,2), \cd) = $
r |c|c|
1      0     14

2        14

1     2

10pt $ \bq((1,2), \cd) = $
r |c|c|
1      16     13

2    13    16

1     2

10pt $ \Phi_{11}((1,2), \cd) = $
r |c|c|
1      0     14

2    13     16

1     2

10pt $ \Phi_{10}((1,2), \cd) = $
r |c|c|
1      16     112

2    0    0

1     2

10pt $ \Phi_{01}((1,2), \cd) = \Phi_{00}((1,2), \cd) = $

r |c|c|
1      0     0

2    0    0

1     2

Applying the same construction used in the proof of Theorem <ref>, we find that $\bp((1,2),\cd)$ can be generated from $\bq((1,2),\cd)$ together with an acceptance indicator coupling $\bb$ such that if $\bxy \sim \bb(\xy, \cd)$, then

10pt $\P( b_x=b_y=1 \g x,y, \cd) = $
r |c|c|
1      0     3 4

2     1     1

1     2

10pt $\P( b_x=1, b_y=0 \g x,y, \cd) = $
r |c|c|
1      1     1 4

2      0     0

1     2

11pt $\P( b_x=0, b_y=1 \g x,y, \cd) = \P( b_x=b_y=0 \g x,y, \cd) = $

r |c|c|
1      0     0

2    0    0

1     2

We conclude that the given procedure indeed provides a method to find a proposal and acceptance coupling to reproduce the given MH transition coupling at the point $\xy = (1,2)$.

§ MAXIMAL KERNEL COUPLINGS

In an application of the results above, we now characterize the maximal couplings of MH-like
transition kernels. Given such a kernel $P$, the identification of couplings $\bp \in \Gamma(P,P)$
that induce rapid meeting between chains is a challenging but important question for theoretical
analysis and especially in applications, where couplings are often required to be Markovian. Maximal
couplings $\bp \in \Gmax(P,P)$ represent myopically optimal solutions to the problem of minimizing the
meeting time between chains, in that they achieve the largest possible one-step meeting probability
$\P(X=Y \g x, y)$ from each state pair $(x,y)$. A clear understanding of the structure of
$\Gmax(P,P)$ is valuable for designing practical couplings and provides a reference point in the
search for more efficient Markovian couplings of MH-like chains.

We write $\Delta := \{(z,z) : z \in \calX\}$ for the diagonal of $\calXp$, $\delta : \calX \to
\Delta$ for the map $z \mapsto (z,z)$, and $A_\Delta := \delta(A) = \{(z,z) : z \in A\}$. We have
assumed that $(\calX, \scrF)$ is a Polish space, so $\Delta \in \scrFp$ and $\delta$ is a measurable
function. As noted above, the coupling inequality states that if $\mu$ and $\nu$ are probability
measures on $(\calX, \scrF)$ and $\gamma \in \Gamma(\mu, \nu)$, then $\P_{\XY \sim \gamma}(X = Y)
\leq 1 - \lVert \mu - \nu \rVert_\TV$. A coupling that achieves this upper bound is said to be
maximal. In the next section we see that this is equivalent to a measure theoretical condition,
which we use in our characterization of maximal couplings of MH-like kernels.

§.§ The Hahn maximality condition

Given probability measures $\mu$ and $\nu$ on $(\calX, \scrF)$, the Hahn-Jordan theorem
<cit.> states that there exists a measurable set $S \in \scrF$ and
sub-probability measures $\mu^r$ and $\nu^r$ such that $\mu - \nu = \mu^r - \nu^r$ and $\mu^r(S^c) =
\nu^r(S) = 0$. The pair $(S,S^c)$ is called the Hahn decomposition for $\mu - \nu$, and it is
essentially unique in the sense that if $R \in \scrF$ is another set with $\mu^r(R^c) = \nu^r(R) =
0$, then $(\mu-\nu)(S \symdiff R) = 0$. Here $A \symdiff B = (A \sm B) \cup (B \sm A)$ denotes the
symmetric difference of measurable sets. The pair $(\mu^r, \nu^r)$ is called the Jordan
decomposition of $\mu - \nu$, and it is unique.

In the Jordan decomposition of $\mu - \nu$, $\mu^r$ and $\nu^r$ are called the upper and lower
variation of $\mu - \nu$, and $\mu \wedge \nu := \mu - \mu^r = \nu - \nu^r$ is called the meet or
infimum measure of $\mu$ and $\nu$. $\mu \wedge \nu$ is non-negative and has the defining property
that if $\eta$ is another measure on $(\calX, \scrF)$ with $\eta(A) \leq \mu(A) \wedge \nu(A)$ for
all $A \in \scrF$, then $\eta(A) \leq (\mu \wedge \nu)(A)$ for all $A \in \scrF$. Note that by the
definition of total variation, $\lVert \mu - \nu \rVert_\TV = \sup_{A \in \scrF}\lvert \mu(A) -
\nu(A) \rvert = \mu^r(\calX) = \nu^r(\calX) = 1 - (\mu \wedge \nu) (\calX)$. See e.g. <cit.> or <cit.> for more on the
lattice-theoretic properties of the set of measures on $(\calX, \scrF)$.

For any measure $\mu$ on $(\calX, \scrF)$ let $\delta_\star \mu$ be the pushforward of $\mu$ by the diagonal map $\delta$,
so that $\delta_\star \mu (A) = \mu (\delta^{-1} (A))$ for $A \in \scrFp$.
This makes $\delta_\star \mu$ a measure on $(\calXp, \scrFp)$, with
$\delta_\star \mu (A) = \delta_\star \mu (A \cap \Delta)$ for $A \in \scrFp$,
and $\delta_\star \mu (B_\Delta) = \mu (B)$ for any $B \in \scrF$.
With this notation, we have the following characterization of maximal couplings:

Let $\mu - \nu = \mu^r - \nu^r$ be the Jordan decomposition
of a pair of probability measures $\mu$ and $\nu$ on $(\calX, \scrF)$.
A coupling $\gamma \in \Gamma(\mu, \nu)$ is maximal if and only if there exists a
$\gamma^r  \in \Gamma(\mu^r, \nu^r )$
such that $\gamma(A) = \gamma^r(A) + \delta_\star \big( \mu \wedge \nu \big) (A)$ for all $A \in \scrFp$.

Note that we must have $\mu^r(\calX) = \nu^r(\calX)$ for $\Gamma(\mu^r,\nu^r)$ to be
nonempty. This follows from the Jordan decomposition, since $0 = (\mu - \nu)(\calX) = (\mu^r -
\nu^r)(\calX)$. We also have $\gamma^r(\Delta) = 0$, since

1 -‖μ- ν‖_    = γ(Δ)
= γ^r(Δ) + δ_⋆(μ∧ν)(Δ)

= γ^r(Δ) + (μ∧ν)()
= γ^r(Δ) + 1 -‖μ- ν‖_.

Finally, we observe that
Lemma <ref> implies the maximal coupling recognition result of <cit.>.
In particular, we have the following characterization of maximal couplings based on the Hahn

Let $\mu$ and $\nu$ be measures on $(\calX, \scrF$).
A coupling $\gamma \in \Gamma(\mu, \nu)$
is maximal if and only if there is an $S \in \scrF$ such that
$\gamma( (S^c \times \calX) \sm \Delta )$ $= \gamma( (\calX \times S) \sm \Delta ) = 0$.
Any $(S,S^c)$ with this property will be a Hahn decomposition for $\mu-\nu$.

Let $\mu - \nu = \mu^r - \nu^r$ be a Jordan decomposition, so that for some $S \in \scrF$ we have
$\mu^r(S^c) = \nu^r(S) = 0$.
If $\gamma \in \Gamma(\mu,\nu)$ is maximal, Lemma <ref> implies that
$\gamma(A) = \gamma^r(A) + \delta_\star(\mu \wedge \nu)(A)$ for all $A \in \scrFp$. Thus
$\gamma((S^c \times \calX) \sm \Delta) = \gamma^r(S^c \times \calX) = \mu^r(S^c) = 0$.
Similarly, $\gamma( (\calX \times S) \sm \Delta ) = 0$.

For the converse, let $\gamma \in \Gamma(\mu,\nu)$ and $\gamma( (S^c \times \calX) \sm \Delta ) = \gamma( (\calX \times S) \sm \Delta ) = 0$.
For any $B \in \scrF$,

μ(B)     = γ(B ×) = γ( (B ×) Δ) + γ(B_Δ)

ν(B)     = γ(×B) = γ( (×B) Δ) + γ(B_Δ).

By assumption, $S$ contains the support of $\gamma((\cd \times \calX) \sm \Delta)$
and $S^c$ contains the support of $\gamma((\calX \times \cd)\sm\Delta )$. Thus
$\mu(\cd) - \nu(\cd) = \gamma((\cd \times \calX) \sm \Delta) - \gamma((\calX \times \cd)\sm\Delta)$
is the Jordan decomposition of $\mu - \nu$ and $(S,S^c)$ is a Hahn decomposition.
The uniqueness of the Jordan decomposition implies
$\gamma((B \times \calX) \sm \Delta) = \mu^r(B)$ and
$\gamma((\calX \times B) \sm \Delta) = \nu^r(B)$, which in turn yields
$\gamma^r(\cd) := \gamma(\cd \sm \Delta) \in \Gamma(\mu^r, \nu^r)$.
We also have $(\mu \wedge \nu)(B) = \mu(B) - \mu^r(B) = \nu(B) - \nu^r(B)$ ,
so the above implies $\gamma(B_\Delta) = (\mu \wedge \nu)(B)$ for all $B \in \scrF$.
Thus we conclude that for any $A \in \scrFp$,
$\gamma(A) = \gamma(A \sm \Delta) + \gamma(A \cap \Delta)= \gamma^r(A) + \delta_\star(\mu \wedge \nu)(A)$.

We will use the result above to establish conditions in the form of any $\bp \in \Gmax(P,P)$ in terms of proposal and acceptance couplings. First, we consider the relationship of the maximality of transition kernel coupling $\bp$ and the maximality of a proposal coupling $\bq$ that generates it.

§.§ Maximal proposal kernel couplings

It may seem that if $\bp \in \Gmax(P,P)$ is generated by a proposal coupling $\bq \in \Gamma(Q,Q)$ and some acceptance coupling $\bb$ then $\bq$ might have to be a maximal coupling. The proposal-based maximal coupling of O'Leary et al., 2021 has this property, and it seems plausible that to maximize the probability of $X=Y$ one might need to start by maximizing the probability of $x'=y'$. However, the following shows that no special relationship exists between maximal proposal and transition couplings.

Suppose the transition kernel coupling $\bp \in \Gmax(P,P)$ is generated by a proposal coupling $\bq_m \in \Gmax(Q,Q)$ and an acceptance coupling $\bb_m$, that $\bq_m(\xy, \Delta^c) > 0$ for some $\xy$,
and at that $\xy$, $\P(b_x = b_y = 1 \g x,y) < 1$ where $(x_m',y_m') \sim \bq_m(\xy,\cd)$ and $(b_x,b_y) \sim \bb_m(\xy, (x_m',y_m'))$.
Then there exists a non-maximal coupling $\bq \in \Gamma(Q,Q)$ and an acceptance indicator coupling $\bb$ such that $\bq$ and $\bb$ also generate $\bp$.

In the following proof, we use $\bq_m$ to construct a $\bq$ that agrees with $\bq_m$ on accepted proposals and independently redraws rejected ones. The hypotheses on the support of $\bq_m$ and $\bxy$ are very general but are needed to ensure that this procedure results in a coupling $\bq$ that is not maximal.

Construction of $\bq$ for Lemma <ref>

* Draw $(x'_m, y'_m) \sim \bq_m(\xy, \cd)$ and $(b_x, b_y) \sim \bb_m(\xy, (x'_m, y'_m))$

* For $z \in \{x, y\}$:

* If $b_z = 1$, set $z' = z'_m$. Else:

* Draw $(\tilde x, \tilde y) \sim \bq_m(\xy, \cd)$
and $(\tilde b_x, \tilde b_y) \sim \bb_m(\xy, (\tilde x, \tilde y)$

* If $(\tilde b_x, \tilde b_y) = (b_x, b_y)$, set $z' = \tilde z$

* Else: go to 2(b)

* Return $(x', y')$ and $(b_x, b_y)$

Let $\bq(\xy,\cd)$ be the distribution of the $\xyp$ output of Algorithm <ref>.
We claim that $\bq \in \Gamma(Q,Q)$. For $A \in \scrF$,

(, A ×)

= (x_m' ∈A, b_x=1 x,y) +  ∑_j ∈{0,1}  (b_x=0, b_y=j x,y) (x̃ ∈A b̃_x=0, b̃_y=j, x,y)

= (x_m' ∈A, b_x=1 x,y) +  ∑_j ∈{0,1}  (x_m' ∈A, b_x=0, b_y=j x,y)
= (x'_m ∈A x) = Q(x,A).

A similar argument shows $\bq(\xy, \calX \times A) = Q(y,A)$.
Let $\xy$ be such that $\bq_m(\xy, \Delta^c) > 0$.
We have assumed that there is a positive probability of rejecting either $x'_m$ or $y'_m$ at $\xy$.
Thus $\P(x' = y' \g x,y) < \P(x'_m = y'_m \g x,y)$, and so we conclude that $\bq$ is not a maximal coupling.

Next, for $i,j \in \{0,1\}$ and $A \in \scrFp$, define $\Phi_{ij}(\xy, A) := \P((x',y') \in A, b_x = i, b_y=j)$ using the full output of Algorithm <ref>. We observe that this is a coupled acceptance mechanism relating $\bq$ and $\bp$. The first condition of Definition <ref> is satisfied by construction. For the second condition, define $X_m = b_x x_m' + (1-b_x) x$ and
$Y_m = b_y y_m' + (1-b_y) y$. Since $\bq_m$ and $\bb_m$ generate $\bp$, we must have $(X_m, Y_m) \sim \bp(\xy,\cd)$. Thus for any $\axy \in \scrFp$,

Φ_11(, ) + Φ_10(, A_x ×) 1(y ∈A_y)

+ Φ_01(, ×A_y) 1(x ∈A_x)
+ Φ_00(, ×) 1(x ∈A_x) 1(y ∈A_y)

= ( X_0 ∈A_x, Y_0 ∈A_y, b_x = 1, b_y=1 x,y)
+ ( X_0 ∈A_x, Y_0 = y, b_x = 1, b_y=0 x,y)

+ ( X_0 = x, Y_0 ∈A_y, b_x = 0, b_y=1 x,y)
+ ( X_0 = x ,Y_0 = y, b_x = 0, b_y=0 x,y)

= (, ).

The third condition on $\Phi$ follows from the fact that $b_x = 1$ if $x_m'=x$ and $b_y = 1$ if $y_m'=y$.
Since $\Phi$ is a coupled acceptance mechanism relating $\bq$ and $\bp$,
Lemma <ref> ensures the existence of a $\bb$ such that $\bq$ and $\bb$ generate $\bp$.

The result above shows that if a maximal transition coupling $\bp \in \Gmax(P,P)$ is generated by a proposal coupling $\bq$ and an acceptance coupling $\bb$, then $\bq$ does not have to be maximal. The following example shows that some maximal couplings $\bp$ cannot be generated from any maximal coupling $\bq \in \Gmax(Q,Q)$.

Assume $\calX = \{1,2,3\}, \scrF = 2^\calX, \sas \xy = (1,2)$. From these states, we assume the following proposal and transition kernel distributions:

Q(x=1, ) = (0,,)         P(x=1, ) = (,,0)

Q(y=2,) = (,0,)         P(y=2, ) = (,0,).

It is straightforward to verify that these distributions correspond to an MH transition kernel obtained when $Q(3, \cd) = (0,1,0)$ and $\pi = (\sfrac{2}{5}, \sfrac{2}{5}, \sfrac{1}{5})$. Simple algebra shows that any coupling in $\Gmax(Q,Q)$ and any coupling in $\Gmax(P,P)$ must have the following properties:

3pt $ \bq((1,2), \cd) = $

r |c|c|c| l
1     0         0

2     0    0     0      ←y

3     0     0

1     2     3

3pt $ \bp((1,2), \cd) = $  	rcccl

r |c|c|c| l
1         0     0

2     0     0     0      ←y

3     0         0

1     2     3

There exists no acceptance indicator coupling $\bb$ such that it and the unique maximal $\bq$ given
above generate $\bp$, since $\xyp \sim \bq((1,2),\cd), (b_x,b_y) \sim \bb((1,2), \xyp)$,
$X = b_x x' + (1-b_x) x$, $Y = b_y y' + (1-b_y) y$,
and $(X,Y) \sim \bp((1,2), \cd)$ yield a contradiction:

= ( X=2,Y=3 x=1, y=2)
≤( x'=2,y'=3 x=1, y=2) = 0.

Note that in line with Theorem <ref>, we can still generate $\bp((1,2),\cd)$
using the following non-maximal proposal coupling and the coupled acceptance indicators $b_x, b_y$:

3pt $ \tilde Q ((1,2), \cd) = $

r |c|c|c| l
1     0     0

2     0     0     0      ←y

3     0         0

1     2     3

(b_x =1, b_y = 1 (x,y) = (1,2), (x',y') = (2,3)) = 1

(b_x = 0, b_y = 1 (x,y) = (1,2), (x',y') = (3,1)) = 1.

One upshot of Lemma <ref> and Example <ref> is that a coupling $\bp \in \Gmax(P,P)$ requires a certain amount of proposal probability on the diagonal, but the maximality of $\bq$ is neither necessary nor sufficient for $\bq$ to be able to generate $\bp$.

§.§ Characterization of maximal kernel couplings

Next we turn to the main result of this section, which extends Theorem <ref> to
characterize the maximal couplings of an MH-like transition kernel in terms of proposal and
acceptance indicator couplings. For each $x,y \in \calX$, let $(\sxy, \sxy^c)$ be any Hahn
decomposition for $P(x,\cd) - P(y, \cd)$. Thus $\sxy \in \scrF$ and $P(x,A) \geq P(y,A)$ for any $A
\in \scrF$ with $A \subset \sxy$. Note that if $P(x,\cd)$ and $P(y,\cd)$ have Radon–Nikodym derivatives
$p(x,\cd)$ and $p(y,\cd)$ with respect to a common dominating measure, then we can use $S_{xy} = \{z
: p(x, z) \geq p(y,z) \}$ for these sets.

Let $P$ be the MH-like transition kernel on $(\calX, \scrF)$ generated by a proposal kernel $Q$ and an acceptance rate function $a$. Then $\bp \in \Gmax(P,P)$
if and only if $\bp$ is generated by $\bq \in \Gamma(Q,Q)$ and an acceptance indicator coupling $\bb$ with the following properties: if $\bxy \sim \bb(\xy,\xyp)$, then for all $x, y \in \calX$:

* $\P(b_x=1 \g x,y,x') = a(x,x')$ for $Q(x,\cdot)$-almost all $x'$

* $\P(b_y=1 \g x,y,y')= a(y,y')$ for $Q(y,\cdot)$-almost all $y'$

and for $\bq(\xy,\cd)$-almost all $\xyp$,

* $\P(b_x=b_y=1\g x,y,x',y') = 0$ if $x' \neq y'$ and either $x' \in \sxy^c$ or $y' \in \sxy$

* $\P(b_x=1, b_y=0\g x,y,x',y') = 0$ if $x' \neq y$ and either $x' \in \sxy^c$ or $y \in \sxy$

* $\P(b_x=0, b_y=1 \g x,y,x',y') = 0$ if $y' \neq x$ and either $x \in \sxy^c$ or $y' \in \sxy$

* $\P(b_x=0, b_y=0 \g x,y,x',y') = 0$ if $x \neq y$ and either $x \in \sxy^c$ or $y \in \sxy$.

Diagram of acceptance scenarios considered in Theorem <ref>.
The support of a maximal coupling $\bp(\xy,\cd)$ is contained in the union of $\sxy \times \sxy^c$ (gray box) and $\Delta$ (the diagonal).
Arrows illustrate the relationship of proposals $\xyp$ to transitions $(X,Y)$ under different accept/reject combinations,
with transitions outside the support of $\bp(\xy,\cd)$ forbidden almost surely.
Case 1: the maximality of $\bp$ does not constrain the acceptance pattern of proposals $\xyp \in \sxy \times \sxy^c$.
Case 2: proposals in $\Delta$ can be fully accepted $(b_x=b_y=1)$ or fully rejected $(b_x=b_y=0)$, but $y'$ must be accepted if $x' \in S_{xy}^c$, and $x'$ must be accepted if $y' \in S_{xy}$.
Case 3: proposals in $(\sxy \times \sxy^c)^c \cap \Delta^c$ must be fully rejected unless $y'=x$ or $x'=y$.
Case 4: a proposal $\xyp$ outside the support of $\bp(\xy, \cd)$ may be partially accepted $(b_x \neq b_y)$ if it yields a transition to $(x,x)$ or $(y,y)$.

Recall that by Corollary <ref>, the maximality of a coupling $\bp \in \Gamma(P,P)$ is equivalent to a condition on the support of each
$\bp(\xy,\cd)$. Conditions 3-6 relate these support constraints to the behavior of a proposal coupling $\bq$ and an acceptance indicator coupling $\bb$.
See Figure <ref> for an illustration of the acceptance scenarios considered in these conditions and a visual intuition for why certain ones must be ruled out for $\bq$ and $\bb$ to generate a maximal $\bp$.

Suppose $\bp \in \Gmax(P,P)$. By Theorem <ref>, there exists $\bq \in \Gamma(Q,Q)$ and an acceptance indicator coupling $\bb$
such that for any $x, y \in \calX$ and $\bxy \sim \bb(\xy,\xyp)$, we have

* $\P(b_x=1 \g x,y,x') = a(x,x')$ for $Q(x,\cdot)$-almost all $x'$, and

* $\P(b_y=1 \g x,y,y')= a(y,y')$ for $Q(y,\cdot)$-almost all $y'$.

Thus  Conditions 1 and 2 directly follow from Theorem <ref>.

Since	$\bq$ and $\bb$ generate $\bp$, we have
$\XY \sim \bp(\xy,\cd)$ where
$X = b_x x' + (1-b_x) x$ and $Y=b_y y' + (1-b_y) y$.
Since $\bp$ is maximal, Corollary <ref> implies

$$ 0 = \bp\big( \xy, ( S_{xy}^c \times \calX) \sm \Delta \big) = \P(X \in \sxy^c, X \neq Y \g x,y).$$

Breaking this up into the four possible acceptance scenarios
$\bxy = (1,1)$, $(1,0)$, $(0,1)$, and $(0,0)$ yields

0 = [ 1(x' ≠y', x' ∈^c) (b_x=b_y=1 x,y,x',y') ]

0 = [ 1(x' ≠y, x'∈^c) (b_x=1,b_y=0 x,y,x',y') ]

0 = [ 1(y' ≠x, x ∈^c) (b_x=0, b_y=1 x,y, x',y') ]

0 = [ 1(x ∈^c ) (b_x=b_y=0 x,y,x',y') ].

In turn, these equations imply that for $\bq(\xy,\cd)$-almost all $\xyp$,

(b_x=b_y=1 x,y,x',y') = 0  if  x' ≠y'  and  x' ∈^c

(b_x=1, b_y=0 x,y,x',y') = 0  if  x' ≠y  and  x' ∈^c

(b_x=0, b_y=1 x,y,x',y') = 0  if  y' ≠x  and  x ∈^c

(b_x=b_y=0 x,y,x',y') = 0  if  x ≠y  and  x ∈^c.

This shows that the first either/or case of each of Conditions 3-6 are satisfied. Since $\bp$ is maximal,
Corollary <ref> also implies $0 = \bp\big( \xy, (\calX \times S_{xy}) \sm \Delta \big)$.
Proceeding as above shows that the second either/or cases are also satisfied.
So we conclude that if $\bp \in \Gmax(P,P)$, then $\bp$ is generated by a $\bq$ and $\bb$ satisfying the six conditions stated above.

For the converse, suppose that $\bq \in \Gamma(Q,Q)$ and a proposal coupling $\bb$ generate
$\bp$ and satisfy the given hypotheses.
Since Conditions 1 and 2 are equivalent to the conditions of Theorem <ref>,
we have $\bp \in \Gamma(P,P)$.
Now let $\xyp \sim \bq(\xy,\cd)$, $\bxy \sim \bb(\xy,\xyp)$, $X = b_x x' + (1-b_x) x$, and $Y= b_y y' + (1-b_y) y$.
$\bq$ and $\bb$ generate $\bp$, so

(, (S_xy^c ×) Δ) = (X ∈S_xy^c, X ≠Y x,y)

= (x' ∈A, x' ≠y', b_x=1, b_y=1 x,y) + (x' ∈A, x' ≠y, b_x=1, b_y=0 x,y)

+ (y' ≠x, b_x=0, b_y=1 x,y) 1(x ∈A) + (b_x=0, b_y=0 x,y) 1(x ∈A) 1(x ≠y) = 0.

The last equality follows directly from Conditions 3-6 of the Theorem,
with Condition 3 ensuring that the first term equals zero, Condition 4 ensuring that the second term equals zero, and so on.
A similar argument yields $\bp(\xy, (\calX \times S_{xy} ) \sm \Delta) = 0$.
By Corollary <ref>, $\bp$ is maximal if and only if
there is a measurable set $S \in \scrF$ such that
$\bp(\xy, (S^c \times \calX) \sm \Delta ) = \bp(\xy, (\calX \times S) \sm \Delta ) = 0$.
The argument above shows that $S_{xy}$ has these properties,
so we conclude that $\bp \in \Gmax(P,P)$.

Now we conclude this section. Theorem <ref> completely characterizes the maximal couplings
of MH-like transition kernels. We show every maximal kernel coupling can be represented by a
proposal coupling and an acceptance coupling that satisfies additional constraints on the Hahn
decomposition. Meanwhile, perhaps surprisingly, we show in Example <ref> that there is no
special relationship between maximal proposal couplings and maximal kernel couplings.

§ EXAMPLES

In Section <ref> we showed that any coupling of MH-like transition kernels can be
generated by a proposal coupling followed by an acceptance indicator coupling. Here we apply this
result to some popular algorithms. In Section <ref> we give a more explicit form of
Theorem <ref> that holds under mild assumptions on the proposal distribution $Q$.
Sections <ref> and <ref> concern the random walk Metropolis algorithm,
the Metropolis-adjusted Langevin algorithm, and the Metropolis–Hastings algorithm on a discrete
state space. These examples illustrate the range of behavior possible for simple, gradient-based,
and discrete forms of the MH algorithm. We note that our methods also apply to algorithms like
Hamiltonian Monte Carlo and Metropolis-within-Gibbs and yield qualitatively similar conclusions.

Finally, in Section <ref> we consider the two-step representation of an MH
transition kernel satisfying minorization conditions. Such conditions play an important role in the
`drift and minorization' method of bounding convergence to stationarity, as in
Rosenthal, 1995 and Jones and Hobert, 2001. The splitting argument at the
heart of this approach is usually described in terms of the overall transition kernel, but here we show that
it takes a natural form in terms of proposal and acceptance indicator couplings.

§.§ Simplified characterization of couplings

To prove the `only if' part of Theorem <ref> we constructed a map from an arbitrary
coupling $\bp \in \Gamma(P,P)$ to a proposal coupling $\bq \in \Gamma(Q,Q)$ and an acceptance
indicator coupling $\bb$ such that $\bq$ and $\bb$ generate $\bp$.  Lemmas
<ref>–<ref> suggest a complicated relationship between $\bp$,
$\bq$, and $\bb$, at least when $P$ is allowed to be any MH-like transition kernel.
Corollary <ref> shows that this relationship takes a more intuitive
form when $Q(x, \cdot)$ is absolutely continuous with respect to the base measure and when $Q(x,
\sx) = 0$ for all $x \in \scrF$. These assumptions often hold, e.g. on a continuous state space when
$\lambda$ is non-atomic, on a discrete state space when $Q$ represents a (non-lazy) random walk, and
in many other cases.

We need to define a few new objects before stating the main result of this section. First, for all $A_x
\in \scrF$ let $\bp_y(x, A_x) := \bp(\xy, (A_x \sm \sx) \times \sy)$, so that $\bp_y(x, \cdot)$ is a
a sub-probability on $(\calX, \scrF)$. For all $x, y \in \calX$, the measure $\bp_y(x, \cdot) \ll
\lambda$ if $Q(x, \cdot) \ll \lambda$ since

_y(x, A_x)     = (, (A_x ) ×) ≤(, (A_x ) ×)

= P(x, A_x ) = ∫_A_x  a(x,x') q(x,x') λ(x').

Here $q(x,\cdot) = \diff Q(x,\cdot) / \diff \lambda$.
In this case $\bp_y(x, \cdot)$ has density $\bar p_y(x, \cdot)$ with respect to $\lambda$ by the Radon–Nikodym
theorem. A similar argument shows that $\bp_x(y, A_y) := \bp(\xy, \sx \times (A_y \sm \sy))$ has
density $\bar p_x(y, \cdot)$ with respect to $\lambda$.

Let $r(x) := P(x, \sx)$, the probability of a transition from $x$ to itself under $P$. From the
definitions in Section <ref>, we have
$\beta(x) = 1(r(x) = 0)$ and

μ(x, A_x) :=
Q(x, A_x) - P(x, A_x ) /r(x)      r(x) > 0

1(x ∈A_x)      r(x) = 0.

It follows that $\mu(x, A_x) (1 - \beta(x)) = (Q(x, A_x) - P(x,
A_x \sm \sx))/r(x)$ if $r(x) >0$ and 0 otherwise.
Thus $\mu(x, \cdot) (1 - \beta(x))$ has density
$m(x,x') := q(x,x') (1-a(x,x'))/r(x)$ when $r(x) > 0$, and 0 otherwise.

Next, we separate $\bp$ into one part that is absolutely continuous with respect to
$\lambda \times \lambda$ and another part that is singular to it. By the Lebesgue decomposition
theorem <cit.> for each $x, y \in \calX$ we have $\bp(\xy, \cdot) =
\bp_\ll(\xy, \cdot) + \bp_\perp(\xy, \cdot)$ with $\bp_\ll(\xy, \cdot) \ll \lambda \times \lambda$
and $\bp_\perp(\xy, \cdot) \perp \lambda \times \lambda$. We then define $p(\xy, \cdot)$ to be the
density of $\bp_\ll(\xy, \cdot)$ with respect to $\lambda \times \lambda$. Finally let $\bar r(x,y)
:= \bp(\xy, \sx \times \sy)$, the probability of a transition from $\xy$ to itself under $\bp$. With
these definitions, we can now give an explicit characterization of the couplings $\bp \in
\Gamma(P,P)$ under mild conditions on the proposal distribution.

Let $P$ be the MH-like transition kernel on $(\calX, \scrF)$ generated by a proposal kernel $Q$ and
an acceptance rate function $a$, and suppose that $Q(x, \cdot) \ll \lambda$ with $Q(x,\sx) = 0$ for
all $x \in \calX$. If a joint kernel $\bp \in \Gamma(P,P)$, then it is generated by $\bq = \bq_\ll
+ \bq_\perp \in \Gamma(Q,Q)$ and an acceptance indicator coupling $\bb$ with the following
properties for all $x,y \in \calX$ and $\bxy \sim \bb(\xy,\xyp)$:

* $\bq_\perp(\xy, A) = \bp_\perp(\xy, A \cap (\sx^c \times \sy^c))$ for $A \in \scrF$,

* $\bq_\ll(\xy, \cdot)$ has the following density with respect to $\lambda \times \lambda$:

q(, )

= p(, ) + p̅_y(x, x') m(y,y')
+ m(x,x') p̅_x(y, y') + m(x,x') m(y, y') r̅(x,y),

* $b_x = b_y = 1$ almost surely when $\xyp$ is in the support of $\bq_\perp(\xy, \cdot)$,

and for $\bq_\ll(\xy, \cdot)$-almost all $\xyp$,

* $\P(b_x = 1 \g x,y,x',y')\, q(\xy, \xyp) = p(\xy, \xyp) + \bar p_y(x, x') m(y,y')$,

* $\P(b_y = 1 \g x,y,x',y')\, q(\xy, \xyp) = p(\xy, \xyp) + \bar p_x(y, y') m(x,x')$.

Let $B_{xy} := \sx^c \times \sy^c$, and note that for all $x,y \in \calX$ and $\bq \in \Gamma(Q,Q)$,
we have $\bq(\xy, B_{xy}) = 1$, since $B_{xy}^c = (\sx \times \calX) \cup (\calX \times \sy)$,
$\bq(\xy, \sx \times \calX) = Q(x, \sx) = 0$, and $\bq(\xy, \calX \times \sy) = Q(y, \sy) = 0$. Thus we may restrict attention to the behavior of $\bq(\xy, \cdot)$ on $B_{xy}$.

When $\bp \in \Gamma(P,P)$, Lemma <ref> tells us that there exists a proposal
coupling $\bq \in \Gamma(Q,Q)$ and a coupled acceptance mechanism $\Phi$ relating $\bp$ and $\bq$.
In particular, for $x,y \in \calX$ and $A_x, A_y \in \scrF$ with $x \not \in A_x$ and $y \not
\in A_y$, the proof of that Lemma shows that we can use the following measures:

(, ) = (Φ_11 + Φ_10 + Φ_01 + Φ_00)(, )

Φ_11(, ) = ( , )

Φ_10(, ) = ( , A_x ×) (1 - β(y))  μ(y, A_y)

Φ_01(, ) = (1 - β(x)) μ(x, A_x) ( , ×A_y)

Φ_00(, ) = (1 - β(x)) μ(x, A_x) (1-β(y)) μ(y, A_y) (, ×) .

From the Lebesgue decomposition of $\bp$, we have

( , ) = _⊥(,) + ∫_ p(,) .

The definitions above Corollary <ref> also imply that
$\Phi_{10}(\xy, \cdot)$ has density $p_y(x, x') m(y,y')$,
$\Phi_{01}(\xy, \cdot)$ has density $p_x(y, y') m(x,x')$,
and $\Phi_{00}(\xy, \cdot)$ has density $\bar r(x,y) m(x,x') m(y,y')$.
Thus $\bq(\xy, \cdot)$ is the sum of a singular part $\bq_\perp(\xy, A) = \bp(\xy, A \cap B_{xy})$
and an absolutely continuous part $\bq_\ll(\xy, \cdot)$ with the density function specified in condition 2, above.

Next by Lemma <ref>, we know that there exists an acceptance indicator coupling $\bb$
such that $\bq$ and $\bb$ generate $\bp$. This $\bb$ has the property that
$\bq(\xy, \cdot)$-almost all values of $\xyp$,
if $\bxy \sim \bb(\xy,\xyp)$, then

(b_x=1 x,y,x',y')    = (Φ_11 + Φ_10)(, ·) / (, ·)

(b_y=1 x,y,x',y')     = (Φ_11 + Φ_01)(, ·) / (, ·).

For $A \in \scrF$ contained in the support of $\bq_\perp(\xy, \cdot)$,
we have $\Phi_{11}(\xy, A) = \bq(\xy, A)$ and $\Phi_{10}(\xy, A) = \Phi_{01}(\xy, A) = 0$, so the Radon-Nikodym derivatives above equal 1 almost surely. This proves condition 3.
Otherwise, for
$\bq(\xy, \cdot)$-almost all
points $\xyp$ with $q(\xy, \xyp) > 0$ we have

(b_x=1 x,y,x',y')
=  (Φ_11 + Φ_10)(, ·) / (λ×λ)/(, ·) / (λ×λ)
= p(, ) + p̅_y(x, x') m(y,y')/q(,)

and similarly for $\P(b_y \g x,y,x',y')$.
Finally, we have $p(\xy, \xyp) = \bar p_y(x,x') = \bar p_x(y,y') = 0$ whenever $q(\xy, \xyp) = 0$,
thus proving conditions 4 and 5.

Corollary <ref> applies to MH-like algorithms on both continuous and discrete spaces, as long as $Q(x,\cdot)$ has a density or mass function and as long as the proposal $x'$ almost surely differs from the current point $x$. It provides an explicit way to represent any kernel coupling in terms of proposal and acceptance indicator couplings.

§.§ Metropolis–Hastings algorithms on a continuous state space

We now turn to the implications of our characterization results for some widely-used algorithms. To
begin, let $\calX = \R^n$ equipped with Lebesgue measure $\lambda$, and let $Q$ be a proposal kernel
on $\calX$ with density $q$ such that $q(x,y) = g(\lVert x - y \rVert)$ for some $g : \R^+ \to \R^+$
and any $x,y \in \calX$. Let $\pi$ be a target distribution with density $\pi(\cdot)$ and let $a$ be
the associated MH acceptance rate function. Given these hypotheses on $Q$, we refer to the MH
transition kernel $P$ generated by $Q$ and $a$ as a Random Walk Metropolis (RWM) kernel.

Corollary <ref> implies the existence of a proposal coupling $\bq \in \Gamma(Q,Q)$ which can be written as $\bq = \bq_\ll + \bq_\perp$. Here $\bq_\perp(\xy, A) = \bp_\perp(\xy, A \cap (\sx^c \times \sy^c))$ for $A \in \scrF$ is  the measure $\barP$ after removing the mass at its current state $(x,y)$, and
$\bq_\ll(\xy, \cdot)$ has density

q(, )

= p(, ) + p̅_y(x, x') m(y,y')
+ m(x,x') p̅_x(y, y') + m(x,x') m(y, y') r̅(x,y),

with respect to $\lambda \times \lambda$, where all the notations are defined at the beginning of Section <ref>. For RWM algorithms, the function $m$ takes the following form for every $x,x'$:
m(x,x') := q(x,x') (1-a(x,x'))/r(x) = q(x,x')(1 - π(x')/π(x))/1 - ∫_q(x,y) (π(y)/π(x)∧1) λ(y).

The Metropolis-adjusted Langevin algorithm (MALA) [Roberts and Tweedie, 1996] uses a discretized
approximation to the Langevin diffusion $\diff X_t = \frac 12 \nabla \log\pi(X_t) \diff t + \diff
W_t$, where $W_t$ represents a Brownian motion. After each update the MH acceptance-rejection
mechanism is applied to determine whether to accept the proposed move. Thus MALA may be viewed as a
case of the MH algorithm using a proposal distribution $Q(x,\cdot) \sim \N(x+\tau \nabla \pi(x),
2\tau \mathbb I)$. This distribution has density $q(x,y) \propto \exp(-\frac{1}{4\tau}\lVert y - x -
\tau \nabla \log\pi(x) \rVert_2^2)$, where $\tau$ is a tuning parameter. Since MALA makes use of
gradient information, it typically outperforms RWM in high dimensions [Roberts and Rosenthal, 1998].
For MALA algorithms, the measure $\mu(x,\cdot)$ has a slightly different integral representation
relative to RWM:

\begin{align*}
\mu(x,A) & := \begin{cases}
\frac{\int_{A} q(x, y) (1 - (\frac{\pi(y)q(y,x)}{\pi(x)q(x,y)}\wedge 1))\lambda(\diff y)}{r(x)} & \text{if } r(x) > 0 \\
1(x \in A) & \text{otherwise.}
\end{cases}
\end{align*}

Here $r(x) = 1 - \int_\calX q(x,y)  (\frac{\pi(y)q(y,x)}{\pi(x)q(x,y)}\wedge 1) \lambda(\diff y)$ is the rejection probability at $x$.

Fix $x,y$ with $r(x), r(y) > 0$ and let $p(x,y) = q(x,y) (\frac{\pi(y)q(y,x)}{\pi(x)q(x,y)}\wedge 1)$ be the transition density from $x$ to $y$. Then every kernel coupling $\bar P$ of the MALA algorithm is very similar to Example <ref>.
Again by Corollary <ref>, there exists  a proposal coupling $\bq \in \Gamma(Q,Q)$ which can be written as $\bq = \bq_\ll + \bq_\perp$. Here $\bq_\perp(\xy, A) = \bp_\perp(\xy, A \cap (\sx^c \times \sy^c))$ for $A \in \scrF$ is  the measure $\barP$ after removing the mass at its current state $(x,y)$, and
$\bq_\ll(\xy, \cdot)$ has density

q(, )

= p(, ) + p̅_y(x, x') m(y,y')
+ m(x,x') p̅_x(y, y') + m(x,x') m(y, y') r̅(x,y),

with respect to $\lambda \times \lambda$, where all the notations are defined at the beginning of Section <ref>.  For MALA algorithms, the function $m$ takes the following slightly different form from the RWH algorithms:
m(x,x') := q(x,x') (1-a(x,x'))/r(x) = q(x,x')(1 - π(x')q(x',x)/π(x)q(x,x'))/ 1 - ∫_q(x,y)  (π(y)q(y,x)/π(x)q(x,y)∧1) λ(y).

Comparing with Example <ref>, we find that the two-step representations for both algorithms take the same general form, while the details  (such as $p(\cdot, \cdot)$, $r(\cdot)$, $q(\cdot, \cdot)$, and $m(\cdot, \cdot))$ differ by algorithm.

§.§ The Metropolis–Hastings algorithm on a finite state space

Consider an arbitrary Metropolis–Hastings algorithm on the finite state space $\calX = \{x_1, \cdots, x_n\}$ with target distribution $\pi$ and proposal distribution $Q$ with the property that $Q(x, \{x\}) = 0$ for all $x \in \calX$. Let $\bar P$ be a transition kernel coupling. For each fixed $x, y \in \calX$, $\bar P((x,y), \cdot )$ can be represented by a $n\times n$ matrix $M_{\bar P}$ where the $(i,j)$-th entry corresponds to the probability of moving $(x,y)$ to $(x_i, x_j)$. Let $(r_1, \cdots, r_n), (c_1, \cdots, c_n)$ be the row and column sums of $M_{\bar P}$. The definition of a coupling guarantees that $r_i = P(x, x_i) = Q(x,x_i) (\frac{\pi(x_i)Q(x_i,x)}{\pi(x)Q(x,x_i)}\wedge 1)$, $c_j = P(y, x_j) = Q(y, x_j) (\frac{\pi(x_j)Q(x_j, y)}{\pi(y)Q(y, x_j)}\wedge 1)$ for every $i,j$. The desired transition kernel  coupling $\bar Q$ can also be represented as an $n\times n$ matrix $M_{\bar Q}$ with row sums $[Q(x, x_1), \cdots Q(x, x_n)]$ and column sums $[Q(y, x_1), \cdots, Q(y, x_n)]$.

Writing $x = x_{i_0}$ and $y = x_{j_0}$, then  Lemma <ref> and Corollary <ref> implies that $M_{\bar Q}$ can be expressed as the sum of  $n\times n$ matrices $M_{11}, M_{10}, M_{01}, M_{00}$, where

M_11(i,j)    =  M_P̅(i,j) 1_(i,j)≠(i_0, j_0)     M_10(i,j) = M_P̅(i, j_0) μ_y(j)1_i ≠i_0

M_01(i,j)    =  μ_x(i) M_P̅(i_0, j)  1_j ≠j_0    M_00(i,j) =  M_P̅(i_0, j_0)  μ_x(i) μ_y(j).

μ_x(i) =

Q(x, x_i) - P(x,x_i)/1 - r_i_0     if  r_i_0 < 1

1_i = i_0     otherwise

μ_y(j) =

Q(y, x_j) - P(y,x_j)/1 - c_j_0     if  c_j_0 < 1

1_j = j_0     otherwise.

It is straightforward to verify that the row and column sums of $\bar Q$ recover $Q(x,\cdot)$ and $Q(y,\cdot)$.

Corollary <ref> also specifies the necessary acceptance step coupling. After proposing a move from $(x,y) = (x_{i_0}, x_{j_0})$ to $(x_{i_1}, y_{j_1})$,
the probability accepting both $x$ and $y$ proposals is $M_{11}(i_1, j_1)/M_{\bar Q}(i_1,j_1)$,
the probability of accepting the $x$ proposal and rejecting the $y$ proposal is $M_{10}(i_1, j_1)/M_{\bar Q}(i_1,j_1)$,
the probability of rejecting the $x$ proposal and accepting the $y$ proposal is $M_{01}(i_1, j_1)/M_{\bar Q}(i_1,j_1)$,
and the probability of rejecting both proposals and remaining at $(x,y)$ is $M_{00}(i_1, j_1)/M_{\bar Q}(i_1,j_1)$. Again it is straightforward to confirm that these probabilities yield the desired transition behavior.

§.§ Coupling with a minorization condition

Let $P$ be an MH-like transition kernel generated by a proposal kernel $Q$ and an acceptance rate
function $a$, and assume that $P$ has stationary distribution $\pi$. The kernel $P$
satisfies a minorization condition corresponding to a set $\calC \subseteq \calX$ if there exists
$\eps > 0$ and a probability measure $\nu$ on $(\calX, \scrF)$ such that $P(x,A) \geq  \epsilon\,
\nu(A)$ for all $x \in \calC$ and $A \in \scrF$. If $\calC = \calX$, then a simple argument shows
that $\lVert P^n(x,\cdot) - \pi(\cdot) \rVert_{\TV} \leq (1 - \epsilon)^n$ for every $n$
[Meyn and Tweedie, 2012]. When $\calC$ is a strict subset of $\calX$, convergence rate results
require additional assumptions to control the distribution of return times of the chain to
the set $\calC$.

Minorization arguments often employ the following coupling construction, sometimes called a Nummelin
splitting [Nummelin, 1978, Athreya and Ney, 1978, Jones and Hobert, 2001, Gelman et al., 2010], to bound
the convergence rate of a chain to its stationary distribution. Suppose that we run two identically
distributed Markov chains $(X_n)$ and $(Y_n)$ in tandem, with one initialized arbitrarily and the
other initialized from its stationary distribution $\pi$. If $X_n, Y_n \in \calC$ at some step $n$,
then we flip a coin with probability $\eps$ of heads. If the coin comes up heads we then draw
$X_{n+1} = Y_{n+1} \sim \nu$, and otherwise we draw $X_{n+1}$ and $Y_{n+1}$ independently from their
residual distributions so that $X_{n+1} \sim \nu^r_x := (P(X_n,\cdot) - \epsilon \nu(\cdot) / (
1-\epsilon)$ and $Y_{n+1}\sim \nu^r_y := (P(Y_n,\cdot) - \epsilon \nu(\cdot))/(1-\epsilon)$. Once
the chains have met we update both chains according to the same draws from $P$, so that they  they
remain together at all subsequent iterations. Otherwise we repeat the above whenever both chains
occupy $\calC$.

The procedure above yields a coupling $\bar P$ of transition kernels $P$, defined without direct
reference to the proposal or acceptance distributions. Alternatively, we can use Theorem
<ref> to represent this coupling in terms of a proposal coupling $\bq$ and an acceptance
indicator coupling $\bb$. For every $x,y \in \calC$, the kernel coupling $\bp(\xy, \cdot)$ described
above is a mixture of a measure on the diagonal $\Delta = \{(x,x) : x \in \calX) \} \subset \calX
\times \calX$ and a product measure on the complement of $\Delta$. In particular, for any $S \in
\scrF \otimes \scrF$ we have $\bp(\xy, S) =\eps\, \nu(S \cap \Delta) + (1 - \eps) (\nu^r_x \times
\nu^r_y) (S \sm \Delta)$.

To represent $\bar P$ by a two-step coupling it suffices to construct the coupled acceptance measure
$\Phi = (\Phi_{11}, \Phi_{10}, \Phi_{01}, \Phi_{00})$. We continue to assume that $Q(x, \cdot) \ll
\lambda$ and $Q(x, \sx) = 0$ for all $x \in \calX$, and as noted above we have $\beta(x) = 0$ if
$r(x)> 0$ and $1$ otherwise, and

μ(x,A_x)     =
Q(x,A_x) - P(x,A_x∖{x})/r(x)     if  r(x) > 0

1(x ∈A_x)     otherwise

and similarly for $\mu(y, A_y)$. From the proof of Lemma <ref>, we can write the components of $\Phi$ as follows:

Φ_11(, A_x×A_y)= ( , A_x×A_y ∩(^c ×^c) )

Φ_10(, A_x×A_y) = ( , (A_x ∩^c) ×) ×μ(y, A_y)

Φ_01(, A_x×A_y) = μ(x,A_x)×( ,   ×(A_y ∩^c))

Φ_00(, A_x×A_y) =  r(x,y) μ(x,A_x)×μ(y,A_y)

where $r(x,y) =\bar P((x,y),\{x\}\times\{y\})$ the probability that the kernel stays at $(x,y)$. In this case, the two chains are independent when meeting does not occur. Thus we have $r(x,y) = r(x) r(y)$.  After setting all the $\Phi_{ij}$, we define $\bar Q = \Phi_{00} +\Phi_{01} + \Phi_{10}+\Phi_{11}$ as our proposal coupling.

Next we consider the acceptance indicator coupling $\bb$.
Lemma  <ref> implies the existence of acceptance indicators $\bxy \sim \bb(\xy,\xyp)$ such that

(b_x = i, b_y = j x,y,x',y') = ϕ_ij( , )

where $\phi_{i,j}(\xy,\cdot) = \diff \Phi_{i,j}(\xy, \cdot)/\diff Q(\xy, \cdot)$.
If we write every term of $\Phi_{ij}$ in its integration form, then $\phi_{i,j}$ can also be evaluated at every point  as a ratio of densities. For example, let $x' \neq x$, $y' \neq y$ be two different points in $\calX$. Then the probability density of $\bq$ for a move from $\xy$ to $\xyp$ will be

q(, )
= (p(x, x') -ϵν(x'))(p(y,y') - ϵν(y'))
+ (p(x,x') - ϵν(x')) (q(y,y') - p(y,y'))

+ (p(x,x') -  q(x,x')) (q(y,y') - ϵν(y')) +
(q(x,x') -p(x,x'))  (q(y,y') - p(y,y')).

Here $p(x, x') = q(x, x') (\frac{\pi(x') q(x',x)}{\pi(x)q(x,x')}\wedge 1)$ is the transition kernel density from $x$ to $x'$.

Thus, when $x' \neq x$, $y' \neq y$, and $x' \neq y'$, we have the following expressions for the distribution of the acceptance indicator pair $\bxy$ conditional on the current state $\xy$ and the proposal state $\xyp$:

p_11    := (b_x = 1, b_y = 1 x,y,x',y')
=  ( p(x,x') -ϵν(x'))(p(y,y') - ϵν(y')) / q(, )

p_10    := (b_x = 1, b_y = 0 x,y,x',y')
=  ( p(x,x') - ϵν(x')) (q(y,y') - p(y,y')) / q(, )

p_01    := (b_x = 0, b_y = 1 x,y,x',y')
=  ( p(x,x') -  q(x,x')) (q(y,y') - ϵν(y')) / q(, )

p_00    := (b_x = 0, b_y = 0 x,y,x',y')
=  ( q(x,x') -p(x,x')) (q(y,y') - p(y,y'))  / q(, ) .

The marginal probability of accepting the $x$ move is $p_{10} + p_{11}$ and the probability of accepting the  $y$ move is $p_{01} + p_{11}$, consistent with Lemma <ref>.  As a sanity check,  the probability density of moving from $\xy$ to $\xyp$ according to our coupling and acceptance mechanism is
$q(\xy,\xyp)\times p_{11} = (p(x,x') -\epsilon \nu(x')) \cdot(p(y,y') - \epsilon \nu(y'))$, which is indeed the probability density of the minorization coupling $\bar P(\xy, \cdot)$ at point $\xyp$. The other cases, such as  $y' = x'$, or $x' = x$, or $y' = y$ can be calculated in the same way.

§ DISCUSSION

The analysis of couplings is an appealing topic from both a theoretical and an applied point of
view. In theoretical work, couplings arise as a proof technique in the study of Markov chains and
other stochastic processes. They are also closely related to assignment problems under marginal
constraints, a topic of interest since at least Birkhoff, 1946. In applications,
couplings play a leading role in new techniques for convergence diagnosis, variance
reduction, and unbiased estimation, as detailed in Section <ref>.

In this study, we have considered kernel and maximal kernel couplings for the Metropolis–Hastings
algorithm and its relatives. In Theorem <ref>, we showed that every transition kernel
coupling arises from a proposal coupling and an acceptance indicator with certain properties. We
also showed the converse: any kernel $\bp$ on the joint space generated this way must be a kernel
coupling. In Theorem <ref> we took this a step further, demonstrating that maximal kernel
couplings correspond to pairs of proposal and acceptance couplings subject to a short list of additional
conditions. These characterization results provide a unifying and descriptive framework to specify
possible couplings of the MH transition kernel.

Throughout this paper, we have taken the perspective that the transition kernel of interest $P$ on a
state space $(\calX, \scrF)$ arises from a given proposal kernel $Q$ and acceptance rate function
$a$. Alternatively, we could have begun with any kernel $P$ such that there exists another `weakly
dominating' kernel $Q$ such that $P(x, A) \leq Q(x, A)$ for all $x \in \calX$ and $A \in \scrF$ with
$x \not \in A$. With this perspective, our Theorem <ref> reads roughly as follows: `suppose
a kernel $P$ is weakly dominated by $Q$, and let $a(x, \cdot)$ be the Radon–Nikodym derivative of
$P(x, \cdot)$ with respect to $Q(x, \cdot)$ away from the current state $x$. Then every kernel
coupling $\bp \in \Gamma(P,P)$ is generated by a coupling $\bq \in \Gamma(Q,Q)$ followed by an
acceptance indicator coupling $\bb$ based on $a$.' From this perspective, our result appears as a joint
probability existence and characterization theorem which includes MH-like kernel couplings as a
special case.

Looking forward, we believe that our results can aid in the design of new and more efficient methods
based on couplings of the MH algorithm. We also expect our results to support the theoretical
analysis of kernel couplings for this broad class of discrete-time Markov chains. For example, it
may be possible to derive meeting time bounds or information on the spectrum of $\bp$ based on
underlying data on $\bq$ and $\bb$, using a version of  the drift and minorization arguments of
Rosenthal, 1995, Rosenthal, 2002 or the techniques of
Atchadé and Perron, 2007. A better understanding of the set of kernel couplings may also support
optimization arguments like those of Boyd et al., 2004, Boyd et al., 2006, Boyd et al., 2009.

This work represents a step toward relating the properties of $\Gamma(P,P)$ and $\Gmax(P,P)$ to
those of $\Gamma(Q,Q)$ and the associated acceptance couplings. As noted above, Markovian couplings
which are efficient in the sense of Aldous, 1983 are well understood in
only a few special cases. Beyond that, only a few additional bounds exist on the efficiency of
Markovian couplings [Burdzy and Kendall, 2000]. These questions remain largely open for MH-like
chains. A clear understanding of the set of Markovian couplings will make it possible to identify
better couplings for use in practice and settle the question of how efficient couplings can be for
this important case.

§.§.§ Acknowledgments

The authors would like to thank Pierre E. Jacob, Persi Diaconis, and Qian Qin for helpful comments. John O'Leary gratefully acknowledges support by the National Science Foundation through grant

[Aldous, 1983]
D. Aldous.
Random walks on finite groups and rapidly mixing Markov chains.
In Séminaire de Probabilités XVII 1981/82, pages
243–297. Springer, 1983.

[Aldous and Fill, 1995]
D. Aldous and J. Fill.
Reversible Markov Chains and Random Walks on Graphs.
Berkeley, 1995.

[Aliprantis and Burkinshaw, 1998]
C. D. Aliprantis and O. Burkinshaw.
Principles of Real Analysis.
Gulf Professional Publishing, 1998.

[Andrieu et al., 2010]
C. Andrieu, A. Doucet, and R. Holenstein.
Particle Markov chain Monte Carlo methods.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 720 (3):0 269–342, 2010.

[Andrieu et al., 2020]
C. Andrieu, A. Lee, and S. Livingstone.
A general perspective on the Metropolis-Hastings kernel.
arXiv preprint arXiv:2012.14881, 2020.

[Atchadé and Perron, 2007]
Y. F. Atchadé and F. Perron.
On the geometric ergodicity of Metropolis-Hastings algorithms.
Statistics, 410 (1):0 77–84, 2007.

[Athreya and Ney, 1978]
K. B. Athreya and P. Ney.
A new approach to the limit theory of recurrent Markov chains.
Transactions of the American Mathematical Society,
245:0 493–501, 1978.

[Banerjee and Kendall, 2017]
S. Banerjee and W. S. Kendall.
Rigidity for Markovian maximal couplings of elliptic diffusions.
Probability Theory and Related Fields, 1680
(1-2):0 55–112, 2017.

[Barker, 1965]
A. A. Barker.
Monte Carlo calculations of the radial distribution functions
for a proton–electron plasma.
Australian Journal of Physics, 180 (2):0
119–134, 1965.

[Birkhoff, 1946]
G. Birkhoff.
Three observations on linear algebra.
Univ. Nac. Tacuman, Rev. Ser. A, 5:0 147–151, 1946.

[Biswas et al., 2019]
N. Biswas, P. E. Jacob, and P. Vanetti.
Estimating convergence of Markov chains with L-lag couplings.
In Advances in Neural Information Processing Systems, pages
7391–7401, 2019.

[Böttcher, 2017]
B. Böttcher.
Markovian maximal coupling of Markov processes.
arXiv preprint arXiv:1710.09654, 2017.

[Bou-Rabee et al., 2020]
N. Bou-Rabee, A. Eberle, and R. Zimmer.
Coupling and convergence for Hamiltonian Monte Carlo.
Annals of Applied Probability, 300 (3):0
1209–1250, 2020.

[Boyd et al., 2004]
S. Boyd, P. Diaconis, and L. Xiao.
Fastest mixing Markov chain on a graph.
SIAM Review, 460 (4):0 667–689, 2004.

[Boyd et al., 2006]
S. Boyd, P. Diaconis, J. Sun, and L. Xiao.
Fastest mixing Markov chain on a path.
The American Mathematical Monthly, 1130 (1):0
70–74, 2006.

[Boyd et al., 2009]
S. Boyd, P. Diaconis, P. Parrilo, and L. Xiao.
Fastest mixing Markov chain on graphs with symmetries.
SIAM Journal on Optimization, 200 (2):0
792–819, 2009.

[Burdzy and Kendall, 2000]
K. Burdzy and W. S. Kendall.
Efficient Markovian couplings: examples and counterexamples.
Annals of Applied Probability, pages 362–409, 2000.

[Connor and Jacka, 2008]
S. Connor and S. Jacka.
Optimal co-adapted coupling for the symmetric random walk on the
Journal of Applied Probability, 450 (3):0
703–713, 2008.

[Doeblin, 1938]
W. Doeblin.
Exposé de la théorie des chaînes simples constantes de
Markov à un nombre fini d'états.
Mathématique de l'Union Interbalkanique, 20
(77-105):0 78–80, 1938.

[Douc et al., 2018]
R. Douc, E. Moulines, P. Priouret, and P. Soulier.
Markov Chains.
Springer, 2018.

[Dshalalow, 2012]
J. H. Dshalalow.
Foundations of Abstract Analysis.
Springer Science & Business Media, 2012.

[Duane et al., 1987]
S. Duane, A. D. Kennedy, B. J. Pendleton, and D. Roweth.
Hybrid Monte Carlo.
Physics Letters B, 1950 (2):0 216–222, 1987.

[Dudley, 2002]
R. Dudley.
Real Analysis and Probability.
Cambridge University Press, New York, 2002.

[Ernst et al., 2019]
P. A. Ernst, W. S. Kendall, G. O. Roberts, and J. S. Rosenthal.
MEXIT: Maximal un-coupling times for stochastic processes.
Stochastic Processes and their Applications, 1290
(2):0 355–380, 2019.

[Fill, 1997]
J. A. Fill.
An interruptible algorithm for perfect sampling via Markov chains.
In Proceedings of the Twenty-Ninth Annual ACM Symposium on
Theory of Computing, pages 688–695, 1997.

[Flegal and Herbei, 2012]
J. M. Flegal and R. Herbei.
Exact sampling for intractable probability distributions via a
Bernoulli factory.
Electronic Journal of Statistics, 6:0 10–37, 2012.

[Gelman et al., 2010]
A. Gelman, S. Brooks, G. Jones, and X. Meng.
Handbook of Markov Chain Monte Carlo: Methods and
Chapman & Hall/CRC handbooks of modern statistical methods. CRC
Press, 2010.
ISBN 9781420079418.

[Glynn and Rhee, 2014]
P. W. Glynn and C.-H. Rhee.
Exact estimation for Markov chain equilibrium expectations.
Journal of Applied Probability, 510 (A):0
377–389, 2014.

[Goldstein, 1979]
S. Goldstein.
Maximal coupling.
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte
Gebiete, 460 (2):0 193–204, 1979.

[Goodman and Lin, 2009]
J. B. Goodman and K. K. Lin.
Coupling control variates for Markov chain Monte Carlo.
Journal of Computational Physics, 2280 (19):0
7127–7136, 2009.

[Griffeath, 1975]
D. Griffeath.
A maximal coupling for Markov chains.
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte
Gebiete, 310 (2):0 95–106, 1975.

[Harris, 1955]
T. E. Harris.
On chains of infinite order.
Pacific Journal of Mathematics, 50 (Suppl.
1):0 707–724, 1955.

[Hastings, 1970]
W. K. Hastings.
Monte Carlo sampling methods using Markov chains and their
Biometrika, 570 (1):0 97–109, 1970.

[Hayes and Sinclair, 2005]
T. P. Hayes and A. Sinclair.
A general lower bound for mixing of single-site dynamics on graphs.
In 46th Annual IEEE Symposium on Foundations of Computer
Science (FOCS'05), pages 511–520. IEEE, 2005.

[Hayes and Vigoda, 2003]
T. P. Hayes and E. Vigoda.
A non-markovian coupling for randomly sampling colorings.
In 44th Annual IEEE Symposium on Foundations of Computer
Science, 2003. Proceedings., pages 618–627. IEEE, 2003.

[Heng and Jacob, 2019]
J. Heng and P. E. Jacob.
Unbiased Hamiltonian Monte Carlo with couplings.
Biometrika, 1060 (2):0 287–302, 2019.

[Hsu and Sturm, 2013]
E. P. Hsu and K.-T. Sturm.
Maximal coupling of Euclidean Brownian motions.
Communications in Mathematics and Statistics, 10
(1):0 93–104, 2013.

[Jacob et al., 2020]
P. E. Jacob, J. O'Leary, and Y. F. Atchadé.
Unbiased Markov chain Monte Carlo methods with couplings.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 820 (3):0 543–600, 2020.

[Johnson, 1996]
V. E. Johnson.
Studying convergence of Markov chain Monte Carlo algorithms
using coupled sample paths.
Journal of the American Statistical Association, 910
(433):0 154–166, 1996.

[Johnson, 1998]
V. E. Johnson.
A coupling-regeneration scheme for diagnosing convergence in Markov
chain Monte Carlo algorithms.
Journal of the American Statistical Association, 930
(441):0 238–248, 1998.

[Jones and Hobert, 2001]
G. L. Jones and J. P. Hobert.
Honest exploration of intractable probability distributions via
Markov chain Monte Carlo.
Statistical Science, pages 312–334, 2001.

[Kartashov and Golomozyi, 2013]
M. Kartashov and V. Golomozyi.
Maximal coupling procedure and stability of discrete Markov chains.
Theory of Probability and Mathematical Statistics,
87:0 65–78, 2013.

[Kendall, 2015]
W. S. Kendall.
Coupling, local times, immersions.
Bernoulli, 210 (2):0 1014–1046, 2015.

[Kendall, 2017]
W. S. Kendall.
Lectures on probabilistic coupling, 2017.

[Kuwada, 2009]
K. Kuwada.
Characterization of maximal Markovian couplings for diffusion
Electronic Journal of Probability, 14:0 633–662,

[Levin et al., 2017]
D. A. Levin, Y. Peres, and E. L. Wilmer.
Markov Chains and Mixing Times, volume 107.
American Mathematical Soc., 2017.
ISBN 1470429624.

[Lindvall, 1992]
T. Lindvall.
Lectures on the Coupling Method.
Dover Books on Mathematics, 1992.
ISBN 0-486-42145-7.

[Metropolis et al., 1953]
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller.
Equation of state calculations by fast computing machines.
The Journal of Chemical Physics, 210 (6):0
1087–1092, 1953.

[Meyn and Tweedie, 2012]
S. P. Meyn and R. L. Tweedie.
Markov chains and stochastic stability.
Springer Science & Business Media, 2012.

[Middleton et al., 2019]
L. Middleton, G. Deligiannidis, A. Doucet, and P. E. Jacob.
Unbiased smoothing using particle independent
In K. Chaudhuri and M. Sugiyama, editors, Proceedings of
Machine Learning Research, volume 89, pages 2378–2387. PMLR, 16–18 Apr

[Middleton et al., 2020]
L. Middleton, G. Deligiannidis, A. Doucet, and P. E. Jacob.
Unbiased Markov chain Monte Carlo for intractable target
Electronic Journal of Statistics, 140 (2):0
2842–2891, 2020.
ISSN 1935-7524.

[Neal and Pinto, 2001]
R. Neal and R. Pinto.
Improving Markov chain Monte Carlo estimators by coupling to an
approximating chain.
Technical report, Department of Statistics, University of Toronto,

[Neal, 1993]
R. M. Neal.
Bayesian learning via stochastic dynamics.
In Advances in Neural Information Processing Systems, pages
475–482, 1993.

[Neal, 1999]
R. M. Neal.
Circularly-coupled Markov chain sampling.
Technical report, Department of Statistics, University of Toronto,

[Neal, 2011]
R. M. Neal.
MCMC using Hamiltonian dynamics.
Handbook of Markov Chain Monte Carlo, 20
(11):0 2, 2011.

[Nummelin, 1978]
E. Nummelin.
Uniform and ratio limit theorems for Markov renewal and
semi-regenerative processes on a general state space.
Annales de l'IHP Probabilités et statistiques, 140
(2):0 119–143, 1978.

[O'Leary et al., 2021]
J. O'Leary, G. Wang, and P. E. Jacob.
Maximal couplings of the metropolis-hastings algorithm.
In Proceedings of The 24th International Conference on
Artificial Intelligence and Statistics, volume 130 of Proceedings of
Machine Learning Research, pages 1225–1233. PMLR, 2021.

[Pillai and Smith, 2019]
N. S. Pillai and A. Smith.
Mixing times for a constrained Ising process on the two-dimensional
torus at low density.
In Annales de l'Institut Henri Poincaré, Probabilités
et Statistiques, volume 55, pages 1649–1678. Institut Henri Poincaré,

[Piponi et al., 2020]
D. Piponi, M. Hoffman, and P. Sountsov.
Hamiltonian Monte Carlo swindles.
Proceedings of Machine Learning Research, 108:0
3774–3783, 26–28 Aug 2020.

[Pitman, 1976]
J. Pitman.
On coupling of Markov chains.
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte
Gebiete, 350 (4):0 315–322, 1976.

[Propp and Wilson, 1996]
J. G. Propp and D. B. Wilson.
Exact sampling with coupled Markov chains and applications to
statistical mechanics.
Random Structures and Algorithms, 90 (1-2):0
223–252, 1996.

[Qin and Hobert, 2021]
Q. Qin and J. P. Hobert.
Wasserstein-based methods for convergence complexity analysis of
MCMC with applications.
The Annals of Applied Probability, 2021.

[Reutter and Johnson, 1995]
A. Reutter and V. E. Johnson.
General strategies for assessing convergence of MCMC algorithms
using coupled sample paths.
Technical report, Institute of Statistics and Decision Sciences, Duke
University, 1995.

[Roberts and Rosenthal, 1998]
G. O. Roberts and J. S. Rosenthal.
Optimal scaling of discrete approximations to Langevin diffusions.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 600 (1):0 255–268, 1998.

[Roberts and Tweedie, 1996]
G. O. Roberts and R. L. Tweedie.
Exponential convergence of Langevin distributions and their
discrete approximations.
Bernoulli, 20 (4):0 341–363, 1996.

[Rosenthal, 1995]
J. S. Rosenthal.
Minorization conditions and convergence rates for Markov chain Monte
Journal of the American Statistical Association, 900
(430):0 558–566, 1995.

[Rosenthal, 1996]
J. S. Rosenthal.
Analysis of the Gibbs sampler for a model related to
James-Stein estimators.
Statistics and Computing, 60 (3):0 269–275,

[Rosenthal, 2002]
J. S. Rosenthal.
Quantitative convergence rates of Markov chains: A simple account.
Electronic Communications in Probability, 7:0
123–128, 2002.