LINEAR-ALGEBRA · Interactive Practice | Unit 23 · Video 2

Why Every Markov Chain Forgets Where It Started: The λ=1 Attractor

IKey Formulas

Formula	Name	Description
$u_{k+1} = A\, u_k$	Markov iteration	One time step of the chain
$u_k = c_1 \lambda_1^k x_1 + c_2 \lambda_2^k x_2 + \cdots + c_n \lambda_n^k x_n$	Spectral master formula	Powers of $A$ in the eigenvector basis
$\lambda_1 = 1,\ \ \lvert\lambda_i\rvert < 1$ for $i \ge 2$	Markov spectrum	Always true for column-stochastic $A$
$u_k \to c_1 x_1$ as $k \to \infty$	Steady state	Only the $\lambda=1$ direction survives

IIVisualization 1 — Forgetting the Starting Split

Each step fraction $p$ leaves City A and fraction $q$ leaves City B; run the chain forward and watch the split settle.

p (A→B) 0.20 q (B→A) 0.30 start in A 0.90 step k 30

💡 For $A = \begin{bmatrix} 1-p & q \\ p & 1-q \end{bmatrix}$ the steady state is $\tfrac{1}{p+q}(q,\,p)$ — fixed by the rates alone, never by the start.

IIIVisualization 2 — How Fast a Chain Forgets

Every non-dominant term decays like $|\lambda_2|^k$ ; the closer $|\lambda_2|$ sits to 1, the slower the chain forgets.

|λ₂| 0.70

💡 The steps needed to shrink to 1% is the chain's mixing time; the ratio $|\lambda_2|$ that sets it is the mixing rate.

IVVisualization 3 — All Roads to One Steady State

Six different starting splits, all on the line $a+b=1$ — every trajectory slides to the same steady-state point.

p (A→B) 0.40 q (B→A) 0.20 step k 25

VQuiz Questions

Question 1

For any column-stochastic Markov matrix $A$ , what is the largest eigenvalue $\lambda_1$ ?

✅ Correct! Every column-stochastic matrix has $\lambda_1 = 1$ — guaranteed by the columns summing to 1.

❌ Not quite. The columns-sum-to-1 property forces a specific eigenvalue. Think about what $\mathbf{1}^T A$ equals.

Show solution

Solution:

Every column-stochastic matrix has columns summing to 1. This means the all-ones row vector $\mathbf{1}^T$ satisfies $\mathbf{1}^T A = \mathbf{1}^T$ , so $\mathbf{1}^T$ is a left eigenvector with eigenvalue $1$ . Since $A$ and $A^T$ share eigenvalues, $\lambda = 1$ is also an eigenvalue of $A$ .

Combined with the Perron–Frobenius bound $|\lambda_i| \le 1$ for all eigenvalues of a stochastic matrix, we conclude:

$\lambda_1 = 1 \text{ exactly, always.}$

Question 2

A Markov chain has eigenvalues $\lambda_1 = 1$ , $\lambda_2 = 0.95$ , and $\lambda_3 = 0.2$ . Approximately how many steps $k$ are needed for the non-dominant components to decay by a factor of about 100 (i.e., $|\lambda_2|^k \approx 0.01$ )?

✅ Correct! $\ln(0.01)/\ln(0.95) \approx 90$ . The slowest-decaying eigenvalue $\lambda_2 = 0.95$ sets the mixing time.

❌ Not quite. Convergence is controlled by the second-largest eigenvalue. Solve $0.95^k \approx 0.01$ .

Show solution

Solution:

The convergence rate is governed by the second-largest eigenvalue magnitude, $|\lambda_2| = 0.95$ . We want:

$0.95^k \approx 0.01$

Taking logs: $k \approx \dfrac{\ln(0.01)}{\ln(0.95)} = \dfrac{-4.605}{-0.0513} \approx 89.8$ .

So about 90 steps. Note that $\lambda_3 = 0.2$ decays much faster ( $0.2^{90}$ is astronomically tiny), so it's irrelevant — the slowest non-dominant eigenvalue dominates the mixing time.

Question 3

True or False: For a (well-behaved) Markov chain, the steady state $u_\infty$ depends on the starting distribution $u_0$ .

✅ Correct! The steady state $c_1 x_1$ is determined by the matrix's $\lambda=1$ eigenvector, and the probability constraint pins $c_1$ — independent of $u_0$ .

❌ Not quite. Look back at Visualization 3: six different starting splits all flowed to the same red star.

Show solution

Solution:

The master formula gives $u_k = c_1 \cdot 1^k \cdot x_1 + c_2 \lambda_2^k x_2 + \cdots$ . As $k \to \infty$ , only the first term survives, so:

$u_\infty = c_1 x_1.$

The direction $x_1$ is fixed by the matrix $A$ — it does not depend on $u_0$ at all. The scalar $c_1$ does depend on $u_0$ in principle, but for any probability vector $u_0$ (entries non-negative, summing to 1), the constraint that $u_\infty$ also sums to 1 pins down $c_1$ uniquely.

Result: every probability starting distribution converges to the same steady state. The chain forgets where it began.

(Caveat: this assumes $\lambda = 1$ has multiplicity one and the chain is irreducible/aperiodic — the well-behaved case.)

Question 4

Consider the column-stochastic matrix $A = \begin{bmatrix} 0.7 & 0.4 \\ 0.3 & 0.6 \end{bmatrix}.$

What is the steady-state distribution (the eigenvector for $\lambda = 1$ , normalized so its entries sum to 1)?

✅ Correct! Solving $(A-I)x = 0$ and normalizing gives $(4/7, 3/7)$ .

❌ Not quite. $(0.5, 0.5)$ would only be the steady state if the matrix were symmetric (e.g., $p = q$ ). Here $p \ne q$ .

❌ Not quite. Reading the diagonal isn't the same as solving $Ax = x$ . Set up the eigenvalue equation.

❌ Not quite. You may have swapped the components. Solve $(A-I)x = 0$ carefully.

Show solution

Solution:

We need $A x = x$ , i.e., $(A - I)x = 0$ :

$A - I = \begin{bmatrix} -0.3 & 0.4 \\ 0.3 & -0.4 \end{bmatrix}.$

The first row gives $-0.3 x_1 + 0.4 x_2 = 0$ , so $x_2 = \tfrac{3}{4} x_1$ , or $(x_1, x_2) \propto (4, 3)$ .

Normalizing so the entries sum to 1:

$x_1 = \left(\frac{4}{7},\ \frac{3}{7}\right) \approx (0.571,\ 0.429).$

Shortcut for 2×2 column-stochastic $\begin{bmatrix} 1-p & q \\ p & 1-q \end{bmatrix}$ : steady state is $\dfrac{1}{p+q}(q, p)$ . Here $p = 0.3$ , $q = 0.4$ , giving $(0.4, 0.3)/0.7 = (4/7, 3/7)$ .

Solved: 0 / 4