Quantitative Convergence Rates for Stochastically Monotone Markov Chains

Throughout this paper, $\mathbbm{X}$ is a Polish space, $\mathcal{B}$ is its Borel sets, and $\preceq$ is a closed partial order on $\mathbbm{X}$. The last statement means that the graph of $\preceq$, denoted by

is closed under the product topology on $\mathbbm{X}\times\mathbbm{X}$. A map $h\colon\mathbbm{X}\to\mathbbm{R}$ is called increasing if $x\preceq x^{\prime}$ implies $h(x)\leqslant h(x^{\prime})$. We take $p\mathcal{B}$ to be the set of all probability measures on $\mathcal{B}$ and let $b\mathcal{B}$ be the bounded Borel measurable functions sending $\mathbbm{X}$ into $\mathbbm{R}$. The symbol $ib\mathcal{B}$ represents all increasing $h\in b\mathcal{B}$.

Given $\mu,\nu$ in $p\mathcal{B}$, we say that $\mu$ is stochastically dominated by $\nu$ and write $\mu\preceq_{s}\nu$ if $\mu(h)\leqslant\nu(h)$ for all $h\in ib\mathcal{B}$. In addition, we set

which corresponds to the Kolmogorov metric on $p\mathcal{B}$ [13, 10].

A function $Q\colon(\mathbbm{X},\mathcal{B})\to\mathbbm{R}$ is called a stochastic kernel on $(\mathbbm{X},\mathcal{B})$ if $Q$ is a map from $\mathbbm{X}\times\mathcal{B}$ to $[0,1]$ such that that $x\mapsto Q(x,A)$ is measurable for each $A\in\mathcal{B}$ and $A\mapsto Q(x,A)$ is a probability measure on $\mathcal{B}$ for each $x\in\mathbbm{X}$. At times we use the symbol $Q_{x}$ to represent the distribution $Q(x,\cdot)$ at given $x$. A stochastic kernel $Q$ on $(\mathbbm{X},\mathcal{B})$ is called increasing if $Qh\in ib\mathcal{B}$ whenever $h\in ib\mathcal{B}$.

For a given stochastic kernel $Q$ on $(\mathbbm{X},\mathcal{B})$, we define the left and right Markov operators generated by $Q$ via

(The left Markov operator $\mu\mapsto\mu Q$ maps $p\mathcal{B}$ to itself, while the right Markov operator $f\mapsto Qf$ acts on bounded measurable functions.) A discrete-time $\mathbbm{X}$-valued stochastic process $(X_{t})_{t\geqslant 0}$ on a filtered probability space $(\Omega,\mathscr{F},\mathbbm{P},(\mathscr{F}_{t})_{t\geqslant 0})$ is called Markov-$(Q,\mu)$ if $X_{0}\stackrel{{\scriptstyle\scriptsize{d}}}{{=}}\mu$ and

A coupling of $(\mu,\nu)\in p\mathcal{B}\times p\mathcal{B}$ is a probability measure $\rho$ on $\mathcal{B}\otimes\mathcal{B}$ satisfying $\rho(A\times\mathbbm{X})=\mu(A)$ and $\rho(\mathbbm{X}\times A)=\nu(A)$ for all $A\in\mathcal{B}$. Let $\mathscr{C}(\mu,\nu)$ denote the set of all couplings of $(\mu,\nu)$ and let

The value $\alpha(\mu,\nu)$ lies in $[0,1]$ and can be understood as a measure of “partial stochastic dominance” of $\nu$ over $\mu$ [14]. By the Polish assumption and Strassen’s theorem [22, 15] we have

Let $Q$ be a stochastic kernel on $(\mathbbm{X},\mathcal{B})$ and let $\hat{Q}$ be a stochastic kernel on $(\mathbbm{X}\times\mathbbm{X},\mathcal{B}\otimes\mathcal{B})$. We call $\hat{Q}$ a Markov coupling of $Q$ if $\hat{Q}_{(x,x^{\prime})}$ is a coupling of $Q_{x}$ and $Q_{x^{\prime}}$ for all $x,x^{\prime}\in\mathbbm{X}$. We call $\hat{Q}$ a $\preceq$-maximal Markov coupling of $Q$ if $\hat{Q}$ is a Markov coupling of $Q$ and, in addition,

Consider the geometric drift condition

