A Shared Part in Every Transition
A useful way to make two Markov chains move toward one another is to give them a common chance of making exactly the same transition. Doeblin minorization formalizes this idea: every row of the transition matrix must contain at least the same fixed fraction of one probability distribution. That shared fraction can be interpreted as a random refresh, while the rest of each row is a residual transition rule. Because the refresh chance does not depend on the current state, it gives a geometric bound on how long two chains can remain different.
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix \(P=(p_{ij})\) is row-stochastic, so \(\sum_{j\in S}p_{ij}=1\) for every \(i\). For probability distributions \(\alpha\) and \(\beta\) on \(S\), write their total variation distance as \(\|\alpha-\beta\|_{\mathrm{TV}}=\sup_{A\subseteq S}|\alpha(A)-\beta(A)|\). On a countable space this is also \(\tfrac12\sum_{j\in S}|\alpha_j-\beta_j|\).
When \(0<\varepsilon<1\), subtract the shared part from each row and divide what remains by \(1-\varepsilon\). This gives the residual transition matrix \(R\), with entries \(r_{ij}=(p_{ij}-\varepsilon\nu_j)/(1-\varepsilon)\). Each entry is nonnegative by minorization, and each row sums to \((1-\varepsilon)/(1-\varepsilon)=1\). Thus \(R\) is a transition matrix and
This decomposition has a direct probabilistic interpretation. At each step, choose a refresh with probability \(\varepsilon\), independently of the chain's current state. On a refresh, draw the next state from \(\nu\); otherwise use the residual row \(R(i,\cdot)\). The resulting transition probabilities are exactly those of \(P\). A shared refresh can therefore put chains with different starting states at the same state.
Contraction and Convergence
Proof. First suppose \(0<\varepsilon<1\), so the residual transition matrix \(R\) is defined. A transition matrix cannot increase total variation. To verify this, let \(A\subseteq S\) and write \(f(i)=R(i,A)\), so \(0\le f(i)\le1\). For any probability distributions \(\alpha,\beta\), the difference \((\alpha R)(A)-(\beta R)(A)\) is \(\sum_i(\alpha_i-\beta_i)f(i)\). The positive and negative parts of the signed sequence \((\alpha_i-\beta_i)\) have equal total mass \(\|\alpha-\beta\|_{\mathrm{TV}}\). Since \(f\) lies between zero and one, the absolute value of this sum is at most that mass. Taking the supremum over \(A\) proves \(\|\alpha R-\beta R\|_{\mathrm{TV}}\le\|\alpha-\beta\|_{\mathrm{TV}}\).
The minorization decomposition gives \(\alpha P=\varepsilon\nu+q\alpha R\) and \(\beta P=\varepsilon\nu+q\beta R\). Subtracting cancels the common distribution, and the just-proved contraction for \(R\) yields \(\|\alpha P-\beta P\|_{\mathrm{TV}}\le q\|\alpha-\beta\|_{\mathrm{TV}}\). Applying this one-step inequality repeatedly proves the claimed bound for every \(n\).
It remains to prove existence and uniqueness of a stationary distribution; contraction alone does not require assuming either in advance. For each \(k\ge0\), let \(\nu R^k\) denote the distribution obtained by applying \(R\) for \(k\) steps to initial distribution \(\nu\). Define $$ \pi=\varepsilon\sum_{k=0}^{\infty}q^k\nu R^k. $$ All terms are nonnegative distributions multiplied by nonnegative weights, and their weights sum to \(\varepsilon\sum_{k\ge0}q^k=1\). Hence \(\pi\) is a probability distribution. By the decomposition of \(P\), $$ \pi P=\varepsilon\nu+q\pi R =\varepsilon\nu+\varepsilon\sum_{k=0}^{\infty}q^{k+1}\nu R^{k+1} =\pi. $$ If \(\widetilde{\pi}\) is any other stationary distribution, the contraction inequality gives \(\|\pi-\widetilde{\pi}\|_{\mathrm{TV}}\le q\|\pi-\widetilde{\pi}\|_{\mathrm{TV}}\). Since \(q<1\), this forces the distance to be zero, so the stationary distribution is unique. Taking \(\beta=\pi\) in the iterated contraction proves convergence from every initial distribution. If \(\varepsilon=1\), then \(p_{ij}\ge\nu_j\) for every \(j\), and both rows have total mass one; therefore every row equals \(\nu\). The stated conclusion follows directly. \(\square\)
The theorem requires a single positive minorization constant that applies uniformly across the whole state space. It does not require irreducibility or aperiodicity as separate assumptions: the uniform shared part itself ensures a unique stationary distribution and convergence. The size of \(\varepsilon\) matters, however. A smaller valid constant still gives a valid bound, but a weaker geometric rate.
Worked Example: A Two-State Chain
Consider \(S=\{0,1\}\) and $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ Each row sums to \(1\): \(\tfrac34+\tfrac14=1\) and \(\tfrac14+\tfrac34=1\). The common distribution \(\nu=(\tfrac12,\tfrac12)\) with \(\varepsilon=\tfrac12\) is a minorization, since each entry of \(P\) is at least \(\tfrac12\) times the corresponding entry of \(\nu\). Subtracting the shared row and dividing by \(1-\varepsilon=\tfrac12\) gives $$ R=\begin{bmatrix}1&0\\0&1\end{bmatrix}. $$ Both residual rows sum to \(1\), and indeed \(P=\tfrac12\nu+\tfrac12R\), row by row.
The stationary distribution is \(\pi=(\tfrac12,\tfrac12)\): multiplying gives \(\pi P=(\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac14,\ \tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac34)=(\tfrac12,\tfrac12)\), and its entries sum to \(1\). Start instead from \(\alpha=(1,0)\). Then \(\|\alpha-\pi\|_{\mathrm{TV}}=\tfrac12\), so the theorem gives \(\|\alpha P^n-\pi\|_{\mathrm{TV}}\le(\tfrac12)^n\tfrac12\).
In this example the bound is exact. If \(x_n\) is the probability of state \(0\) at time \(n\), then \(x_0=1\) and \(x_{n+1}=\tfrac34x_n+\tfrac14(1-x_n)=\tfrac14+\tfrac12x_n\). Subtracting \(\tfrac12\) gives \(x_{n+1}-\tfrac12=\tfrac12(x_n-\tfrac12)\), so \(x_n-\tfrac12=(\tfrac12)^{n+1}\). The distance to \(\pi\) is \(|x_n-\tfrac12|=(\tfrac12)^{n+1}\), equal to the bound.
Worked Example: Finding the Stationary Distribution from the Split
Let \(S=\{0,1,2\}\), let \(\nu=(\tfrac12,\tfrac13,\tfrac16)\), and let $$ R=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac13&0&\tfrac23 \end{bmatrix}. $$ The row sums of \(R\) are \(\tfrac12+\tfrac12=1\), \(0+\tfrac12+\tfrac12=1\), and \(\tfrac13+0+\tfrac23=1\). With \(\varepsilon=\tfrac12\), the rows \(P(i,\cdot)=\tfrac12\nu+\tfrac12R(i,\cdot)\) are $$ P=\begin{bmatrix} \tfrac12&\tfrac5{12}&\tfrac1{12}\\ \tfrac14&\tfrac5{12}&\tfrac13\\ \tfrac5{12}&\tfrac16&\tfrac5{12} \end{bmatrix}. $$ Their sums are respectively \(\tfrac6{12}+\tfrac5{12}+\tfrac1{12}=1\), \(\tfrac3{12}+\tfrac5{12}+\tfrac4{12}=1\), and \(\tfrac5{12}+\tfrac2{12}+\tfrac5{12}=1\). Each row contains at least \(\tfrac12\nu=(\tfrac14,\tfrac16,\tfrac1{12})\), as required.
Write \(\pi=(x,y,z)\). The series construction in the theorem implies \(\pi=\tfrac12\nu+\tfrac12\pi R\). Equating coordinates gives $$ x=\tfrac14+\tfrac{x}{4}+\tfrac{z}{6},\qquad y=\tfrac16+\tfrac{x}{4}+\tfrac{y}{4},\qquad z=\tfrac1{12}+\tfrac{y}{4}+\tfrac{z}{3}. $$ The first equation is \(9x-2z=3\); the second is \(9y-3x=2\); and the third is \(8z-3y=1\). From the second, \(y=(2+3x)/9\). Substituting this into the third gives \(z=(5+3x)/24\). Substituting that into the first gives \(9x-(5+3x)/12=3\), hence \(105x=41\), so \(x=\tfrac{41}{105}\). Then \(y=\tfrac{37}{105}\) and \(z=\tfrac{27}{105}\).
Check: The entries sum to \((41+37+27)/105=1\). Also \(\pi R=(\tfrac{59}{210},\tfrac{13}{35},\tfrac{73}{210})\), so \(\tfrac12\nu+\tfrac12\pi R=(\tfrac{41}{105},\tfrac{37}{105},\tfrac{27}{105})=\pi\). Thus \(\pi P=\pi\), verifying the result directly. The theorem also gives \(\|\alpha P^n-\pi\|_{\mathrm{TV}}\le(\tfrac12)^n\|\alpha-\pi\|_{\mathrm{TV}}\) for every initial distribution \(\alpha\).
Worked Example: A Countable Chain with Resets
Let \(S=\{0,1,2,\ldots\}\). At each step, with probability \(\tfrac12\) move to \(0\), and with probability \(\tfrac12\) move from \(i\) to \(i+1\). Thus \(\nu\) is concentrated at \(0\), \(\varepsilon=\tfrac12\), and \(R(i,i+1)=1\) for every \(i\). Every row of \(R\) sums to \(1\); the transition row of \(P\) has probability \(\tfrac12\) at \(0\) and \(\tfrac12\) at \(i+1\), with row sum \(1\) (for \(i=0\), these are distinct destinations \(0\) and \(1\)). The minorization holds because every row assigns mass \(\tfrac12\) to \(0\).
Since \(\nu R^k\) is concentrated at state \(k\), the stationary distribution from the theorem is \(\pi_j=\tfrac12(\tfrac12)^j=2^{-(j+1)}\), for \(j\ge0\). Its total mass is \(\sum_{j\ge0}2^{-(j+1)}=1\). To check stationarity, state \(0\) receives mass \(\tfrac12\) from the reset part. For \(j\ge1\), the only way to enter \(j\) is to move up from \(j-1\), so \((\pi P)_j=\tfrac12\pi_{j-1}=\tfrac12\cdot2^{-j}=2^{-(j+1)}=\pi_j\). The coordinate at \(0\) is also \((\pi P)_0=\tfrac12\sum_i\pi_i=\tfrac12=\pi_0\). Hence \(\pi P=\pi\). From every initial distribution the total variation distance to \(\pi\) is at most \((\tfrac12)^n\), since the initial distance between two probability distributions is at most \(1\).
What the Bound Says—and What It Does Not
The split also explains the contraction intuitively. Couple two chains by using the same refresh coin at each step and, whenever a refresh occurs, the same draw from \(\nu\). If the chains have not yet matched, their residual moves can be drawn according to their respective rows of \(R\). After the first shared refresh their states agree, and they can use identical transitions thereafter. The chance that no refresh has occurred in \(n\) steps is \((1-\varepsilon)^n\); this is the same geometric mechanism behind the total variation bound. The algebraic proof above establishes the bound without needing any extra assumptions about the chain's paths.
Minorization is a strong, uniform condition. For example, a deterministic shift on the nonnegative integers, which moves from \(i\) to \(i+1\) with probability \(1\), cannot have a positive common minorization: distinct rows put all their mass on distinct states, so no probability distribution \(\nu\) can be dominated by a positive fraction of every row. Failure of this particular condition does not itself prove that a chain fails to converge; it only means this Doeblin bound is unavailable in that form.
Common mistake. After subtracting the shared part, it is incorrect to treat the difference as a probability row without normalizing it. In the first row of the three-state example, subtracting \(\tfrac12\nu=(\tfrac14,\tfrac16,\tfrac1{12})\) from \(P(0,\cdot)=(\tfrac12,\tfrac5{12},\tfrac1{12})\) gives \((\tfrac14,\tfrac14,0)\), whose entries sum to \(\tfrac12\), not \(1\). The residual row is obtained by dividing by \(1-\varepsilon=\tfrac12\), giving \((\tfrac12,\tfrac12,0)\). Forgetting this division makes the purported residual object fail the definition of a transition probability distribution.
Check Your Understanding
Use the minorization definition and verify your calculations by checking row sums and substituting into the relevant equations.
- For a minorization with \(\varepsilon=\tfrac13\), what formula gives the residual row \(R(i,\cdot)\), and why does it sum to \(1\)?
- Suppose two distributions \(\alpha,\beta\) satisfy \(\|\alpha-\beta\|_{\mathrm{TV}}=\tfrac25\), and a kernel has minorization constant \(\varepsilon=\tfrac14\). What bound does one-step contraction give?
- In the countable reset example, calculate \(\pi_0,\pi_1,\pi_2\) and check the stationarity equation for state \(2\).
- Why does a common minorization need to use the same distribution \(\nu\) for every starting state?
- If \(\varepsilon=1\), what does the row-sum condition imply about every row of \(P\)?