Markov Chains & Long-Run Behavior

That column condition forces $\lambda = 1$ to be an eigenvalue (the all-ones vector is a left eigenvector), and its right eigenvector — normalized to sum to $1$ — is the steady state: the distribution the chain settles into regardless of where it started. Finding it is one homogeneous solve: $(M - I)\mathbf v = \mathbf 0$. All other eigenvalues have $|\lambda| \le 1$, and the second-largest, $|\lambda_2|$, sets the mixing rate: the memory of the starting state decays like $|\lambda_2|^n$. For the two-state chain in the figure, $M = \begin{pmatrix}0.7&0.4\\0.3&0.6\end{pmatrix}$ and $(M - I)\mathbf v = \mathbf 0$ reads $-0.3v_1 + 0.4v_2 = 0$, so $v_1 : v_2 = 4 : 3$ and the steady state is $\left(\tfrac47, \tfrac37\right)$. The other eigenvalue is $\operatorname{tr}M - 1 = 0.3$, so the memory of the start shrinks by a factor $0.3$ each step.

A state that advances with probability $p$ and stalls otherwise contributes $\tfrac1p$ expected steps (the geometric distribution). Gambler's ruin, board-game durations, drug absorption, and queue lengths are all this one linear system with different numbers.

Each step conditions on where the chain is now: the chance of landing in $i$ is $\sum_j M_{ij}\,x_j$, which is row $i$ of $M$ times $\mathbf x$. Repeating $n$ times gives $M^n$. For the closed form, the eigenvector of $\lambda_2$ must have entries summing to $0$ (column sums of $M$ are $1$, so $M$ preserves the total, and $\lambda_2\ne1$ forces total $0$); in two states that is $(1, -1)$. The distance to equilibrium therefore shrinks by the factor $|\lambda_2|$ every step.

Second step: $\mathbf x_2 = M\mathbf x_1 = (0.7\cdot0.7 + 0.4\cdot0.3,\ 0.3\cdot0.7 + 0.6\cdot0.3) = (0.49 + 0.12,\ 0.21 + 0.18) = (0.61, 0.39)$. Each entry sums over the ways to arrive: in A after two steps means A→A→A ($0.7\cdot0.7$) or A→B→A ($0.3\cdot0.4$). The entries still sum to $1$ ✓ — a quick check that the multiplication used rows, not columns.

Then

Check at $n = 2$: the first entry is $\tfrac47 + \tfrac37\cdot0.09 = \tfrac{4 + 0.27}{7} = \tfrac{4.27}{7} = 0.61$ ✓, matching the hand computation. The gap to equilibrium is $\tfrac37(0.3)^n$: about $0.13$ after one step, $0.0116$ after three, and under $10^{-4}$ after seven. This chain forgets its start fast because $\lambda_2$ is small.

$(M^2)_{AB} = 0.7\cdot0.4 + 0.4\cdot0.6 = 0.28 + 0.24 = 0.52$. The two terms are the two routes: B→A→A (probability $0.4\cdot0.7$) and B→B→A ($0.6\cdot0.4$). Matrix multiplication is exactly "sum over the intermediate state" — which is why powers of $M$ answer every multi-step question at once.

Condition on the first step. From $i$ the chain moves to $j$ with probability $p_{ij}$, and from there its chance of ending in $T$ is $h_j$ — the chain has no memory of how it got to $j$. Adding over $j$ gives the equation. The expected-time equation has the extra $1$ for the step just taken. Both are small linear systems, one unknown per transient state.

That equation says each $h_k$ is the average of its neighbors, so the $h_k$ lie on a straight line from $h_0 = 0$ to $h_4 = 1$: $h_k = \tfrac k4$, and $h_1 = \tfrac14$. The expected number of bets solves $E_k = 1 + \tfrac12E_{k-1} + \tfrac12E_{k+1}$ with $E_0 = E_4 = 0$, whose solution is $E_k = k(4 - k)$: $E_1 = 3$. Check: $E_2 = 4$, and $1 + \tfrac12(E_1 + E_3) = 1 + \tfrac12(3 + 3) = 4$ ✓. A fair game gives a winning chance equal to the fraction of the total money you start with.

Substitute the second into the first: $h_1 = \tfrac23\left(\tfrac13h_1 + \tfrac23\right) = \tfrac29h_1 + \tfrac49$, so $\tfrac79h_1 = \tfrac49$ and $h_1 = \tfrac47$. Then $h_2 = \tfrac13\cdot\tfrac47 + \tfrac23 = \tfrac{4 + 14}{21} = \tfrac67$. Check against the gambler's-ruin formula $h_k = \dfrac{1 - (q/p)^k}{1 - (q/p)^N}$ with $q/p = \tfrac12$, $N = 3$: $h_1 = \dfrac{1/2}{7/8} = \tfrac47$ ✓. Expected time: $E_1 = 1 + \tfrac23E_2$ and $E_2 = 1 + \tfrac13E_1$ give $E_1 = 1 + \tfrac23 + \tfrac29E_1$, so $E_1 = \tfrac{15}{7}$ and $E_2 = \tfrac{12}{7}$.

Moreover no eigenvalue can exceed $1$ in magnitude: if $M\mathbf v = \lambda\mathbf v$, comparing the largest-magnitude entry of both sides shows $|\lambda| \le 1$ (each entry of $M\mathbf v$ is a weighted average of entries of $\mathbf v$). $\blacksquare$ Significance: existence of a steady state is thus structural — probability is conserved, so equilibrium is guaranteed; the only question is how fast you get there, which is $|\lambda_2|$'s job.

Step 1 — transition matrix (columns from-state, rows to-state): $M = \begin{pmatrix}0.7&0.3&0.4\\0.3&0.5&0\\0&0.2&0.6\end{pmatrix}$; each column sums to $1$ ✓.

Step 2 — steady state solves $M\mathbf v = \mathbf v$: from row 2, $0.3s + 0.5r = r$ gives $r = 0.6s$; from row 3, $0.2r + 0.6c = c$ gives $c = 0.5r = 0.3s$.

Step 3 — normalize: $s + 0.6s + 0.3s = 1$, so $s = \dfrac{1}{1.9} = \dfrac{10}{19} \approx 52.6\%$ sunny, $r = \tfrac{6}{19}$, $c = \tfrac{3}{19}$.

Step 4 — verify row 1: $0.7\cdot\tfrac{10}{19} + 0.3\cdot\tfrac{6}{19} + 0.4\cdot\tfrac{3}{19} = \tfrac{7 + 1.8 + 1.2}{19} = \tfrac{10}{19}$ ✓. The forecast for a year from now needs no calendar — only this eigenvector.

Step 1 — let $E_k$ be the expected remaining time from position $k$, with $E_3 = 0$.

Step 2 — first-step analysis at each state: $E_k = 1 + \tfrac23E_{k+1} + \tfrac13E_k$, so $\tfrac23E_k = 1 + \tfrac23E_{k+1}$, i.e. $E_k = \tfrac32 + E_{k+1}$.

Step 3 — unwind from the end: $E_2 = 1.5$, $E_1 = 3$, $E_0 = 4.5$.

Step 4 — interpret: each step forward takes $\tfrac{1}{2/3} = 1.5$ expected seconds (geometric distribution), and three steps are needed — linearity of expectation gives $4.5$ directly, and the linear system confirms it.