where $Q$ is a stochastic kernel on $(\mathbbm{X},\mathcal{B})$, $V$ is a measurable function from $\mathbbm{X}$ to $[1,\infty)$, and $\lambda$ and $\beta$ are nonnegative constants. We fix $d\geqslant 1$ and set

Fix $\mu,\mu^{\prime}$ in $p\mathcal{B}$ and set

Let $\hat{Q}$ be a Markov coupling of $Q$ and let $((X_{t},X^{\prime}_{t}))_{t\geqslant 0}$ be Markov-$(\hat{Q},\mu\times\mu^{\prime})$ on $(\Omega,\mathscr{F},\mathbbm{P},(\mathscr{F}_{t})_{t\geqslant 0})$. We are interested in studying the number of visits to $C\times C$, as given by

The result in Lemma 2.2 has already been used in other sources. To make the paper more self-contained, we provide a proof in the appendix. Our proof is based on arguments in [20].

One special case is when $\preceq$ is the identity order, so that $x\preceq y$ if and only if $x=y$. For this order we have $ib\mathcal{B}=b\mathcal{B}$, so every stochastic kernel is increasing, and the Kolmogorov metric (see (1)) becomes the total variation distance. In this setting total variation setting, Theorem 3.1 is similar to standard geometric bounds for total variation distance, such as Theorem 1 in [20].

It is worth noting that, in the total variation setting, $\varepsilon$ in (8) is at least as large as the analogous term $\varepsilon$ in Theorem 1 in [20]. Indeed, in [20], the value $\varepsilon$, which we now write as $\hat{\varepsilon}$ to avoid confusion, comes from an assumed minorization condition: there exists a $\nu\in p\mathcal{B}$ such that

To compare $\hat{\varepsilon}$ with $\varepsilon$ defined in (8), suppose that this minorization condition holds and define the residual kernel $R(x,B)\coloneq(Q(x,B)-\hat{\varepsilon}\nu(B))/(1-\hat{\varepsilon})$. Fixing $(x,x^{\prime})\in C\times C$, we draw $(X,X^{\prime})$ as follows: With probability $\varepsilon$, draw $X\sim\nu$ and set $X^{\prime}=X$. With probability $1-\varepsilon$, independently draw $X\sim R(x,\cdot)$ and $X^{\prime}\sim R(x^{\prime},\cdot)$. Simple arguments confirm that $X$ is a draw from $Q(x,\cdot)$ and $X^{\prime}$ is a draw from $Q(x^{\prime},\cdot)$. Recalling that $\preceq$ is the identity order, this leads to $\hat{\varepsilon}=\mathbbm{P}\{I\leqslant\hat{\varepsilon}\}\leqslant\mathbbm{P}\{X=X^{\prime}\}=\mathbbm{P}\{X\preceq X^{\prime}\}\leqslant\alpha(Q(x,\cdot),Q(x^{\prime},\cdot))$. (The last bound is by the definition of $\alpha$ in (2) and the fact that the joint distribution of $(X,X^{\prime})$ is a coupling of $Q(x,\cdot)$ and $Q(x^{\prime},\cdot)$.) Since, in this discussion, the point $(x,x^{\prime})$ was arbitrarily chosen from $C\times C$, we conclude that $\hat{\varepsilon}\leqslant\varepsilon$, where $\varepsilon$ is as defined in (8).

The preceding section showed that Theorem 3.1 reduces to existing results for bounds on total variation distance when the partial order $\preceq$ is the identity order. Now we show how Theorem 3.1 leads to new results other settings, such as when $\preceq$ is a pointwise partial order. To this end, consider the process

where $(W_{t})_{t\geqslant 1}$ is an iid shock process taking values in some space $\mathbb{W}$, and $F$ is a measurable function from $\mathbbm{X}\times\mathbb{W}$ to $\mathbbm{X}$. The common distribution of each $W_{t}$ is denoted by $\varphi$. We suppose that $F$ is increasing, in the sense that $x\preceq x^{\prime}$ implies $F(x,w)\preceq F(x^{\prime},w)$ for any fixed $w\in\mathbb{W}$. We let $Q$ represent the stochastic kernel corresponding to (17), so that $Q(x,B)=\varphi\{w\in\mathbb{W}:F(x,w)\in B\}$ for all $x\in\mathbbm{X}$ and $B\in\mathcal{B}$. Since $F$ is increasing, the kernel $Q$ is increasing. Hence Theorem 3.1 applies. We can obtain a lower bound on $\varepsilon$ in (8) by calculating

