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

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

Parent note padhne se pehle, tumhe har ek symbol khud earn karna hoga jo woh use karta hai. Neeche, har item kuch is tarah hai: plain words → the picture → topic ko yeh kyun chahiye. Inhe is tarah order kiya gaya hai ki har ek sirf upar waalon par hi depend kare.

1. Ek "state" aur state space $\{1,\dots ,n\}$

Picture: socho ek pond mein tairte lily pads. Har pad ek state hai. Agar $3$ pads hain, toh frog hamesha exactly ek hi pad $1$, $2$, ya $3$ par baitha hoga — kabhi beech mein nahi, kabhi ek saath dono par nahi.

Saare pads ka collection state space kehlata hai, jo $\{1,\dots ,n\}$ likha jaata hai. Curly braces $\{\}$ ka matlab bas "in sab cheezaon ka set" hai, aur $n$ jitne bhi hain woh hain.

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

Picture: hopping frog ki film banao. Freeze frame $0$: frog kisi pad par hai — us value ko $X_0$ kaho. Freeze frame $1$: woh ab kisi pad par hai — woh $X_1$ hai. Har freeze-frame sequence $X_0,X_1,X_2,\dots$ mein ek letter deta hai.

Yeh funny capital $X$ kyun? Kyunki har frame par outcome tab tak uncertain hota hai jab tak woh ho nahi jaata. Woh quantity jिसकी value chance se decide hoti hai use random variable kehte hain. Subscript time hai, power nahi.

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

Picture: possibilities ka pie chart. Agar pad 1 par frog aadhe time pad 2 par jump karta hai jab tum use dekhte ho, toh "jump to 2" slice pie ka aadha hissa fill karta hai: $P=0.5$.

Vertical bar "$\mid$" andar, jaise $P(A\mid B)$ mein, "given" padha jaata hai — iska matlab hai "$A$ ki probability, yeh jaante hue ki $B$ pehle ho chuka hai." Yeh pie ko sirf un cases tak narrow kar deta hai jahan $B$ sach hai.

3b. Law of Total Probability (yahan poora bataya gaya hai)

Baad mein update rule banane ke liye hume ek law naam se chahiye hogi, toh chaliye use ab state karte hain — self-contained, bina kahi aur click kiye.

Words mein: $A$ ka total chance paane ke liye, har possible starting situation $B_i$ mein split karo, "woh situation kitni likely hai" ($P(B_i)$) ko "wahan se $A$ kitna likely hai" ($P(A\mid B_i)$) se multiply karo, aur saare pieces add karo.

Picture: "$A$ tak pahunchne ke saare raaste" ka pie har starting situation $B_i$ ke liye ek slice mein cut hota hai; har slice ka size $P(B_i)\times P(A\mid B_i)$ hai; slices add karne se poora $A$-pie wapas ban jaata hai.

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

4. Markov property (memorylessness)

Ise left se right padhna: left side kehta hai "pad $j$ par next land karne ka chance, poori history given — main abhi kahan hoon ($X_t=i$) aur pehle maine jo bhi pad visit kiye." Right side poori purani history throw away kar deta hai aur sirf $X_t=i$ rakhta hai. Equals sign claim karta hai: woh same number hain.

Picture: poori film reel cover kar do sirf current frame chhodke. Markov property kehti hai tum phir bhi next frame utna hi well predict kar sakte ho — dhaka hua past tumhe kuch extra nahi bata raha tha.

5. Transition matrix $P$ aur entry $P_{ij}$

Picture: ek table. Rows label hain "main abhi kahan hoon," columns "main aage kahan jaata hoon." Pad 1 se pad 2 jaane ka chance paane ke liye, row 1 se neeche dekho, column 2 tak across jaao.

Har row 1 kyun sum honi chahiye

Big sigma ${\sum }_{j=1}^n$ bas shorthand hai "$j$ ke $1$ se $n$ tak run karne par inhe add karo" ke liye: $P_{i1}+P_{i2}+\cdots +P_{in}$.

Yeh 1 kyun equals karta hai: pad $i$ se frog next step kahi na kahi land karna hi hai. "Kahi na kahi" certain hai, aur certainty probability $1$ hai. Toh poori row (saare destinations) $1$ tak add hoti hai. Jis grid ki har row 1 sum hoti hai use row-stochastic kehte hain.

