Foundations — Stochastic processes — Markov chains, steady-state, random walks

Before you can read the parent note, you need to earn every symbol it uses. Below, each item is: plain words → the picture → why the topic needs it. They are ordered so each one only leans on the ones above it.

---

1. A "state" and the state space $\{1,\dots ,n\}$

The picture: think of lily pads floating on a pond. Each pad is a state. If there are $3$ pads, the frog is always sitting on exactly one of pads $1$, $2$, or $3$ — never between them, never on two at once.

The collection of all pads is the state space, written $\{1,\dots ,n\}$. The curly braces $\{\}$ just mean "the set of all these things," and $n$ is however many there are.

Figure s01 — three lily pads labelled 1, 2, 3 (the state space) with a single frog dot resting on pad 2, captioned "the frog sits on exactly one state now." If the image does not load: picture a pond with three numbered pads and one frog on the middle one.

---

2. Time steps $t$ and the sequence $X_0,X_1,X_2,\dots$

The picture: film the hopping frog. Freeze frame $0$: the frog is on some pad — call that value $X_0$. Freeze frame $1$: it's on some pad now — that's $X_1$. Each freeze-frame gives one letter in the sequence $X_0,X_1,X_2,\dots$

Why the funny capital $X$? Because at each frame the outcome is uncertain until it happens. A quantity whose value is decided by chance is called a random variable. The subscript is time, not a power.

---

3. Probability $P(\text{something})$

The picture: a pie chart of possibilities. If the frog on pad 1 jumps to pad 2 half the time you watch it, the "jump to 2" slice fills half the pie: $P=0.5$.

The vertical bar "$\mid$" inside, as in $P(A\mid B)$, is read "given" — it means "the probability of $A$, knowing that $B$ already happened." It narrows the pie down to only the cases where $B$ is true.

---

3b. The Law of Total Probability (stated here, in full)

We will need one law by name to build the update rule later, so let us state it now — self-contained, no clicking away.

In words: to get the total chance of $A$, split into every possible starting situation $B_i$, multiply "how likely that situation is" ($P(B_i)$) by "how likely $A$ is from there" ($P(A\mid B_i)$), and add all the pieces.

The picture: the pie of "all ways to reach $A$" is cut into slices, one slice per starting situation $B_i$; each slice's size is $P(B_i)\times P(A\mid B_i)$; adding the slices rebuilds the whole $A$-pie.

For the deeper treatment and proofs, see Law of Total Probability.

---

4. The Markov property (memorylessness)

Reading it left to right: the left side says "chance of landing on pad $j$ next, given the entire history — where I am now ($X_t=i$) and every pad I visited before." The right side throws all the old history away and keeps only $X_t=i$. The equals sign claims: they are the same number.

The picture: cover up the whole film reel except the current frame. The Markov property says you can still predict the next frame just as well — the covered-up past told you nothing extra.

---

5. The transition matrix $P$ and the entry $P_{ij}$

The picture: a table. Rows are labelled "where I am now," columns "where I go next." To find the chance of going from pad 1 to pad 2, look down row 1, across to column 2.

Figure s02 — a 3×3 grid of transition probabilities with rows labelled "from 1/2/3" and columns "to 1/2/3"; the cell $P_{12}=0.2$ is highlighted, and a note reminds "each row sums to 1." If the image does not load: imagine a table where reading across any row gives probabilities that add to 1.

Why every row must sum to 1

The big sigma ${\sum }_{j=1}^n$ is just shorthand for "add these up as $j$ runs from 1 to $n$": $P_{i1}+P_{i2}+\cdots +P_{in}$.

Why it equals 1: from pad $i$ the frog must land somewhere next step. "Somewhere" is certain, and certainty is probability $1$. So the whole row (all destinations) adds to $1$. A grid where every row sums to 1 is called row-stochastic.

---

6. The probability vector $\pi$ (and ${\pi }^{(t)}$)

The picture: instead of pinning the frog to one pad, imagine a cloud of probability smeared across the pads — 60% chance on pad 1, 40% on pad 2 would be the row $(0.6,0.4)$. The heights of these bars add to one full unit of certainty.

