Convergence and Periodicity in Markov Chains

Eigenvalues and Long-Term Markov Iteration

A Markov transition matrix describes how a probability distribution changes one step at a time. Its eigenvalues help distinguish two kinds of long-term behaviour: a component of the distribution may decay, or it may persist and change sign on each step. In a two-state chain, the calculation is especially explicit. One eigenvalue is always \(1\); the other can be anywhere from \(-1\) to \(1\), including the exceptional cases where it equals \(1\) or \(-1\).

We use column probability vectors. A two-state probability vector has the form \(\mathbf{x}=(q,1-q)^{\top}\), where \(0\le q\le1\). Let \(a\) be the probability of moving from state 1 to state 1, and \(b\) the probability of moving from state 2 to state 1. The transition matrix is column-stochastic: each column sums to \(1\), and its entries are nonnegative.

Here \(\mathbf{x}_k\) is the probability distribution after \(k\) transitions, with \(\mathbf{x}_0\) the initial distribution. A stationary distribution is a probability vector \(\boldsymbol{\pi}\) satisfying \(\mathbf{P}\boldsymbol{\pi}=\boldsymbol{\pi}\). We will identify both the eigenvalues and the exact iteration formula, then use them to distinguish convergence from oscillation.

The Two Eigenvalues

An eigenvalue of \(\mathbf{P}\) is a scalar \(\lambda\) for which there is a nonzero vector \(\mathbf{v}\) satisfying \(\mathbf{P}\mathbf{v}=\lambda\mathbf{v}\). The eigenvalue \(1\) is present because \(\mathbf{P}\) preserves total probability. The second eigenvalue, counted with multiplicity, is \(a-b\). The phrase “counted with multiplicity” matters: for the identity matrix both eigenvalues are \(1\), so there is no distinct second value.

Proof. The characteristic polynomial, using \(t\) as its variable, is

Thus the eigenvalues are \(1\) and \(a-b\), with a repeated root when \(a-b=1\). Since \(a,b\in[0,1]\), their difference lies in \([-1,1]\). If \(a-b=1\), then \(a=1\) and \(b=0\), because \(a\le1\) and \(b\ge0\); substitution gives \(\mathbf{P}=\mathbf{I}_2\). If \(a-b=-1\), then \(a=0\) and \(b=1\), giving the stated alternating matrix. \(\square\)

One can also see the role of the second eigenvalue directly. The vector \((1,-1)^{\top}\) is an eigenvector, since

This direction changes the balance between the two state probabilities while preserving their sum. When \(|a-b|<1\), its contribution shrinks with each iteration. When \(a-b=-1\), it changes sign but does not shrink. When \(a-b=1\), the matrix is the identity and the distribution does not change at all.

Exact Iteration and Convergence

To derive the iteration, write \(\mathbf{x}_k=(q_k,1-q_k)^{\top}\). The first component after one step is

When \(1-a+b>0\), the fixed value of this scalar recurrence is \(q_*=\dfrac{b}{1-a+b}\). The resulting stationary probability vector is \(\boldsymbol{\pi}=(q_*,1-q_*)^{\top}\). The denominator is positive in this case, so the formula is defined. Subtracting the fixed-point equation \(q_*=b+(a-b)q_*\) from the recurrence gives \(q_{k+1}-q_*=(a-b)(q_k-q_*)\). Repeating this relation yields an exact expression for every iterate.

Proof. Put \(d=1-a+b\), and assume \(d>0\). The equation for a stationary first component is \(q=b+(a-b)q\), or \(dq=b\), so its only solution is \(q=b/d\). This value lies in \([0,1]\): \(b\ge0\), and \(d-b=1-a\ge0\). The second component is \(1-q=(1-a)/d\), so the vector stated in the theorem is a probability vector. The scalar fixed-point equation shows that \(\mathbf{P}\boldsymbol{\pi}=\boldsymbol{\pi}\). Conversely, every stationary probability vector must have first component solving \(dq=b\); since \(d>0\), this solution is unique.

For any initial probability vector, subtract the fixed-point equation from the first-component recurrence. With \(\lambda=a-b\), this gives \(q_{k+1}-q_*=\lambda(q_k-q_*)\). Induction on \(k\) gives \(q_k-q_*=\lambda^k(q_0-q_*)\): it holds at \(k=0\), and multiplying the equation at step \(k\) by \(\lambda\) gives the equation at step \(k+1\). The second component is one minus the first, so the vector formula follows. If \(|\lambda|<1\), then \(\lambda^k\to0\), and the formula gives convergence to \(\boldsymbol{\pi}\). If \(\lambda=-1\), then \(\mathbf{x}_k=\boldsymbol{\pi}+(-1)^k(\mathbf{x}_0-\boldsymbol{\pi})\), which alternates between \(\mathbf{x}_0\) and \(\mathbf{x}_1\). It is constant precisely when \(\mathbf{x}_0=\boldsymbol{\pi}\). \(\square\)

It remains to account for the excluded case \(1-a+b=0\). Both terms \(1-a\) and \(b\) are nonnegative, and their sum is zero only if \(a=1\) and \(b=0\). Then \(\mathbf{P}=\mathbf{I}_2\), and every probability vector is stationary. This is exactly the repeated-eigenvalue case: both eigenvalues are \(1\). Thus the stationary formula with denominator \(1-a+b\) must not be used for the identity matrix.

Worked Iterations

Positive Chains and the Unit Circle

A two-state transition matrix is positive when every entry is strictly positive. In the parametrization used here, this means \(0<a<1\) and \(0<b<1\). Consequently \(-1<a-b<1\), and \(1-a+b>0\). The convergence theorem therefore applies: every initial probability vector converges to the unique stationary distribution. The second eigenvalue is strictly inside the unit circle, so its iterated contribution vanishes.

The two boundary values of the interval \([-1,1]\) explain the exceptional behaviour. At \(1\), the matrix is the identity, and every distribution is fixed. At \(-1\), the matrix swaps the two states, so any nonstationary initial distribution oscillates with period two. Eigenvalues on the unit circle do not decay under taking powers: the value \(1\) preserves a component, while \(-1\) reverses its sign at each step. For a positive two-state chain, neither boundary value occurs for the second eigenvalue.

A related error is to use the stationary formula \(\boldsymbol{\pi}=(b/(1-a+b),(1-a)/(1-a+b))^{\top}\) for the identity matrix. Substituting \(a=1,b=0\) produces division by zero, not a stationary distribution. The correction is to treat that case separately: \(\mathbf{P}=\mathbf{I}_2\), so every probability vector is stationary. Checking the denominator before using the formula prevents this mistake.