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

4.10.27 · D2 · Maths › Advanced Topics (Elite Level) › Stochastic processes — Markov chains, steady-state, random w

Hum 2-state weather chain ko parent se apna running example use karte hain, kyunki do states ko flat picture mein draw karke frame by frame dekha ja sakta hai.

---

Step 1 — Duniya draw karo: states aur arrows

KYA. Hamare system mein exactly do possible situations hain, jinhe states kehte hain. Hum unhe naam dete hain:

• S = "aaj Sunny hai"
• R = "aaj Rainy hai"

Har subah weather in dono boxes mein se exactly ek mein hoti hai. Kal woh doosre box mein jump kar sakti hai ya reh sakti hai. Har jump ki chance ek fixed number hai jo kabhi nahi badlta — yahi poora "rule" hai.

ARROWS kyun draw karein. "80%" jaisa number invisible hai. S se S ki taraf ek arrow jis par $0.8$ likha ho, "agar sunny hai, toh 80% chance hai kal bhi sunny rahega" — isko aap point kar sakte ho. Chaar arrows poore system ka law carry karte hain.

PICTURE. Step figure 1 dekho. Do circles (states), chaar arrows (possible one-day moves), har arrow par uski probability likhi hai.

Reading the arrows off the picture:

$$P_{\text{SS}}=0.8,P_{\text{SR}}=0.2,P_{\text{RS}}=0.4,P_{\text{RR}}=\mathrm{0.6.}$$

---

Step 2 — Arrows ko ek grid mein pack karo (the matrix $P$)

KYA. Chaar alag labels ki jagah, unhe ek $2\times 2$ grid mein arrange karo taaki poori machine ek object ban jaye.

Grid kyun, aur yeh layout kyun. Hum ek bookkeeping table chahte hain jahan row = aaj, column = kal ho. Tab "aaj ki row se nikalne wale arrows" ek saath hote hain aur 1 tak sum honge — picture ka rule ban jaata hai "har row 1 tak add hoti hai".

PICTURE. Step figure 2: wahi chaar arrows, ab unke grid cells mein; row-sum $=1$ highlighted hai.

Kuch naya nahi hua hai — humne sirf chaar arrows ko reorganise kiya. Lekin ab poora rule ek single symbol $P$ hai.

---

Step 3 — Belief describe karo, fact nahi: probability vector

KYA. Hum rarely aaj ka weather yakeen se jaante hain; hum ek belief rakhte hain: "70% chance sunny, 30% chance rainy". Ise numbers ki ek pair ke roop mein likho.

Vector kyun, aur row kyun. Do beliefs ke liye do slots chahiye — length-2 ki list. Hum ise horizontally (ek row) likhte hain purpose se: Step 4 mein yeh row grid ki rows ke upar se slide karegi, aur woh motion hi belief ko arrows ke saath mix karna hai. Ise column ke roop mein likhna galat direction mein multiply karna hoga (yeh parent note ka classic $P\pi$ mistake hai).

PICTURE. Step figure 3: ek horizontal bar jo blue chunk (S par weight) aur orange chunk (R par weight) mein split hai, dono chunks bar ko poora bharti hain.

---

Step 4 — Belief ko ek din aage push karo (yahan $\pi P$ janam leta hai)

KYA. Aaj ki belief ${\pi }^{(t)}=(s,r)$ dete hue, kal Sun ki chance calculate karo.

Hum do channels sum kyun karte hain. Kal do alag raston se sunny ho sakta hai:

1. aaj sunny tha (weight $s$) aur sunny raha (arrow $0.8$),
2. aaj rainy tha (weight $r$) aur sunny mein flip hua (arrow $0.4$).

Yeh raaste overlap nahi karte (aaj ya toh S hai ya R, dono kabhi nahi), isliye hum unki chances add karte hain — phir se Law of Total Probability, ab kahan the ke upar sum karte hue.

PICTURE. Step figure 4: S circle mein pouring karte hue do coloured streams — blue stream $s\cdot 0.8$ aur orange stream $r\cdot 0.4$ — kal ki sunny probability mein merge hote hue.

Pattern notice karo: kal ki S entry paane ke liye humne row $(s,r)$ ko S-column $(0.8,0.4)$ ke neeche chalaya, pairs multiply kiye aur add kiye. Woh "har column ke upar slide-and-add" wahi operation hai jise hum row vector ko matrix se multiply karna kehte hain.

---

Step 5 — Numbers ko march (aur freeze) hote dekho

KYA. Ek lopsided belief se shuru karo, maano ${\pi }^{(0)}=(1,0)$ (certain hai ki aaj sunny hai), aur Step 4 baar baar apply karo.

Iterate kyun karein. Stationary claim long run ke baare mein hai. Ek equation mein "long run" nahi dekh sakte — sequence watch karke aur notice karke dekha jaata hai ki woh move karna band kar deti hai.

$$\begin{array}{rl}{\pi }^{(1)}& =(1,0)P=(0.8,0.2)\\ {\pi }^{(2)}& =(0.8,0.2)P=(0.72,0.28)\\ {\pi }^{(3)}& =(0.688,0.312)\\ & ⋮\\ {\pi }^{(\infty )}& \to (0.6\overline{6},0.3\overline{3})=(\frac{2}{3},\frac{1}{3}).\end{array}$$

${\pi }^{(3)}$ step ko Step 4 ke against check karo: sunny inflow $=0.72\cdot 0.8+0.28\cdot 0.4=0.576+0.112=0.688$, aur rainy $=0.72\cdot 0.2+0.28\cdot 0.6=0.144+0.168=0.312$. Har din $2/3$ se gap chhota hota jaata hai.

