Exact Mixing-Time Calculations for Two-State Chains

Two States, One Convergence Factor

For a general Markov chain, exact mixing calculations can require many matrix powers or careful bounds. An irreducible chain with two states is simpler: after one identifies its stationary distribution, every deviation from stationarity is multiplied at each step by the same number. That number can be negative, so the distributions may alternate around equilibrium even as their distance from it shrinks.

Let $(X_n)_{n\ge0}$ be a Markov chain on the state space $S=\{0,1\}$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Assume the transition probabilities are time-homogeneous and the chain is irreducible. Write $a$ for the probability of moving from 0 to 1 and $b$ for the probability of moving from 1 to 0. Irreducibility on these two states is equivalent to $a>0$ and $b>0$; since they are probabilities, $a,b\le1$. The row-stochastic transition matrix is

P=\begin{bmatrix} 1-a & a\\ b & 1-b \end{bmatrix}.

The rows sum to $(1-a)+a=1$ and $b+(1-b)=1$. Define $r=1-a-b$. It satisfies $-1\le r<1$: the lower endpoint occurs only if $a=b=1$, while $a+b>0$ rules out $r=1$. The value $r$ is the nontrivial eigenvalue of $P$, but the formulas below will be derived directly from the transition rule.

Definition: For probability distributions $\nu$ and $\eta$ on $\{0,1\}$, their total variation distance is $\|\nu-\eta\|_{\mathrm{TV}}=\tfrac12\sum_{j\in\{0,1\}}|\nu(j)-\eta(j)|$. For $0<\varepsilon<1$, the worst-case $\varepsilon$-mixing time is $t_{\mathrm{mix}}(\varepsilon)=\min\{n\ge0:\max_{i\in S}\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\le\varepsilon\}$, where $\pi$ is the stationary distribution. If the set in this minimum is empty, the mixing time is infinite.

Here $P^n(i,\cdot)$ is row $i$ of the $n$-step transition matrix. The total variation convention includes equality at the accuracy threshold: a distance equal to $\varepsilon$ meets the condition $\le\varepsilon$.

Stationarity and the Exact $n$-Step Distribution

A stationary distribution is a row probability vector $\pi$ satisfying $\pi P=\pi$. If $\pi=(\pi_0,\pi_1)$, stationarity in state 1 requires $\pi_1=\pi_0a+\pi_1(1-b)$, or $\pi_0a=\pi_1b$. Together with $\pi_0+\pi_1=1$, this gives

\pi_0=\frac{b}{a+b},\qquad \pi_1=\frac{a}{a+b}.

Both entries are positive and sum to 1 because $a,b>0$. Substitution verifies stationarity: the state-1 coordinate of $\pi P$ is $\pi_0a+\pi_1(1-b)=\frac{ab}{a+b}+\frac{a(1-b)}{a+b}=\frac{a}{a+b}=\pi_1$; since the coordinates sum to 1, the state-0 coordinate is $\pi_0$ as well. The equation $\pi_0a=\pi_1b$ also shows that any stationary probability vector must have these same entries, so this stationary distribution is unique.

Theorem (Exact two-state transition law): For every integer $n\ge0$, the two rows of $P^n$, written as probabilities of state 1, are $P^n(0,1)=\pi_1(1-r^n)$ and $P^n(1,1)=\pi_1+\pi_0r^n$. Equivalently, $$ P^n= \begin{bmatrix} \pi_0+\pi_1r^n & \pi_1(1-r^n)\\ \pi_0(1-r^n) & \pi_1+\pi_0r^n \end{bmatrix}. $$

Proof. If $q_n=\mathbb{P}(X_n=1)$, then conditioning on the state at time $n$ gives $q_{n+1}=(1-q_n)a+q_n(1-b)=a+rq_n$. The value $\pi_1=a/(a+b)$ is a fixed point of this recursion because $a+r\pi_1=a+(1-a-b)a/(a+b)=a/(a+b)=\pi_1$. Subtracting this fixed point from the recursion yields $q_{n+1}-\pi_1=r(q_n-\pi_1)$. Repeated substitution gives $q_n-\pi_1=r^n(q_0-\pi_1)$, including $n=0$, since $r^0=1$. Starting from state 0 gives $q_0=0$, hence $q_n=\pi_1-\pi_1r^n$. Starting from state 1 gives $q_0=1$, hence $q_n=\pi_1+\pi_0r^n$, since $1-\pi_1=\pi_0$. Each row has total probability 1, so its state-0 probability is one minus its state-1 probability. These four entries are precisely the displayed matrix. $\square$

