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

4.10.27 · Maths › Advanced Topics (Elite Level)

1. What / Why / How

Memorylessness kyun matter karta hai: agar future poore past par depend karta, toh "rule" bina kisi seema ke bada hota jaata. Current state mein saari history collapse karke, poori dynamics ek fixed matrix $P$ mein fit ho jaati hai.

Distributions matrix multiplication se evolve hoti hain

Maano $π^{(t)}$ ek row vector hai jahan $π_{i}^{(t)} = P (X_{t} = i)$ .

Row vector ko $P$ se kyun multiply karte hain? Kyunki humne current state $i$ (row index) ke upar sum karte hue law of total probability use ki. Yahi exactly ek vector-matrix product hai.

2. Steady-State (Stationary Distribution)

$π$ unique aur reachable kab hai?

3. Random Walks

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

$n$ ki jagah $n$ kyun? Steps average par cancel ho jaate hain (mean 0), lekin variances add hote hain. Spread standard deviation $Var = n$ ki tarah badhta hai. Yahi diffusion ki pehchaan hai.

4. Common Mistakes (Steel-manned)

5. Active Recall

Recall Markov property ek sentence mein kya hai?

Future sirf present state par depend karta hai, past path par nahin.

Recall Distribution ek step mein kaise evolve hoti hai?

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

Recall Stationary distribution define karne wali equation?

$π = π P$ aur $\sum π_{i} = 1$ — $P$ ka left eigenvector eigenvalue 1 ke liye.

Recall

$n$ steps ke baad symmetric random walk ka mean aur variance? Mean $0$ , variance $n$ , typical distance $n$ .

Recall Gambler's ruin: fair game mein

$i$ se $N$ tak pahunchne ki probability? $i / N$ .

Recall (Feynman, ek 12-saal ke bachche ko explain karo) Yeh sab kya hai?

Socho ek frog lily pads ke beech kood raha hai. Woh agla kahan koodega yeh sirf is baat par depend karta hai ki abhi woh kis pad par hai — uski koi memory nahin hai. Agar aap bahut der tak dekhte raho, toh aap predict kar sakte hain ki woh kitna time har pad par bitaata hai: yahi steady-state hai. "Random walk" woh frog hai jo har kood mein coin flip karta hai left ya right jaane ke liye. Woh mostly ghar ke paas rehta hai, aur jitna woh bhatak jaata hai woh hops ki sankhya ke square root ki tarah badhta hai — dheema aur unsteady, seedha nahin.

Connections

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

Markov property states that

P (X_{t + 1} ∣ X_{t}, \dots, X_{0}) = P (X_{t + 1} ∣ X_{t})

— future sirf present par depend karta hai.

A transition matrix

P

is row-stochastic, meaning

har row ka sum 1 hota hai:

\sum_{j} P_{ij} = 1

Distribution after t steps from start

π^{(0)}

π^{(t)} = π^{(0)} P^{t}

Stationary distribution equation

π = π P

\sum_{i} π_{i} = 1

Why does eigenvalue 1 always exist for stochastic

P

kyunki

P 1 = 1

(rows ka sum 1 hai), isliye

1

ek eigenvalue hai; left eigenvector

π

deta hai.

Conditions for unique, convergent stationary distribution

irreducible + aperiodic.

Balance equation interpretation

ek state mein inflow = us state ki stationary probability:

π_{j} = \sum_{i} π_{i} P_{ij}

Mean position of symmetric random walk after n steps

Variance of symmetric random walk after n steps

n

(variances add hote hain, mean steps cancel ho jaate hain).

Typical distance travelled in n-step random walk

n

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

i / N

First-step analysis recurrence for

h_{i}

h_{i} = \frac{1}{2} h_{i - 1} + \frac{1}{2} 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 π

π P

π

ek row vector hai, isliye

π P

use karo (left multiplication).