The Greek letter $\pi$ (say "pie") is just a name — here it has nothing to do with 3.14159. The superscript $(t)$ in brackets is a time label (again, not a power); when we drop it and write plain $\pi$, we mean the special "settled" list from Section 8.

Figure s03 — two bar charts side by side: the left one shows ${\pi }^{(t)}=(0.6,0.3,0.1)$ as three bars, an arrow labelled "×P" points right, and the right one shows the updated ${\pi }^{(t+1)}=(0.51,0.29,0.20)$; both sets of bars add to 1. If the image does not load: picture three probability bars being reshuffled into three new bars by multiplying by P.

---

7. Vector × matrix: what $\pi P$ actually computes

Why this exact combination? It is the Law of Total Probability from Section 3b, applied with $A=$ "in state $j$ next step" and $B_i=$ "in state $i$ now": $P(B_i)={\pi }_i$ and $P(A\mid B_i)=P_{ij}$, so $P(A)={\sum }_i{\pi }_i{P}_{ij}$. Sum over every possible "where you were" $i$. That summing-and-weighting is what "row vector times matrix" means.

The picture: each column $j$ of $P$ is a set of "pipes" pouring probability into pad $j$. Multiply each incoming pipe by how much probability sits at its source, pour it all into the bucket $j$. The refilled buckets are the new vector.

Recall Why row × matrix and not matrix × column?

Because we summed over the current state $i$, which is the row index of $P$. Summing over a row index is exactly a left-multiplication $\pi P$.

---

8. The stationary distribution $\pi =\pi P$

The picture: the probability cloud finally stops sloshing. Every pad's height is exactly refilled by what pours in — the buckets look identical before and after a step. The frog still hops, but the cloud is frozen.

---

9. Eigenvalue / eigenvector — the deep reason $\pi$ exists

The picture: most vectors get both stretched and rotated by a matrix. An eigenvector is a rare arrow lying on a "special axis" — the matrix slides it along its own line, only lengthening or shrinking it by factor $\lambda$.

Look at the stationary equation $\pi =\pi P$ again: it is $\pi P=1\cdot \pi$. So $\pi$ is a left eigenvector of $P$ with eigenvalue $\lambda =1$ — the direction $P$ leaves completely unchanged. That is why the topic reaches for eigenvectors at all: "unchanged by the step" is literally the eigenvalue-1 equation.

For the full machinery, see Linear Algebra — Eigenvalues and Eigenvectors; for why it's unique and reached, see the Perron–Frobenius Theorem.

---

10. Expected value, variance, and the $\sqrt{n}$ spread (random walks)

Worked step for a single coin-flip step $S$ (value $+1$ with prob $\frac{1}{2}$, $-1$ with prob $\frac{1}{2}$): $E[S]=(+1)\cdot \frac{1}{2}+(-1)\cdot \frac{1}{2}=0,\mathrm{Var}(S)=E[S^2]-E[S{]}^2=1-0=1,$ using $E[S^2]=(+1{)}^2\frac{1}{2}+(-1{)}^2\frac{1}{2}=1$.

Why the square root $\sqrt{n}$ shows up: in a coin-flip walk of $n$ steps, the average position is $0$ (left cancels right), but the variances add to $n$ (one unit per independent step). The natural "width" is the square root of the variance, $\sqrt{n}$ — so after $n$ hops the frog typically strays a distance about $\sqrt{n}$, not $n$. This slow spreading is the seed of the Central Limit Theorem and Diffusion and Brownian Motion.

---

Prerequisite map

Every arrow means "you need the box behind before the box ahead." This whole map feeds the parent topic the Markov chains topic, and its endpoints reach out to Google PageRank, which is just a stationary distribution on the web.

---

Equipment checklist

Cover the right side and answer aloud. If you stumble, reread that section above.

---

Connections

• Law of Total Probability — the "sum over where you were" behind $\pi P$.
• Linear Algebra — Eigenvalues and Eigenvectors — the $wM=\lambda w$ idea used for $\pi$.
• Perron–Frobenius Theorem — why eigenvalue 1 is special, unique, and reached.
• Central Limit Theorem — where the $\sqrt{n}$ spread leads.
• Diffusion and Brownian Motion — the continuous cousin of the random walk.
• Google PageRank — a giant stationary distribution in the wild.