This proof also handles $r=0$: the formula uses $r^0=1$ at time 0, and for $n\ge1$ the factor $r^n$ is zero. Thus both rows equal the stationary distribution after one step.

Exact Worst-Case Distance and Mixing Time

For distributions on two states, the total variation distance equals the absolute difference in their probabilities of state 1. Indeed, if those probabilities are $u$ and $v$, the differences in the two coordinates are $u-v$ and $-(u-v)$, so half the sum of their absolute values is $|u-v|$. Comparing the exact transition law with $\pi$ therefore gives the exact worst-case distance.

Theorem (Exact distance and mixing time): For every $n\ge0$, $$ \max_{i\in\{0,1\}}\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}} =C|r|^n,\qquad C=\max(\pi_0,\pi_1)=\frac{\max(a,b)}{a+b}. $$ If $|r|<1$, then for $0<\varepsilon<1$, $$ t_{\mathrm{mix}}(\varepsilon)= \begin{cases} 0, & \varepsilon\ge C,\\[2mm] \left\lceil\dfrac{\log(\varepsilon/C)}{\log|r|}\right\rceil, & 0<|r|<1\text{ and }\varepsilon<C,\\[3mm] 1, & r=0\text{ and }\varepsilon<C. \end{cases} $$ If $r=-1$, then the distance is $1/2$ at every time: $t_{\mathrm{mix}}(\varepsilon)=0$ when $\varepsilon\ge1/2$, and it is infinite when $\varepsilon<1/2$.

Proof. From the exact transition law, the state-1 probability in row 0 differs from $\pi_1$ by $-\pi_1r^n$, and the state-1 probability in row 1 differs from $\pi_1$ by $+\pi_0r^n$. By the two-state total variation calculation, the respective distances are $\pi_1|r|^n$ and $\pi_0|r|^n$. Their maximum is $C|r|^n$. Also, $\pi_0=b/(a+b)$ and $\pi_1=a/(a+b)$, giving the stated expression for $C$.

When $0<|r|<1$ and $\varepsilon<C$, the mixing condition is $C|r|^n\le\varepsilon$, equivalently $|r|^n\le\varepsilon/C$. Taking logarithms gives $n\log|r|\le\log(\varepsilon/C)$. Since $\log|r|<0$, dividing reverses the inequality, yielding $n\ge\log(\varepsilon/C)/\log|r|$. The least integer $n\ge0$ satisfying this condition is the displayed ceiling. When $\varepsilon\ge C$, the condition already holds at $n=0$, because $|r|^0=1$. When $r=0$, the distance is $C$ at $n=0$ and 0 for every $n\ge1$, which gives the separate zero-eigenvalue case. Finally, $r=-1$ forces $a+b=2$; because $a,b\le1$, this means $a=b=1$. Then $C=1/2$ and $|r|^n=1$ for every $n$, so the distance remains $1/2$. The minimum is 0 if that distance is within the requested threshold, and no time meets a smaller threshold. $\square$

In particular, for an irreducible two-state chain, convergence to stationarity occurs exactly when $r\ne-1$. The exceptional case $a=b=1$ alternates deterministically between the states and has period 2. Otherwise at least one state has a positive self-transition probability; irreducibility then makes the period of both states 1. The factor $r^n$ describes both the rate and the direction of convergence: positive $r$ gives deviations with the same sign at each time, while negative $r$ makes their signs alternate.

Worked Calculations

Worked Example: Positive Convergence Factor

Take $a=\tfrac13$ and $b=\tfrac12$. The matrix is $P=\begin{bmatrix}\tfrac23&\tfrac13\\\tfrac12&\tfrac12\end{bmatrix}$, and its rows sum to $\tfrac23+\tfrac13=1$ and $\tfrac12+\tfrac12=1$. Both switching probabilities are positive, so the chain is irreducible. Compute its exact distance at time $n$ and its mixing time for $\varepsilon=\tfrac1{20}$.