PICTURE. Step figure 5: S-probability ko day number ke against plot kiya gaya, $1$ se shuru hokar $2/3$ par ek flat dashed line ki taraf curve karta hua. Do alag starting beliefs dono usi same line ki taraf drain hoti hain.

---

Step 6 — Frozen equation: $\pi =\pi P$

KYA. "Frozen" ka matlab: ek aur din apply karne se kuch nahi badlta. Frozen belief ko $\pi =(s,r)$ kaho.

Yeh eigen-equation kyun ban jaata hai. "Ek aur din kuch nahi karta" literally $\pi P=\pi$ hai. Yahi $\pi$ ki definition hai ki woh $P$ ka left eigenvector hai eigenvalue $1$ ke saath (dekho Linear Algebra — Eigenvalues and Eigenvectors): ek direction jise machine unchanged chodti hai.

Step 4 ki S-equation mein ${\pi }^{(t+1)}={\pi }^{(t)}=\pi$ set karo:

$$\underset{\text{frozen S}}{\underbrace{s}}=\underset{\text{stay-sunny inflow}}{\underbrace{s\cdot 0.8}}+\underset{\text{rain-to-sun inflow}}{\underbrace{r\cdot 0.4}}.$$

PICTURE. Step figure 6: S circle jisme inflow arrows ek equal outflow arrow se balance hain — bilkul level see-saw. S mein flow andar equal hai S se flow bahar ke.

---

Step 7 — Edge aur degenerate cases (taaki koi scenario surprise na kare)

Sirf accha case dikhane wali picture ek trap hai. Yeh woh tarikay hain jis se "unique $\pi$ par settle karna" ki story toot sakti hai, Step figure 7 mein har ek ka apna frame hai.

Case A — ek trap door (reducible). Agar kuch arrows missing hain taaki ek state, ek baar enter hone ke baad, kabhi nahi chodi ja sake (absorbing state), toh belief usme drain ho jaati hai aur wahan reh jaati hai. Tab kai stationary distributions ho sakti hain — har trap ke liye ek — isliye $\pi$ unique nahi hai.

Case B — ek forced pendulum (periodic). Maano S se aap hamesha R jaate ho aur R se hamesha S wapas aate ho (arrows $0.8,0.4$ ki jagah $1$ aur $1$). Tab belief $(1,0)\to (0,1)\to (1,0)\to \dots$ hamesha flip karti rehti hai. Ek stationary $\pi =(\frac{1}{2},\frac{1}{2})$ phir bhi exist karti hai, lekin ek lopsided start kabhi iske converge nahi hota — woh sirf oscillate karta rehta hai.

Case C — healthy case (irreducible + aperiodic). Hamare weather chain mein ruke rehne ki kuch chance hai ($0.8,0.6>0$) aur har state har doosre tak pahunch sakti hai. Yeh dono bimariyan khatam karta hai: na traps, na forced cycle. Tab $\pi$ unique hai aur har start iske converge hota hai — guarantee Perron–Frobenius Theorem se aati hai.

PICTURE. Step figure 7: teen mini-diagrams side by side — ek trap door, ek rigid two-cycle, aur humari healthy self-looping chain — sirf teesre par ✓ hai.

---

Ek-picture summary

Upar sab kuch ek frame mein compress kiya: ek lopsided starting bar, arrow-grid $P$ har din ek baar kaam karta hai, belief-bar re-split aur drift karti hai, aur frozen $\frac{2}{3}:\frac{1}{3}$ line jahan inflow outflow ko balance karta hai.

$${\pi }^{(0)}\stackrel{\times P}{\to }{\pi }^{(1)}\stackrel{\times P}{\to }{\pi }^{(2)}\to \cdots ⟶\pi \text{where}\pi =\pi P,\sum {\pi }_i=1.$$

Recall Feynman retelling (poora walkthrough ek 12-saal ke bacche ko explain karo)

Ek frog ko do lily pads par imagine karo, Sunny-pad aur Rainy-pad. Har subah woh ek loaded coin flip karta hai jiske odds sirf us pad par depend karte hain jis par woh abhi baitha hai — kal par kabhi nahi. Maine woh odds arrows ke roop mein draw kiye (Step 1) aur unhe ek chote $2\times 2$ table mein stack kiya (Step 2). Frog kahan hai uska mera "andaza" maine ek bar ke roop mein likha jo ek blue part aur ek orange part mein split hai (Step 3). Kal andaza lagane ke liye, maine aaj ka blue aur orange arrows ke zariye har pad mein daala aur dekha kitna har par land hota hai (Step 4) — woh daalna hi mera row-andaza table se multiply karna hai, likha $\pi P$. Jab main baar baar daalta rahuun, toh split slide karna band kar deti hai aur two-thirds Sunny, one-third Rainy par lock ho jaati hai (Step 5), chahe main kahan se bhi shuru karuun. "Locked" ka matlab hai ek aur din daalna kuch nahi badlta, $\pi =\pi P$, jo simply yeh hai "ek pad mein utni hi probability flow in hoti hai jitni flow out hoti hai" — bilkul level see-saw (Step 6). Ek pakad yeh hai: yeh sirf tabhi nicely lock hota hai jab frog har pad tak pahunch sake aur metronome ki tarah alternate karne par majboor na ho; ek trap-pad ya rigid flip-flop ise tod deta hai (Step 7).

---

Connections

• Parent topic — poori theory jise yeh page draw karta hai.
• Linear Algebra — Eigenvalues and Eigenvectors — $\pi =\pi P$ eigenvalue $1$ ke liye ek left eigenvector hai.
• Perron–Frobenius Theorem — Case C mein uniqueness/convergence guarantee karta hai.
• Law of Total Probability — kal-ke-upar-se summing jo Step 4 build karta hai.
• Google PageRank — wahi $\pi =\pi P$ poore web par solve hota hai.