3.1. Preliminaries

As before, let S be a Polish space. A closed partial order ‘⪯’ on S is a partial order ‘⪯’ such that its graph

\begin{align*}\mathbb G \,:= \{{(x, y) \in S \times S}{x \preceq y}\}\end{align*}

is closed in the product topology. Henceforth, a partially ordered Polish space is any such pair (S, ⪯), where S is nonempty and Polish, and ‘⪯’ is a closed partial order on S. When no confusion arises, we denote it simply by S. The partial order is assumed to be closed in the theory developed below because we build a metric over Borel probability measures that depends on this partial order and closedness of the order is required to show that the metric is complete.

For such a space S, we call I ⊂ S increasing if x ∈ I and x ⪯ y implies that y ∈ I. We call h: S → ℝ increasing if x ⪯ y implies that h(x) ≤ h(y). We let $i\cal B,\,i\cal O$, and $i\mathfrak C$ denote the increasing Borel, open, and closed sets, respectively, while ibS is the increasing functions in bS. In addition,

• • iH := H ∩ ibS = {h ∈ ibS: − 1 ≤ h ≤ 1}, and

• • iH ₀ := H ₀ ∩ ibS = {h ∈ ibS: 0 ≤ h ≤ 1}.

If $B \in \cal B$ then i(B) is all y ∈ S such that x ⪯ y for some x ∈ B, while d(B) is all y ∈ S such that y ⪯x for some x ∈ B. Given μ and ν in $\cal M$, we say that μ is stochastically dominated by ν and write μ ⪯_sd ν if μ(S) = ν(S) and μ(I) ≤ ν(I) for all $I \in i\cal B$. Equivalently, μ(S) = ν(S) and μ(h) ≤ ν(h) for all h in iH or iH ₀. See [Reference Kamae and Krengel18].

One important partial order on S is the identity order, where x ⪯ y if and only if x = y. Then $i\cal B = \cal B$, ibS = bS, iH = H, iH ₀ = H ₀, and μ ⪯_sd ν if and only if μ = ν.

Lemma 3.1. If $\lambda \in \cal M_s$ then $\sup_{I \in i\cal B} \lambda(I) = \sup_{h \in iH_0} \lambda(h)$ and

(3.1)\begin{align}\label{eq:cfs2} \sup_{h \in iH} |\lambda(h)| = \max \Big\{\sup_{h \in iH} \lambda(h),\; \sup_{h \in iH} (-\lambda)(h) \Big\}\!.\\[-12pt]\nonumber \end{align}

The proof is given in Appendix A.1. We can easily check that

(3.2)\begin{align}\label{eq:chho}\lambda \in \cal M_s \quad\text{and}\quad \lambda(S) = 0 \quad \Rightarrow \quad \sup_{h \in iH} \lambda(h) = 2 \sup_{h \in iH_0} \lambda(h). \end{align}

3.2. Definition of ordered affinity

For each pair $ (\mu, \nu) \in {\cal M} \times \cal M$, let

\begin{align*} {\Phi(\mu, \nu) \,:= \{ {(\mu', \nu') \in \cal M \times \cal M }: {\mu' \leq \mu,\, \nu' \leq \nu,\, \mu' {\preceq_{sd}} \nu'}\}}.\end{align*}

We call Φ(μ, ν) the set of ordered component pairs for (μ, ν). Here ‘ordered’ means ordered by stochastic dominance. The set of ordered component pairs is always nonempty, since (μ ∧ ν, μ ∧ ν) is an element of Φ(μ, ν).

Example 3.2. Given Bernoulli distributions μ = (δ ₁ + δ ₂)/2 and ν = (δ ₀ + δ ₁)/2, we have (μ′, ν′) ∈ Φ (μ, ν) when μ′= ν′= δ ₁/2.

We call an ordered component pair (μ′, ν′) ∈ Φ (μ, ν) a maximal ordered component pair if it has greater mass than all others; that is, if

\begin{align*} \mu''(S) \leq \mu'(S) \quad \text{for all } (\mu'', \nu'') \in \Phi(\mu, \nu). \end{align*}

(We can restate this by replacing μ′(S) and μ″(S) with ν′(S) and ν″(S), respectively, since the mass of ordered component pairs is equal by the definition of stochastic dominance.) We let Φ^∗(μ, ν) denote the set of maximal ordered component pairs for (μ, ν). Thus, if