First, $a+b=\tfrac13+\tfrac12=\tfrac56$, so $r=1-\tfrac56=\tfrac16$. The stationary distribution is $\pi_0=(\tfrac12)/(\tfrac56)=\tfrac35$ and $\pi_1=(\tfrac13)/(\tfrac56)=\tfrac25$, which sum to 1. The exact transition matrix is therefore

P^n= \begin{bmatrix} \tfrac35+\tfrac25(\tfrac16)^n & \tfrac25\bigl(1-(\tfrac16)^n\bigr)\\ \tfrac35\bigl(1-(\tfrac16)^n\bigr) & \tfrac25+\tfrac35(\tfrac16)^n \end{bmatrix}.

The worst-case distance is $C|r|^n=\tfrac35(\tfrac16)^n$, since $C=\max(\tfrac35,\tfrac25)=\tfrac35$. At $n=1$, the two state-1 probabilities are $\tfrac25(1-\tfrac16)=\tfrac13$ and $\tfrac25+\tfrac35\cdot\tfrac16=\tfrac12$. Their signed deviations from $\pi_1=\tfrac25$ are $-\tfrac1{15}$ and $+\tfrac1{10}$, respectively; the distances are $\tfrac1{15}$ and $\tfrac1{10}$.

For $\varepsilon=\tfrac1{20}$, the initial worst-case distance is $\tfrac35>\tfrac1{20}$. At $n=1$ it is $\tfrac35\cdot\tfrac16=\tfrac1{10}>\tfrac1{20}$; at $n=2$ it is $\tfrac35\cdot\tfrac1{36}=\tfrac1{60}<\tfrac1{20}$. Hence the exact mixing time is 2. Substitution confirms the threshold condition: $\tfrac1{60}\le\tfrac1{20}$, while the preceding time has distance $\tfrac1{10}>\tfrac1{20}$.

Worked Example: Negative Convergence Factor

Let $a=\tfrac34$ and $b=\tfrac12$, and find the worst-case distance at times 1 and 2, followed by the mixing time for $\varepsilon=\tfrac3{40}$. The transition matrix is $P=\begin{bmatrix}\tfrac14&\tfrac34\\\tfrac12&\tfrac12\end{bmatrix}$; its rows sum to $\tfrac14+\tfrac34=1$ and $\tfrac12+\tfrac12=1$. The positive switching probabilities make the chain irreducible.

Here $a+b=\tfrac54$, so $r=1-\tfrac54=-\tfrac14$. The stationary probabilities are $\pi_0=(\tfrac12)/(\tfrac54)=\tfrac25$ and $\pi_1=(\tfrac34)/(\tfrac54)=\tfrac35$, which sum to 1. Thus the exact worst-case distance at time $n$ is $\tfrac35(\tfrac14)^n$. At time 1 it equals $\tfrac3{20}$, which exceeds $\tfrac3{40}$. At time 2 it equals $\tfrac3{80}$, which is less than $\tfrac3{40}$.

To check the time-2 calculation directly, $r^2=\tfrac1{16}$. Row 0 has state-1 probability $\tfrac35(1-\tfrac1{16})=\tfrac35\cdot\tfrac{15}{16}=\tfrac9{16}$; its deviation from $\pi_1=\tfrac35$ is $\tfrac9{16}-\tfrac35=\tfrac{45}{80}-\tfrac{48}{80}=-\tfrac3{80}$. Row 1 has state-1 probability $\tfrac35+\tfrac25\cdot\tfrac1{16}=\tfrac38+\tfrac1{40}=\tfrac5{8}$; its deviation is $\tfrac58-\tfrac35=\tfrac{25}{40}-\tfrac{24}{40}=\tfrac1{40}$. The row distances are $\tfrac3{80}$ and $\tfrac1{40}=\tfrac2{80}$, so their maximum is $\tfrac3{80}$, agreeing with the formula. Since time 1 fails and time 2 meets the threshold, $t_{\mathrm{mix}}(\tfrac3{40})=2$.