6. Probability vector $\pi$ (aur ${\pi }^{(t)}$)

Picture: frog ko ek pad par pin karne ki bajaye, imagine karo probability ka ek cloud pads par spread hai — 60% chance pad 1 par, 40% pad 2 par toh woh row $(0.6,0.4)$ hogi. Inhe bars ki tarah socho jo ek poori unit of certainty tak add hoti hain.

Greek letter $\pi$ (bolte hain "pie") bas ek naam hai — yahan iska 3.14159 se koi lena-dena nahi. Brackets mein superscript $(t)$ ek time label hai (phir se, power nahi); jab hum ise drop karte hain aur plain $\pi$ likhte hain, toh hum Section 8 ki special "settled" list ki baat karte hain.

7. Vector × matrix: $\pi P$ actually kya compute karta hai

Yeh exactly yeh combination kyun? Yeh Section 3b ka Law of Total Probability hai, $A=$ "next step state $j$ mein" aur $B_i=$ "abhi state $i$ mein" ke saath apply kiya gaya: $P(B_i)={\pi }_i$ aur $P(A\mid B_i)=P_{ij}$, toh $P(A)={\sum }_i{\pi }_i{P}_{ij}$. Har possible "tum kahan the" $i$ par sum karo. Woh summing-and-weighting hi woh hai jo "row vector times matrix" ka matlab hai.

Picture: $P$ ka har column $j$ "pipes" ka ek set hai jo probability pad $j$ mein pour kar raha hai. Har incoming pipe ko multiply karo us probability se jo uske source par baitha hai, sab bucket $j$ mein pour karo. Refilled buckets nayi vector hain.

8. Stationary distribution $\pi =\pi P$

Picture: probability cloud finally sloshing band ho jaata hai. Har pad ki height exactly wahi refill hoti hai jo andar pour hoti hai — buckets ek step se pehle aur baad mein identical dikhte hain. Frog abhi bhi hop kar raha hai, lekin cloud freeze hai.

9. Eigenvalue / eigenvector — deep reason kyun $\pi$ exist karta hai

Picture: zyaadatar vectors matrix se both stretch aur rotate hote hain. Ek eigenvector ek rare arrow hai jo ek "special axis" par lie karta hai — matrix ise uski apni line par slide karta hai, sirf $\lambda$ factor se lengthen ya shrink karta hai.

Stationary equation $\pi =\pi P$ dobara dekho: yeh $\pi P=1\cdot \pi$ hai. Toh $\pi$ ek left eigenvector of $P$ with eigenvalue $\lambda =1$ hai — woh direction jिसे $P$ bilkul unchanged chodta hai. Isliye topic eigenvectors ki taraf jaata hai: "step se unchanged" literally eigenvalue-1 equation hai.

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, aur $\sqrt{n}$ spread (random walks)

Ek single coin-flip step $S$ ke liye worked step (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$.

Square root $\sqrt{n}$ kyun aata hai: $n$ steps ki coin-flip walk mein, average position $0$ hai (left right cancel karta hai), lekin variances add hote hain $n$ tak (har independent step mein ek unit). Natural "width" variance ka square root hai, $\sqrt{n}$ — toh $n$ hops ke baad frog typically $\sqrt{n}$ ki distance stray karta hai, $n$ nahi. Yeh slow spreading Central Limit Theorem aur Diffusion and Brownian Motion ka seed hai.

Prerequisite map

Har arrow ka matlab hai "box aage wale se pehle peeche wala box chahiye." Yeh poora map parent topic the Markov chains topic ko feed karta hai, aur iske endpoints Google PageRank tak reach karte hain, jo web par bas ek stationary distribution hai.

Equipment checklist

Right side cover karo aur aloud jawab do. Agar tum stumble karo, toh upar woh section dobara padho.

Connections

• Law of Total Probability — $\pi P$ ke peeche "sum over where you were."
• Linear Algebra — Eigenvalues and Eigenvectors — $\pi$ ke liye use kiya gaya $wM=\lambda w$ idea.
• Perron–Frobenius Theorem — eigenvalue 1 special, unique, aur reached kyun hai.
• Central Limit Theorem — jahan $\sqrt{n}$ spread le jaata hai.
• Diffusion and Brownian Motion — random walk ka continuous cousin.
• Google PageRank — ek giant stationary distribution wild mein.