(3.3)\begin{align}\label{eq:dsig}{ \alpha_O(\mu, \nu)\,:= {\rm sup} \{ {\mu'(S) }{ (\mu', \nu') \in \Phi(\mu, \nu) }\}},\end{align}

then

\begin{align*}{\Phi^*(\mu, \nu)= \{{(\mu', \nu') \in \Phi(\mu, \nu)}{\mu'(S) = \alpha_O(\mu, \nu)}\}.}\end{align*}

Using the Polish space assumption, one can show that maximal ordered component pairs always exist.

The value α_O(μ, ν) defined in (3.3) gives the mass of the maximal ordered component pair. We call it the ordered affinity from μ to ν. On an intuitive level, we can think of α_O(μ, ν) as the ‘degree’ to which μ is dominated by ν in the sense of stochastic dominance. Since (μ ⊥ ν, μ ⊥ ν) is an ordered component pair for (μ, ν), we have

(3.4)\begin{align}\label{eq:aldbal} 0 \leq \alpha(\mu, \nu) \leq \alpha_O(\mu, \nu),\end{align}

where α(μ, ν) is the standard affinity defined in Section 2. In fact, α_O(μ, ν) generalizes the standard the notion of affinity by extending it to arbitrary partial orders, as shown in the next lemma.

3.3. Properties of ordered affinity

Let us list some elementary properties of α_O. The following list should be compared with Lemma 2.1. It shows that analogous results hold for α_O as hold for α. (Lemma 2.1 is in fact a special case of Lemma 3.3 with the partial order set to the identity order.)

Lemma 3.3. For all ${ (\mu, \nu) \in \cal M \times \cal M}$, we have

1. (a) 0 ≤ α_O(μ, ν) ≤ min{μ(S), ν(S)},

2. (b) α_O(μ, ν) = μ(S) = ν(S) if and only if μ⪯_sd ν, and

3. (c) cα_O(μ, ν) = α_O(cμ, cν) whenever c ≥ 0.

Proof. Fix ${ (\mu, \nu) \in \cal M \times \cal M}$. Claim (a) follows directly from the definitions. Regarding claim (b), suppose first that μ⪯_sd ν. Then (μ, ν) ∈ Φ(μ, ν) and, hence, α_O(μ, ν) = μ(S). Conversely, if α_O(μ, ν) = μ(S) then, since the only component μ′≤ μ with μ′(S) = μ(S) is μ itself, we must have (μ, ν′) ∈ Φ(μ, ν′) for some ν′≤ ν with μ⪯_sd ν′. But then μ(I) ≤ ν′(I) ≤ ν(I) for any $I \in i\cal B$. Hence, μ⪯_sdν.

Claim (c) is trivial if c = 0, so suppose instead that c > 0. Fix (μ′, ν′) ∈ Φ(μ, ν) such that α_O(μ, ν) = μ′(S). It is clear that (cμ′, cν′) ∈ Φ(cμ, cν), implying that

(3.5)\begin{align} \label{eq:cin} c \alpha_O(\mu, \nu) = c \mu'(S) \leq \alpha_O(c\mu, c\nu). \end{align}

For reverse inequality, we can apply (3.5) again to get

\begin{align*} \alpha_O(c\mu, c\nu) = c \left(\frac{1}{c}\right) \alpha_O(c\mu, c\nu) \leq c \alpha_O(\mu, \nu).\\[-44pt] \end{align*}

3.4. Equivalent representations

In (2.2) we noted that the affinity between two measures has several alternative representations. In our setting these results generalize as follows.

Theorem 3.1. For all ${(\mu, \nu) \in \cal P \times \cal P}$, we have

(3.6)\begin{align}\label{eq:affco}\alpha_O(\mu, \nu)= 1 - \sup_{I \in i\cal B} \{ \mu(I) - \nu(I) \}= \max_{(X, Y) \in \cal C(\mu, \nu)} \mathbb P\{ X \preceq Y \}.\end{align}

Evidently (2.2) is a special case of (3.6) because (3.6) reduces to (2.2) when ‘⪯’ is set to equality. For example, when ‘⪯’ is equality,

$$\mathop {\sup }\limits_{I \in i{\cal B}} \{ \mu (I) - \nu (I)\} = \mathop {\sup }\limits_{B \in {\cal B}} \{ \mu (B) - \nu (B)\} = \mathop {\sup }\limits_{B \in {\cal B}} |\mu (B) - \nu (B)|,$$

where the last step is from (2.1). Note also that, as shown in the proof of Theorem 3.1, the supremum can also be written in terms of the open increasing sets i𝒪 or the closed decreasing sets $d\mathfrak C$. In particular,

\begin{align*} \sup_{I \in i\cal B} \{ \mu(I) - \nu(I) \} = \sup_{I \in i\cal O} \{ \mu(I) - \nu(I) \} = \sup_{D \in d\mathfrak C} \{ \nu(D) - \mu(D) \}.\end{align*}

One of the assertions of Theorem 3.1 is the existence of a coupling $ (X, Y) \in \cal C(\mu, \nu)$ attaining ℙ{X ⪯ Y} = α_O (μ, ν). Let us refer to any such coupling as an order maximal coupling for (μ, ν).

Example 3.3. For (x, y) ∈ S × S, we have

\begin{align*} \alpha_O(\delta_x, \delta_y) = {\bf 1}\{x \preceq y\} = {\bf 1}_{\mathbb G}(x, y),\end{align*}

as can easily be verified from the definition or either of the alternative representations in (3.6). The map $ (x, y) \mapsto {\bf 1}_{\mathbb G}(x, y)$ is measurable due to the Polish assumption. As a result, for any $ (X, Y) \in \cal C(\mu, \nu)$, we have

\begin{align*} \mathbb E \alpha_O(\delta_X, \delta_Y) = \mathbb P\{X \preceq Y\} \leq \alpha_O(\mu, \nu),\end{align*}

with equality when (X, Y) is an order maximal coupling.

3.5. Comments on Theorem 3.1

The existence of an order maximal coupling shown in Theorem 3.1 implies two well-known results that are usually treated separately. One is the Nachbin–Strassen theorem (see, e.g. Theorem 1 of [Reference Kamae, Krengel and O’Brien19] or Chapter IV of [Reference Lindvall22]), which states the existence of a coupling $ (X, Y) \in \cal C(\mu, \nu) $ attaining ℙ{X ⪯ Y} = 1 whenever μ⪯_sdν. The existence of an order maximal coupling for each (μ, ν) in $\cal P \times \cal P$ implies this statement, since, under the hypothesis that μ⪯_sdν, we also have α_O(μ, ν) = 1. Hence, any order maximal coupling satisfies ℙ{X ⪯ Y} = 1.

The other familiar result implied by the existence of an order maximal coupling is the existence of a maximal coupling in the standard sense (see the discussion of maximal couplings after (2.2) and the result on page 19 of [Reference Lindvall22]). Indeed, if we take ‘⪯’ to be the identity order then (3.6) reduces to (2.2), as already discussed.

4.1. Connection to other modes of convergence

As well as total variation, the metric γ is closely related to the so-called Bhattacharya metric, which is given by

(4.4)\begin{align} \label{eq:bhm} \beta(\mu, \nu) \,:\!= \sup_{h \in iH} |\mu(h) - \nu(h)| . \end{align}

See [Reference Bhattacharya and Lee1] and [Reference Chakraborty and Rao3]. (In [Reference Chakraborty and Rao3] the metric is defined by taking the supremum over iH ₀ rather than iH, but the two definitions differ only by a positive scalar.) The Bhattacharya metric can be thought of as an alternative way to generalize total variation distance, in the sense that, like γ, the metric β reduces to total variation distance when ‘⪯’ is the identity order (since iH equals H under this order). From (3.1) we have

\begin{align*} \label{eq:cfsi} \frac{1}{2} \Big[ \sup_{h \in iH} \lambda(h) +\sup_{h \in iH} (-\lambda)(h) \Big] \leq \sup_{h \in iH} |\lambda(h)| \leq \sup_{h \in iH} \lambda(h) + \sup_{h \in iH} (-\lambda)(h), \end{align*}

and from this and (4.2) we have

(4.5)\begin{align} \label{eq:em} \gamma(\mu, \nu) \leq \beta(\mu, \nu) \leq 2 \gamma(\mu, \nu). \end{align}

Hence, β and γ are equivalent metrics.

The metric γ is also connected to the Wasserstein metric ([Reference Gibbs and Su12], [Reference Givens and Shortt13]). If ρ metrizes the topology on S then the Wasserstein distance between probability measures μ and ν is

\begin{align*} w(\mu, \nu) \,:\!= \inf_{(X, Y) \in \cal C(\mu, \nu)} \mathbb E \, \rho(X, Y) .\end{align*}

The total ordered variation metric can be compared as follows. Consider the ‘directed semimetric’ $\hat \rho(x, y) \,:= \bf 1\{x {\npreceq} y\}$. In view of (3.6) we have

\begin{align*} \gamma(\mu, \nu) = \inf_{(X, Y) \in \cal C(\mu, \nu)} \mathbb E \, \hat \rho(X, Y) + \inf_{(X, Y) \in \cal C(\mu, \nu)} \mathbb E \, \hat \rho(Y, X) .\end{align*}

Thus, γ (μ, ν) is found by summing two partial, ‘directed Wasserstein deviations’. Summing the two directed differences from opposite directions yields a metric.

4.2. Completeness

To obtain completeness of ($\cal P,\,\gamma$), we adopt the following additional assumption, which is satisfied if, say, compact sets are order bounded (i.e. lie in order intervals) and order intervals are compact. (For example, ℝⁿ with the usual pointwise partial order has this property.)

5.1. Order affinity and monotone Markov kernels

Let S be a Polish space partially ordered by ‘⪯’. A Markov kernel P is called monotone if Ph ∈ ibS ₀ whenever h ∈ ibS ₁. An equivalent condition is that μP ⪯_sd νP whenever μ ⪯_sd ν; or just P(x, ·) ⪯_sd P(y, ·) whenever x ⪯ y. It is well known (see, e.g. Proposition 1 of [Reference Kamae, Krengel and O’Brien19]) that if μ ⪯_sd ν and P is monotone, then μ ⊗ P ⪯ _sd ν ⊗ P. Note that, when ‘⪯’ is the identity order, every Markov kernel is monotone.

Lemma 5.1. If P is a monotone Markov kernel from S ₀ to S ₁ and μ, μ′, ν, and ν′are probabilities in $\cal P_0$, then

\begin{align*} \mu' {\preceq_{sd}} \mu \quad and \quad \nu {\preceq_{sd}} \nu' \quad \Rightarrow \quad \alpha_O(\mu P, \nu P) \leq \alpha_O(\mu' P, \nu' P). \end{align*}

Proof. Let P, μ, μ′, ν, and ν′ have the stated properties. In view of the equivalently representation in (3.6), the claim will be established if

\begin{align*} \sup_{I \in i\cal B} \{ (\mu P)(I) - (\nu P)(I) \} \geq \sup_{I \in i\cal B} \{ (\mu' P)(I) - (\nu' P)(I) \}.\end{align*}

This holds by the monotonicity of P and the order of μ, μ′, ν, and ν′.

Lemma 5.2. If P is a monotone Markov kernel from S ₀ to S ₁, then

\begin{align*} \alpha_O(\mu P, \nu P) \geq \alpha_O(\mu, \nu) \quad {for\; any\; \mu, \nu \; in \;\cal P_0}.\end{align*}

Proof. Fix μ, ν in $\cal P_0$, and let ($\hat \mu, \hat \nu$) be a maximal ordered component pair for (μ, ν). From monotonicity of P and the fact the Markov kernels preserve the mass of measures, it is clear that $ (\hat \mu P, \hat \nu P)$) is an ordered component pair for (μP, νP). Hence,

\begin{align*} \alpha_O(\mu P, \nu P) \geq (\hat \mu P)(S) = \hat \mu(S) = \alpha_O(\mu, \nu).\\[-35pt] \end{align*}

On the other hand, for the joint distribution, the ordered affinity of the initial pair is preserved.

Lemma 5.3. If P is a monotone Markov kernel from S ₀ to S ₁, then

\begin{align*} \alpha_O(\mu \otimes P, \nu \otimes P) = \alpha_O(\mu, \nu) \quad {for\; any\; \mu,\nu\; in \;\cal P_0}.\end{align*}

Proof. Fix μ, ν in $\cal P_0$, and let (X ₀, X ₁) and (Y ₀, Y ₁) be random pairs with distributions μ ⊗ P and ν ⊗ P, respectively. We have

\begin{align*} \mathbb P\{ (X_0, X_1) \preceq (Y_0, Y_1) \} \leq \mathbb P\{ X_0 \preceq Y_0 \} \leq \alpha_O(\mu, \nu). \end{align*}

Taking the supremum over all couplings in $\cal C(\mu \otimes P, \nu \otimes P)$ shows that α_O(μ ⊗ P, ν ⊗ P) is dominated by α_O(μ, ν).

To see the reverse inequality, let ($\hat \mu, \hat \nu$) be a maximal ordered component pair for (μ, ν). Monotonicity of P now gives $\hat \mu \otimes P {\preceq_{sd}} \hat \nu \otimes P$. Using this and the fact the Markov kernels preserve the mass of measures, we see that ($\hat \mu \otimes P, \hat \nu \otimes P$) is an ordered component pair for (μ ⊗ P, ν ⊗ P). Hence,

\begin{align*} \alpha_O(\mu P, \nu P) \geq (\hat \mu \otimes P)(S_0 \times S_1) = \hat \mu(S_0) = \alpha_O(\mu, \nu).\\[-32pt] \end{align*}

5.2. Monotone Markov chains

Given μ ∈ 𝒫 and Markov kernel P on S, a stochastic process {X_t}_t≥0 taking values in $S^{\infty} \,:\!= \times_{t=0}^\infty S$ will be called a Markov chain with initial distribution μ and kernel P if the distribution of {X_t} on S ^∞ is

\begin{align*} \boldsymbol Q_\mu \,:\!= \mu \otimes P \otimes P \otimes P \otimes \cdots\!.\end{align*}

(The meaning of the right-hand side is clarified in [Reference Lindvall22, Section III.8], [Reference Kamae, Krengel and O’Brien19, p. 903], and [Reference Meyn and Tweedie25, Section 3.4] for example.) If P is a monotone Markov kernel then (x, B) ↦ Q_x(B) := Q _{δ x}(B) is a monotone Markov kernel from S to S ^∞. See Propositions 1 and 2 of [Reference Kamae, Krengel and O’Brien19].

There are various useful results about representations of Markov chains that are ordered almost surely. One is that, if the initial conditions satisfy μ ⪯_sd ν and P is a monotone Markov kernel, then we can find Markov chains {X_t} and {Y_t} with initial distributions μ and ν and kernel P such that X_t ⪯ Y_t for all t almost surely. (See, e.g. Theorem 2 of [Reference Kamae, Krengel and O’Brien19].) This result can be generalized beyond the case where μ and ν are stochastically ordered, using the results presented above. For example, let μ and ν be arbitrary initial distributions and let P be monotone, so that Q_x is likewise monotone. By Lemma 5.3 we have

\begin{align*} \alpha_O(\boldsymbol Q_\mu, \boldsymbol Q_\nu) = \alpha_O(\mu \otimes \boldsymbol Q_x, \nu \otimes \boldsymbol Q_x) = \alpha_O(\mu, \nu).\end{align*}

In other words, the ordered affinity of the entire processes is given by the ordered affinity of the initial distributions. It now follows from Theorem 3.1 that there exist Markov chains {X_t} and {Y_t} with initial distributions μ and ν and Markov kernel P such that

\begin{align*} \mathbb P\{ X_t \preceq Y_t \text{ for all } t \geq 0\} = \alpha_O(\mu, \nu).\end{align*}

The standard result is a special case, since μ ⪯_sd ν implies that α_O(μ, ν) = 1, and, hence, the sequences are ordered almost surely.

5.3. Nonexpansiveness

It is well known that every Markov kernel is nonexpansive with respect to the total variation norm, so that

(5.1)\begin{align} \label{eq:netv} \| \mu P - \nu P \| \leq \| \mu - \nu \| \quad \text{for all } (\mu, \nu) \in \cal P \times \cal P. \end{align}

An analogous result is true for γ when P is monotone. That is,

(5.2)\begin{align} \label{eq:netov} \gamma(\mu P , \nu P ) \leq \gamma( \mu , \nu ) \quad \text{for all } (\mu, \nu) \in \cal P \times \cal P.\end{align}

The bound (5.2) follows directly from Lemma 5.2. Evidently (5.1) be recovered from (5.2) by setting ‘⪯’ to equality.

Nonexpansiveness is interesting partly in its own right (we apply it in proofs below) and partly because it suggests that, with some additional assumptions, we can strengthen it to contractiveness. We expand on this idea below.

5.4. An order coupling bound for Markov chains

Doeblin [Reference Doeblin7] established and exploited the coupling inequality

(5.3)\begin{align} \label{eq:d} \| \mu_t - \nu_t \| \leq 2 \, \mathbb P\{X_j \not= Y_j \text{ for any } j \leq t\} ,\end{align}

where μ_t and ν_t are the time t distributions of Markov chains {X_t} and {Y_t} generated by common Markov kernel P. Even when the state space is uncountable, the right-hand side of (5.3) can often be shown to converge to zero by manipulating the joint distribution of (X_j, Y_j) to increase the chance of a meeting ([Reference Doob9], [Reference Harris14], [Reference Lindvall22], [Reference Meyn and Tweedie25], [Reference Nummelin26], [Reference Orey27], [Reference Pitman28], [Reference Revuz31], [Reference Thorisson34]).

Consider the following generalization: given a monotone Markov kernel P on S and arbitrary $\mu, \nu \in \cal P$, we can construct Markov chains {X_t} and {Y_t} with common kernel P and respective initial conditions μ and ν such that

(5.4)\begin{align} \label{eq:do} \gamma( \mu_t, \nu_t) \leq \mathbb P\{X_j \npreceq Y_j \text{ for any } j \leq t\} + \mathbb P\{Y_j \npreceq X_j \text{ for any } j \leq t\}. \end{align}

This generalizes (5.3) because both the right- and left-hand sides of (5.4) reduce to (5.3) if we take $' \preceq '$ to be equality.

To prove (5.4), we need only show that

(5.5)\begin{align} \label{eq:ido} 1 - \alpha_O( \mu P^t, \nu P^t) \leq \mathbb P\{X_j \npreceq Y_j \text{ for any } j \leq t\},\end{align}

since, with (5.5) is established, we can reverse the roles of {X_t} and {Y_t} in (5.5) to obtain $1 - \alpha_O( \nu P^t, \mu P^t) \leq \mathbb P\{Y_j \npreceq X_j \;\text {for any}\; j \leq t\}$ and then add this inequality to (5.5) to produce (5.4).

If {X_t} and {Y_t} are Markov chains with kernel P and initial conditions μ and ν, then (3.6) yields α_O(μP^t, νP^t) ≥ ℙ{X_t ⪯ Y_t}. Therefore, we need only construct such chains with the additional property that

(5.6)\begin{align} \label{eq:oia} \mathbb P\{X_j \npreceq Y_j \text{ for any } j \leq t\} = \mathbb P\{X_t \npreceq Y_t\}.\end{align}

Intuitively, we can do so by using a ‘conditional’ version of the Nachbin–Strassen theorem, producing chains that, once ordered, remain ordered almost surely. This can be formalized as follows. By [Reference Machida and Shibakov23, Theorem 2.3], there exists a Markov kernel M on S × S such that $\mathbb G$ is absorbing for M (i.e. $M((x,y), \mathbb G) = 1$ for all (x, y) in $\mathbb G$),

\begin{align*} P(x, A) = M((x,y), \, A \times S) \quad \text{and} \quad P(y, B) = M((x,y), \, S \times B) \end{align*}

for all (x, y) ∈ S × S and all $A, B \in \cal B$. Given M, let η be a distribution on S × S with marginals μ and ν, let Q_η := η ⊗ M ⊗ M ⊗ · · · be the induced joint distribution, and let {(X_t, Y_t)} have distribution Q_η on (S × S)^∞. By construction, X_t has distribution μP^t and Y_t has distribution νP^t. Moreover, (5.6) is valid because $\mathbb G$ is absorbing for M, and, hence, $\mathbb P\{(X_j, Y_j) \notin \mathbb G $ for any $ j \leq t\} = \mathbb P\{(X_t, Y_t) \notin \mathbb G\}$.

5.5. Uniform ergodicity

Let S be a partially ordered Polish space satisfying Assumption 4.1, and let P be a monotone Markov kernel on S. A distribution π is called stationary for P if πP = π. Consider the value

(5.7)\begin{align} \label{eq:odob} \sigma(P) \,:\!= \inf_{(x, y) \in S \times S} \alpha_O(P_x, P_y) ,\end{align}

which can be understood as an order-theoretic extension of the Markov–Dobrushin coefficient of ergodicity ([Reference Dobrushin5], [Reference Seneta32]). It reduces to the usual notion when ‘⪯’ is equality.

Theorem 5.1. If P is monotone then

(5.8)\begin{align} \label{eq:fbod} \gamma(\mu P, \nu P) \leq (1 - \sigma(P)) \, \gamma(\mu, \nu) \quad {for\; all }\;(\mu, \nu) \in \cal P \times \cal P.\end{align}

Thus, strict positivity of σ(P) implies that μ ↦ μP is a contraction map on $ (\cal P, \gamma ) $. Moreover, in many settings, the bound in (5.8) cannot be improved upon, as we now see.

Lemma 5.4. If P is monotone, S is not a singleton, and any x, y in S have a lower bound in S, then,

(5.9)\begin{align} \label{eq:ev} {for \; all } \; \xi > \sigma(P),\;\;{there \; exists }\; \mu, \nu \in {\cal P} \;{such \; that }\;\gamma(\mu P, \nu P) > (1 - \xi) \gamma(\mu, \nu).\end{align}

The significance of Theorem 5.1 is summarized in the next corollary.

Corollary 5.1. Let P be monotone, and let S satisfy Assumption 4.1. If there exists an m ∈ ℕ such that σ(P^m) > 0, then P has a unique stationary distribution π in $\cal P$, and

(5.10)\begin{align} \label{eq:ifbod} \gamma(\mu P^t, \pi) \leq (1 - \sigma(P^m))^{{\lfloor t/m \rfloor}} \, \gamma(\mu, \pi)\quad {for \; all }\; \mu \in {\cal P}, t \geq 0.\end{align}

Here ⌊x⌋ is the largest n ∈ ℕ with n ≤ x.

Proof of Corollary 5.1. Let P and μ be as in the statement of the theorem. The existence of a fixed point of μ ↦ μP, and hence a stationary distribution $\pi \in \cal P$, follows from Theorem 5.1 applied to P^m, Banach’s contraction mapping theorem, and the completeness of ($\cal P$, γ) shown in Theorem 4.1. The bound in (5.10) follows from (5.8) applied to P^m and the nonexpansiveness of P in the metric γ (see (5.2)).

5.6. Applications from the introduction

Let us see how Corollary 5.1 can be used to show stability of the two models discussed in the Introduction, beginning with the monotone model in (1.1). The state space is S = [0, 1] with its standard order and all assumptions are as per the discussion immediately following (1.1). We let P be the corresponding Markov kernel and consider the following coupling of (P ₁, P ₀). Let W be a draw from the Bernoulli($\tfrac12$) distribution, and let V = 1 − W. Then P ₁ and P ₀ are respectively the distributions of

\begin{align*}X \,:\!= \frac{1 + W}{2}\quad \text{and} \quad Y \,:\!= \frac{0 + V}{2} = \frac{1 - W}{2}.\end{align*}

Since X ≤ Y if and only if W =0, we have, by Lemma 5.1 and (3.6),

\begin{align*} \alpha_O(P_x, P_y) \geq \alpha_O(P_1, P_0) \geq \mathbb P\{ X \preceq Y \} = \tfrac{1}{2} \end{align*}

for all x, y ∈ S. From the definition in (5.7) we then have $\sigma(P) \geq \tfrac12$, and globally stability in the γ metric follows from Corollary 5.1.

Next we turn to the inventory model in (1.2), with state space S = [0, K] and {W_t} an i.i.d. process satisfying ℙ{W_t ≥ w} > 0 for any real w. Let {X_t} and {Y_t} be generated by (1.2), with common shock sequence {W_t}, and respective initial conditions x, y in S. In view of (2.2), we have

$$\alpha ({P_x},{P_y}) \ge {\mathbb P \{ {X_1} = {Y_1}\}} \ge {\mathbb P \{{W_1} \ge K\}} = : \kappa > 0.$$

Letting ‘⪯’ be equality on S, we have α_O(P_x, P_y) = α(P_x, P_y) ≥ κ, and hence σ(P) ≥ κ. Globally stability in the γ metric follows from Corollary 5.1.

5.7. General applications

Next we show that Theorem 5.1 and in particular Corollary 5.1 cover as special cases two well-known results on Markov chain stability from the classical literature on one hand and the more recent monotone Markov chain literature on the other.

Consider first the standard notion of uniform ergodicity. A Markov kernel P on S is called uniformly ergodic if it has a stationary distribution π and $\sup_{x \in S} \| P_x^t - \pi \| \to 0$ as t → ∞. Uniform ergodicity was studied by Markov [Reference Markov24] in a countable state space, and by Doeblin [6], Yosida and Kakutani [Reference Yosida and Kakutani37], Doob [Reference Doob9], and many subsequent authors in a general state space. It is defined and reviewed in Chapter 16 of [Reference Meyn and Tweedie25]. One of the most familiar equivalent conditions for uniform ergodicity [Reference Meyn and Tweedie25, Theorem 16.0.2] is the existence of an m ∈ ℔ and a nontrivial $\phi \in \cal M$ such that $P^m_x \geq \phi$ for all x in S.

One can recover this result using Corollary 5.1. Take ‘⪯’ to be equality, in which case every Markov operator is monotone, γ is total variation distance, and Assumption 4.1 is always satisfied. Moreover, σ(P^m) reduces to the ordinary ergodicity coefficient of P^m, evaluated using the standard notion of affinity, and, hence,

\begin{align*} \sigma(P^m) = \inf_{(x, y) \in S \times S} \alpha(P^m_x, \, P^m_y) = \inf_{(x, y) \in S \times S} (P^m_x \wedge P^m_y) (S) \geq \phi(S) > 0.\end{align*}

Thus, all the conditions of Corollary 5.1 are satisfied, and

\begin{align*} \sup_{x \in S} \| P^t_x - \pi \| = \sup_{x \in S} \gamma( P^t_x \, , \, \pi) \leq 2 (1 - \sigma(P^m))^{{\lfloor t/m \rfloor}} \to 0 \quad\text{as } t \to \infty.\end{align*}

Now consider the setting of Bhattacharya and Lee [Reference Bhattacharya and Lee1], where S =ℝⁿ, ‘⪯’ is the usual pointwise partial order ‘≤’ for vectors, and {g_t} is a sequence of i.i.d. random maps from S to itself, generating {X_t} via X_t = g_t(X _t−1) = g_t o · · · o g ₁(X ₀). The corresponding Markov kernel is P(x, B) = ℙ{g ₁ (x) ∈ B}. The random maps are assumed to be order preserving on S, so that P is monotone. Bhattacharya and Lee used a ‘splitting condition’, which assumes existence of a x̄ ∈ S and m ∈ ℕ such that

1. (a) s ₁ := ℙ{g_m o · · · o g ₁(y) ≤ x̄ for all y ∈ S} > 0, and

2. (b) s ₂ := ℙ{g_m o · · · o g ₁(y) ≥ x̄ for all y ∈ S} > 0.

Under these assumptions, they show that $\sup_{x \in S} \beta(P^t_x, \, \pi)$ converges to zero exponentially fast in t, where β is the Bhattacharya metric introduced in (4.4). This finding extends earlier results by Dubins and Freedman [Reference Dubins and Freedman10] and Yahav [Reference Yahav36] to multiple dimensions.

This result can be obtained as a special case of Corollary 5.1. Certainly S is a partially ordered Polish space and Assumption 4.1 is satisfied. Moreover, the ordered ergodicity coefficient σ(P^m) is strictly positive. To see this, suppose that the splitting condition is satisfied at m ∈ ℕ. Pick any x, y ∈ S, and let {X_t} and {Y_t} be independent copies of the Markov chain, starting at x and y, respectively. We have

\begin{align*} \sigma(P^m) \geq \mathbb P\{X_m \leq Y_m\} \geq \mathbb P\{X_m \leq \bar x \leq Y_m\} = \mathbb P\{X_m \leq \bar x \} \mathbb P\{\bar x \leq Y_m\} \geq s_1 s_2.\end{align*}

The last term is strictly positive by assumption. Hence, all the conditions of Corollary 5.1 are satisfied, a unique stationary distribution π exists, and $\sup_{x \in S} \gamma(P^t_x, \, \pi)$ converges to zero exponentially fast in t. We showed in (4.5) that β ≤ 2γ, so the same convergence holds for the Bhattacharya metric.

We can also recover a related convergence result due to Hopenhayn and Prescott [Reference Hopenhayn and Prescott16, Theorem 2] that is routinely applied to stochastic stability problems in economics. They assumed that S is a compact metric space with a closed partial order, and a least element a and greatest element b. They supposed that P is monotone, and that there exists an x̄ in S and an m ∈ ℕ such that

(5.11)\begin{align} \label{eq:mmc} P^m(a, [\bar x, b]) > 0 \quad \text{and} \quad P^m(b, [a, \bar x]) > 0.\end{align}

In this setting, they showed that P has a unique stationary distribution π and $\mu P^t \buildrel {\rm w} \over \longrightarrow \pi$ for any $\mu \in \cal P$ as t → ∞. This result can be obtained from Corollary 5.1. Under the stated assumptions, S is Polish and Assumption 4.1 is satisfied. The coefficient σ(P^m) is strictly positive because, if we let {X_t} and {Y_t} be independent copies of the Markov chain starting at b and a, respectively, then, since $ (X_m, Y_m) \in {\cal C}(P^m_b, P^m_a)$, we have

\begin{align*} \alpha_O(P^m_b, P^m_a) \geq \mathbb P\{X_m \leq Y_m\} \geq \mathbb P\{X_m \leq \bar x \leq Y_m\} = \mathbb P\{X_m \leq \bar x \} \mathbb P\{\bar x \leq Y_m\}.\end{align*}

The last term is strictly positive by (5.11). Positivity of σ(P^m) now follows from Lemma 5.1, since a ⪯ x, y ⪯ b for all x, y ∈ S. Hence, by Corollary 5.1, there exists a unique stationary distribution π and $\gamma(\mu P^t, \pi) \to 0$ as t → ∞ for any $\mu \in \cal P$. This convergence implies weak convergence by Proposition 4.1 and compactness of S.