Worked Example: Zero Convergence Factor

Take $a=\tfrac23$ and $b=\tfrac13$. Then $P=\begin{bmatrix}\tfrac13&\tfrac23\\\tfrac13&\tfrac23\end{bmatrix}$; each row sums to $\tfrac13+\tfrac23=1$, and both switching probabilities are positive. Since $a+b=1$, $r=0$. The stationary distribution is $\pi=(\tfrac13,\tfrac23)$, whose entries sum to 1. The two rows of $P$ equal $\pi$, so $P^1(i,\cdot)=\pi$ for both starting states, and the distance is zero at every $n\ge1$.

For $\varepsilon=\tfrac14$, the time-zero distances are $\|\delta_0-\pi\|_{\mathrm{TV}}=\tfrac23$ and $\|\delta_1-\pi\|_{\mathrm{TV}}=\tfrac13$, so the worst-case distance is $\tfrac23>\tfrac14$. At time 1 the worst-case distance is 0, which is at most $\tfrac14$. Thus $t_{\mathrm{mix}}(\tfrac14)=1$. This verifies why $r=0$ requires a separate case rather than substituting into a logarithmic formula.

Reading the Formula Carefully

A common mistake is to reverse the signs of the two row deviations. The formula for state 1 gives, in row 0, $\pi_1(1-r^n)-\pi_1=-\pi_1r^n$, and, in row 1, $\pi_1+\pi_0r^n-\pi_1=+\pi_0r^n$. For the first example at $n=1$, these are $\tfrac13-\tfrac25=-\tfrac1{15}$ and $\tfrac12-\tfrac25=+\tfrac1{10}$. Writing $+\tfrac1{15}$ and $-\tfrac1{10}$ reverses the signed deviations. The absolute distances happen to remain the same, but the incorrect signs obscure which row lies below stationarity and which lies above it.

Another point is the distinction between a stationary distribution and convergence to it. The distribution $\pi$ is stationary even for the deterministic alternating chain $a=b=1$, but starting from either state the chain remains at total variation distance $\tfrac12$ from $\pi$ at every time. Thus a stationary distribution alone does not imply mixing. For the other irreducible two-state chains, $|r|<1$, and the exact formula shows that the distance tends to zero.

The exact calculation is useful because it separates the starting state, the equilibrium weights, and the rate factor. It also prevents a common overestimate or underestimate: the worst-case multiplier is $C=\max(\pi_0,\pi_1)$, not necessarily $\tfrac12$. When one state has larger stationary probability, starting from the other state produces the larger initial distance.

Check Your Understanding

Use the exact formulas above, and include the row-sum and threshold checks in each calculation.

For $a=\tfrac14$ and $b=\tfrac12$, find $r$, $\pi$, and the worst-case distance at time $n=2$.
For $a=\tfrac12$ and $b=\tfrac12$, determine the exact worst-case distance at every time and decide whether the chain converges to stationarity.
Suppose $0<|r|<1$ and $\varepsilon<C$. Explain why dividing by $\log|r|$ reverses the inequality in the mixing-time calculation.
For the zero-factor example, calculate the time-zero distance from each state to $\pi$, and verify the stated worst-case distance.
State the signed deviations of the two rows from stationarity in their state-1 probabilities, and explain why taking absolute values does not fix a mistaken account of their signs.

Exact Mixing-Time Calculations for Two-State Chains

What You'll Learn

Two States, One Convergence Factor

Stationarity and the Exact \(n\)-Step Distribution

Exact Worst-Case Distance and Mixing Time

Worked Calculations

Worked Example: Positive Convergence Factor

Worked Example: Negative Convergence Factor

Worked Example: Zero Convergence Factor

Reading the Formula Carefully

Check Your Understanding

Exact Mixing-Time Calculations for Two-State Chains

What You'll Learn

Two States, One Convergence Factor

Stationarity and the Exact \(n\)-Step Distribution

Exact Worst-Case Distance and Mixing Time

Worked Calculations

Worked Example: Positive Convergence Factor

Worked Example: Negative Convergence Factor

Worked Example: Zero Convergence Factor

Reading the Formula Carefully

Check Your Understanding

Previous

Next