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

1. What / Why / How

WHY memorylessness matters: if the future depended on the full past, the "rule" would grow without bound. By collapsing all history into the current state, the entire dynamics fit into one fixed matrix $P$ .

Distributions evolve by matrix multiplication

Let $\pi^{(t)}$ be a row vector where $\pi^{(t)}_i = P(X_t=i)$ .

WHY a row vector times $P$ ? Because we used the law of total probability summing over the current state $i$ (the row index). That is exactly a vector-matrix product.

2. Steady-State (Stationary Distribution)

When is $\pi$ unique & reached?

3. Random Walks

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

WHY $\sqrt n$ not $n$ ? Steps cancel on average (mean 0), but variances add. Spread grows like the standard deviation $\sqrt{\mathrm{Var}}=\sqrt n$ . This is the signature of diffusion.

4. Common Mistakes (Steel-manned)

5. Active Recall

Recall What is the Markov property in one sentence?

The future depends only on the present state, not on the past path.

Recall How does a distribution evolve one step?

$\pi^{(t+1)}=\pi^{(t)}P$ (row vector × transition matrix).

Recall Equation defining the stationary distribution?

$\pi=\pi P$ with $\sum\pi_i=1$ — left eigenvector of $P$ for eigenvalue 1.

Recall Mean and variance of a symmetric random walk after

$n$ steps? Mean $0$ , variance $n$ , typical distance $\sqrt n$ .

Recall Gambler's ruin: probability of reaching

$N$ from $i$ (fair game)? $i/N$ .

Recall (Feynman, explain to a 12-year-old) What is all this?

Imagine a frog hopping between lily pads. Where it jumps next depends only on which pad it's on right now — it has no memory. If you watch for a very long time, you can predict what fraction of time it spends on each pad: that's the steady-state. A "random walk" is the frog flipping a coin each hop to go left or right. It mostly stays near home, and the distance it strays grows like the square root of the number of hops — slow and wobbly, not straight.

Connections

Linear Algebra — Eigenvalues and Eigenvectors (steady-state = eigenvalue 1)
Perron–Frobenius Theorem (uniqueness & convergence)
Law of Total Probability (derives the update rule)
Central Limit Theorem (random walk → Gaussian, spread $\sqrt n$ )
Diffusion and Brownian Motion (continuous limit of random walks)
Google PageRank (stationary distribution of a web Markov chain)

Markov property states that

P(X_{t+1}\mid X_t,\dots,X_0)=P(X_{t+1}\mid X_t)

— future depends only on present.

A transition matrix

P

is row-stochastic, meaning

each row sums to 1:

\sum_j P_{ij}=1

Distribution after t steps from start

\pi^{(0)}

\pi^{(t)}=\pi^{(0)}P^{t}

Stationary distribution equation

\pi=\pi P

\sum_i\pi_i=1

Why does eigenvalue 1 always exist for stochastic

P

because

P\mathbf{1}=\mathbf{1}

(rows sum to 1), so

1

is an eigenvalue; left eigenvector gives

\pi

Conditions for unique, convergent stationary distribution

irreducible + aperiodic.

Balance equation interpretation

inflow into a state = stationary probability of that state:

\pi_j=\sum_i\pi_iP_{ij}

Mean position of symmetric random walk after n steps

Variance of symmetric random walk after n steps

n

(variances add, mean steps cancel).

Typical distance travelled in n-step random walk

\sqrt n

Gambler's ruin (fair) probability of hitting N before 0 from i

i/N

First-step analysis recurrence for

h_i

h_i=\tfrac12 h_{i-1}+\tfrac12 h_{i+1}

h_0=0,h_N=1

2-state chain

P=[[0.8,0.2],[0.4,0.6]]

steady state

(2/3,1/3)

Common error:

P\pi

\pi P

\pi

is a row vector, so use

\pi P

(left multiplication).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek frog alag-alag lily pads pe jump kar raha hai. Markov chain ka matlab simple hai: frog agla jump sirf current pad dekh ke decide karta hai — uski koi memory nahi ki pehle kahan tha. Isi "memorylessness" ki wajah se sab kuch ek choti si transition matrix $P$ me aa jaata hai. Har row ka sum 1 hota hai, kyunki frog ko kahin na kahin to jaana hi hai (total probability = 1).

Probability distribution ko hum ek row vector $\pi$ se likhte hain, aur ek step aage badhne ke liye bas $\pi P$ multiply karte hain. Yaad rakho: $\pi P$ , na ki $P\pi$ — kyunki $\pi$ row vector hai. Agar chain ko bahut der tak chalao, to distribution settle ho jaata hai ek fixed value pe jise steady-state ya stationary distribution $\pi$ kehte hain, jahan $\pi = \pi P$ . Iska matlab har state me "jitna andar aa raha hai utna hi bahar ja raha hai" — balance. Weather example me sunny din 2/3 time aur rainy 1/3 time aate hain, chahe shuruaat kahin se bhi ho.

Random walk ek special Markov chain hai jahan har step pe coin flip karke +1 ya -1 jaate ho. Average position 0 rehti hai (kyunki dono taraf equal cancel ho jaate hain), par spread $\sqrt{n}$ ke hisaab se badhta hai — yahi diffusion ka signature hai. Yaad rakho: mean grow nahi karta, spread grow karta hai. Gambler's ruin me agar fair game hai aur tum $i se start karke $N tak pohuchna chahte ho, to probability simply$ i/N$ hai — ye "first-step analysis" se nikalta hai, jisme tum pehle step ko condition karte ho aur Markov property se chain restart ho jaati hai.

Ye topic important hai kyunki PageRank (Google search), physics ki diffusion, finance, aur queueing — sab Markov chains pe khade hain. Ek baar steady-state aur $\sqrt n$ rule samajh gaye, to bahut saari real-world systems predict kar sakte ho.

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

1. What / Why / How

Distributions evolve by matrix multiplication

2. Steady-State (Stationary Distribution)

When is $\pi$ unique & reached?

3. Random Walks

4. Common Mistakes (Steel-manned)

5. Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Topics (Elite Level)

Connections