Indeed, if $W$ and $W^{\prime}$ are drawn independently from $\varphi$, then $X=F(x,W)$ is a draw from $Q(x,\cdot)$ and $X^{\prime}=F(x^{\prime},W)$ is a draw from $Q(x^{\prime},\cdot)$. Hence

To illustrate the method in Section 4.2, we consider the TCP window size process (see, e.g., [2]), which has embedded jump chain $X_{t+1}=a(X_{t}^{2}+2E_{t+1})^{1/2}$. Here $a\in(0,1)$ and $(E_{t})$ is iid exponential with unit rate. If $C=[0,c]$, then drawing $E,E^{\prime}$ as independent standard exponentials and using (19),

Since $E^{\prime}-E$ has the Laplace-$(0,1)$ distribution, we get

We provide an elementary scenario where Theorem 3.1 provides a usable bound while the minorization based methods described in Section 4.1 do not. Let $\mathbbm{Q}$ be the rational numbers, let $\mathbbm{X}=\mathbbm{R}$, and assume that

Let $C$ contain at least one rational and one irrational number. Let $\mu$ be a measure on the Borel sets of $\mathbbm{R}$ obeying $\mu(B)\leqslant Q(x,B)=\mathbbm{P}\{x/2+W\in B\}$ for all $x\in C$ and Borel sets $B$. If $x$ is rational, then $x/2+W\in\mathbbm{Q}$ with probability one, so $\mu(\mathbbm{Q}^{c})\leqslant Q(x,\mathbbm{Q}^{c})=0$. Similarly, if $x$ is irrational, then $x/2+W\in\mathbbm{Q}^{c}$ with probability one, so $\mu(\mathbbm{Q})\leqslant Q(x,\mathbbm{Q})=0$. Hence $\mu$ is the zero measure on $\mathbbm{R}$. Thus, we cannot take a $\hat{\varepsilon}>0$ and probability measure $\nu$ obeying the minorization condition (16). On the other hand, letting $V(x)=x+1$ and $d=1$, so that $C=\{V\leqslant 2\}=[0,1]$, the value $e$ from (18) obeys $e=\mathbbm{P}\{1/2+W\leqslant W^{\prime}\}=\mathbbm{P}\{W^{\prime}-W\geqslant 1/2\}=\frac{1}{4}$. Hence, by (19), the constant $\varepsilon$ in Theorem 3.1 is positive.

Many economic models examine wealth dynamics in the presence of credit market imperfections (see, e.g., [1]). These often result in dynamics of the form

Here $(X_{t})$ is some measure of household wealth, $G$ is a function from $\mathbbm{R}_{+}$ to itself and $(\eta_{t})$ and $(\xi_{t})$ are independent $\mathbbm{R}_{+}$-valued sequences. The function $G$ is increasing, since greater current wealth relaxes borrowing constraints and increases financial income. We assume that there exists a $\lambda<1$ such that $\mathbbm{E}\,\eta_{t}G(x)\leqslant\lambda x$ for all $x\in\mathbbm{R}_{+}$, and, in addition, that $\bar{\xi}\coloneq\mathbbm{E}\xi_{t}<\infty$.

Let $Q$ be the stochastic kernel corresponding to (20). With $V(x)=x+1$, we have

Fixing $d\in\mathbbm{R}_{+}$ and setting $C=\{V\leqslant d\}=[0,d]$, we can obtain $e$ in (18) via

This term will be strictly positive under suitable conditions, such as when $\psi$ has a sufficiently large support. Combining (19) and (21) with the bound in Theorem 3.1, we have, for any $\mu$ and $\mu^{\prime}$ in $p\mathcal{B}$ and $j,t\in\mathbbm{N}$ with $j\leqslant t$,

where $H(\mu,\mu^{\prime})\coloneq\left(\int x\mu(\mathop{}\!\mathrm{d}x)+\int x\mu^{\prime}(\mathop{}\!\mathrm{d}x)\right)/2$.

Notice that, for this model, the lack of smooth mixing and continuity implies that neither total variation nor Wasserstein distance bounds can be computed without additional assumptions.