Stochastic processes — Markov chains, steady-state, random walks: Worked examples

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

Shuru karne se pehle, do objects ka quick reminder jo hum baar baar use karte hain, simple shabdon mein:

Hume ek random number ko summarise karne ke do tarike bhi chahiye honge, toh inhe ek baar, abhi, define karte hain kisi bhi calculation se pehle:

The scenario matrix

Is chapter ka har problem exactly inhi cells mein se ek mein aata hai. Aage ke worked examples mein tag lagaye gaye hain ki woh kaun si cell cover karte hain, taaki milke poora grid fill ho jaaye.

#	Case class	Tricky kya hai	Covered by
A	Standard steady-state (2–3 states, simple numbers)	Solve $π = π P$ + normalise	Ex 1
B	Sign / direction of drift random walk mein ( $p \neq = q$ )	Mean ab $0$ nahi — kis taraf jhukta hai?	Ex 2
C	Zero / degenerate input: ek absorbing state ( $P_{ii} = 1$ )	Ek row jo tumhe "trap" karti hai — steady-state non-unique ho sakta hai	Ex 3
D	Limiting behaviour: $π^{(t)}$ kya approach karta hai, aur kitni tezi se?	The second eigenvalue speed control karta hai	Ex 4
E	Periodic / non-convergent chain	Distribution forever oscillate karta hai, $π$ exist karta hai lekin kabhi reach nahi hota	Ex 5
F	Real-world word problem (customer/machine model)	English → matrix translate karo, phir answer interpret karo	Ex 6
G	Gambler's ruin, biased ( $p \neq = q$ ) + expected duration	Linear formula kaam nahi karta; ek ratio formula aata hai	Ex 7
H	Exam twist: expected number of visits / first-passage	First-step analysis ek alag quantity par	Ex 8

Example 1 — Cell A: standard 3-state steady-state

Forecast: pehle guess karo — middle pad $2$ sabse reachable hai aur sab ko feed karta hai. Kya tumhe lagta hai usmein ends se compare mein zyada ya kam probability hogi? Apna guess likho.

Recall Setup: hum kaun si equation solve kar rahe hain?

$π = π P$ with $π_{1} + π_{2} + π_{3} = 1$ . Ye balance equation hai "inflow = there" har column ke liye.

Step 1. Teen balance equations likho, ek $P$ ke har column ke liye (ek column sab ki probability collect karta hai jo us state mein flow in karti hai). $π_{1} = 0.5 π_{1} + 0.25 π_{2}, π_{2} = 0.5 π_{1} + 0.5 π_{2} + 0.5 π_{3}, π_{3} = 0.25 π_{2} + 0.5 π_{3} .$ Ye step kyun? Har equation kehti hai "state $j$ mein baithi probability barabar hai total probability jo sabhi $i$ se flow in karti hai", jo exactly $π_{j} = \sum_{i} π_{i} P_{ij}$ hai.

Step 2. Equation 1 simplify karo: $0.5 π_{1} = 0.25 π_{2} \Rightarrow π_{1} = 0.5 π_{2}$ . Symmetry se, equation 3 deta hai $π_{3} = 0.5 π_{2}$ . Ye step kyun? $π_{1}$ term ko left side le jao; algebra collapse ho jaata hai kyunki chain left-to-right symmetric hai.

Step 3. Normalise karo: $π_{1} + π_{2} + π_{3} = 0.5 π_{2} + π_{2} + 0.5 π_{2} = 2 π_{2} = 1 \Rightarrow π_{2} = 0.5$ , toh $π_{1} = π_{3} = 0.25$ . Ye step kyun? Teeno fractions certainty ( $1$ ) mein add hone chahiye; woh scale pin karta hai.

$π = (0.25, 0.5, 0.25)$

Middle pad zyada hold karta hai — agar tumne yahi guess kiya tha toh good hai.

Example 2 — Cell B: biased random walk, drift kis taraf hai?

Forecast: $p > q$ , toh ye right lean karta hai. Lekin random wobble se compare mein kitna zyada 100 steps baad? Guess karo ki drift ya spread 100 steps baad jeet ta hai.

Figure kaise padhein. Horizontal axis steps ki number $n$ hai; vertical axis particle ki position $X_{n}$ hai. Teen patalee coloured lines individual random journeys hain. Thick navy line drift $E [X_{n}] = 0.2 n$ hai — average position, steadily label kiye hue point $(100, 20)$ tak chadh rahi hai. Do dashed navy lines spread band $E [X_{n}] \pm Var (X_{n})$ hain; unke beech shaded orange region woh jagah hai jahan ek typical path rehta hai. Visual lesson: drift line ek straight line mein tezi se upar jaati hai jabki shaded band sirf slowly phailta hai (jaise $n$ ), toh step $100$ tak drift ( $20$ ) ne wobble ( $\approx 9.8$ ) ko clearly peeche chhod diya hai.

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

Step 1. Ek step $S_{k}$ ka mean $E [S_{k}] = (+ 1) (0.6) + (- 1) (0.4) = 0.2$ . Ye step kyun? Upar di gayi expectation ki definition se, ek move ka mean = har outcome uski probability ke saath. Ye nonzero mean drift hai — constant lean jo parent note ke symmetric case mein nahi tha.

Step 2. $E [X_{100}] = \sum_{k = 1}^{100} E [S_{k}] = 100 \times 0.2 = 20$ . Ye step kyun? Expectation additive hai; identical steps ise $n$ times ek step bana dete hain. Drift linearly grow karta hai $n$ mein — ye figure mein steep straight navy line hai.

Step 3. Ek step ka variance, $Var (S_{k}) = E [S_{k}^{2}] - (E [S_{k}])^{2}$ use karte hue: pehle $E [S_{k}^{2}] = (+ 1)^{2} (0.6) + (- 1)^{2} (0.4) = 1$ , toh $Var (S_{k}) = 1 - (0.2)^{2} = 0.96$ . Ye step kyun? Ye exactly woh variance definition hai jo humne upar set ki thi. Kyunki steps independent hain, variances add hote hain: $Var (X_{100}) = 100 \times 0.96 = 96$ .

Step 4. Spread $= Var (X_{100}) = 96 \approx 9.80$ . Ye step kyun? Typical wobble standard deviation hai (variance ka square root) — figure mein shaded band ki half-width. Compare karo: drift $20$ vs wobble $\approx 9.80$ — drift jeet ta hai, toh particle reliably origin ke right mein hai.

Example 3 — Cell C: ek absorbing state (degenerate row)

Forecast: state $2$ bilkul symmetric hai $1$ aur $3$ ke beech ( $0.3$ dono ke liye). Padhe bina absorption probability guess karo.

Step 1. Maano $h = P (absorbed in 3 ∣ start in 2)$ . First-step analysis: $h = 0.3 go to 3 (1) + 0.4 h + 0.3 go to 1 (0) .$ Ye step kyun? State $2$ se, pehle move par condition karo (memorylessness). Seedha $3$ jaana prob $1$ se succeed karta hai; $1$ jaana fail karta hai; $2$ mein rehna hume wahi unknown $h$ ke saath chhodta hai.

Step 2. Solve karo: $h - 0.4 h = 0.3 \Rightarrow 0.6 h = 0.3 \Rightarrow h = 0.5$ . Ye step kyun? $h$ terms collect karo; self-loop $0.4 h$ left side jaata hai. Symmetry confirm hua: $h = 0.5$ .

Step 3. Stationary distributions. Yahan $π = π P$ solve karne se infinitely many milte hain: koi bhi $π = (a, 0, 1 - a)$ with $0 \leq a \leq 1$ kaam karta hai. Ye step kyun? Dono absorbing states apne aap mein stationary hain; unka koi bhi mixture bhi hoga. Ye non-uniqueness hai jiske baare mein parent note ne warn kiya tha — chain reducible hai (tum $1$ se $3$ nahi pahunch sakte).

$P (absorb in 3 ∣ start 2) = 0.5, π = (a, 0, 1 - a) .$

Example 4 — Cell D: $π^{(t)}$ kitni tezi se converge karta hai?

Forecast: har stochastic matrix mein eigenvalue $1$ hota hai. Doosra wala speed decide karta hai. Guess karo: $0$ ke paas hona matlab faster ya slower convergence?

Step 1. Eigenvalues solve karo $det (P - λ I) = 0$ se: $(0.8 - λ) (0.6 - λ) - (0.2) (0.4) = 0$ . Ye step kyun? Determinant exactly tab zero hota hai jab $P - λ I$ kisi vector ko zero pe squash kare — yaani woh vector ek eigenvector hai.

Step 2. Expand karo: $λ^{2} - 1.4 λ + (0.48 - 0.08) = λ^{2} - 1.4 λ + 0.4 = 0$ . Roots: $λ = 1$ aur $λ = 0.4$ . Ye step kyun? Quadratic factor karo. Jaisa promise kiya tha, $λ_{1} = 1$ ; mover hai $λ_{2} = 0.4$ .

Step 3. Decay ko $d (t) \approx ∣ λ_{2} ∣^{t} = 0. 4^{t}$ maanke, hum chahte hain $0. 4^{t} < 0.01$ : $t > \frac{l n 0.01}{l n 0.4} = \frac{- 4.605}{- 0.916} \approx 5.03.$ Ye step kyun? $t$ ko exponent se nikalne ke liye logs lo. Toh $6$ steps mein already total-variation distance $1%$ se neeche aa jaati hai.

$λ_{2} = 0.4, \approx 6 steps to 1%.$

Example 5 — Cell E: ek periodic chain jo kabhi converge nahi karta

Forecast: ye chain deterministically flip karta hai $1 \to 2 \to 1 \to 2$ . Stationary $π$ exist karta hai — lekin kya ek lopsided start kabhi settle karega? Guess karo haan/nahi.

Step 1. Solve karo $π = π P$ : $(π_{1}, π_{2}) (0110) = (π_{2}, π_{1})$ , toh $π_{1} = π_{2}$ . $π_{1} + π_{2} = 1$ ke saath: $π = (0.5, 0.5)$ . Ye step kyun? Balance equation ka ek solution hona — stationary distribution ka exist karna — convergence guarantee nahi karta.

Step 2. Ab $π^{(0)} = (1, 0)$ se iterate karo: $π^{(1)} = (0, 1), π^{(2)} = (1, 0), π^{(3)} = (0, 1), \dots$ Ye step kyun? $P$ se multiply karna sirf dono entries swap karta hai. Ye forever period $2$ ke saath oscillate karta hai, kabhi $(0.5, 0.5)$ tak nahi pahuncha.

$π = (0.5, 0.5) exist karta hai, lekin π^{(t)} oscillate karta hai aur kabhi converge nahi hota.$

Example 6 — Cell F: real-world word problem

Forecast: stickiness $0.9$ high hai, lekin win-back $0.2$ modest hai. Long-run subscribed fraction guess karo — $2/3$ se upar ya neeche?

Step 1. English ko matrix mein translate karo. States: $S$ (subscribed), $C$ (cancelled). $P = (0.9 0.2 0.1 0.8) .$ Ye step kyun? Row $S$ padhti hai "raho $0.9$ , jaao $0.1$ "; row $C$ padhti hai "wapas aao $0.2$ , gone raho $0.8$ ". Har row $1$ mein sum hoti hai ✔ — woh sum sanity check hai ki English sahi se ek valid transition matrix mein translate hui.

Step 2. $S$ column ke liye balance equation likho: $π_{S} = 0.9 π_{S} + 0.2 π_{C}$ . Ye step kyun? $S$ mein inflow = wo $90%$ jo subscribed rahe plus cancelled ke $20%$ jo wapas aaye; steady state mein ye $S$ mein baithe mass $π_{S}$ ke barabar hona chahiye.

Step 3. Rearrange karo: $π_{S} - 0.9 π_{S} = 0.2 π_{C} \Rightarrow 0.1 π_{S} = 0.2 π_{C} \Rightarrow π_{S} = 2 π_{C}$ . Ye step kyun? $π_{S}$ terms left par collect karo; leftover do unknowns ko ek clean ratio $2 : 1$ se relate karta hai.

Step 4. Normalise karo: $π_{S} + π_{C} = 2 π_{C} + π_{C} = 3 π_{C} = 1 \Rightarrow π_{C} = \frac{1}{3}, π_{S} = \frac{2}{3}$ . Ye step kyun? Dono fractions $1$ mein add hone chahiye (har customer exactly ek state mein hai); woh scale fix karta hai.

Step 5. Plain English mein interpret karo: long run mein har teen mein se do customers ( $66.7%$ ) kisi bhi given month mein subscribed hain, chahe company ne kaisi bhi shuruat ki ho. Ye step kyun? Problem ne ek real-world fraction maanga tha, toh hum vector ko words mein wapas translate karte hain — word problem ka point yahi hai.

$π = (\frac{2}{3}, \frac{1}{3}) : 66.7% subscribed long-run.$

Example 7 — Cell G: biased gambler's ruin + expected duration

Forecast: favourable game ke saath ( $p > q$ ), $2$ se $5$ tak pahunchna fair-game answer $2/5 = 0.4$ se zyada hona chahiye. Ek number guess karo.

Step 1. First-step equation setup karo. Maano $h_{i} = P (reach 5 before 0 ∣ start at i)$ . Pehle bet par condition karo: $h_{i} = p h_{i + 1} + q h_{i - 1}, h_{0} = 0, h_{5} = 1.$ Ye step kyun? Memorylessness: ek bet ke baad game restart karta hai $i + 1$ par (win) ya $i - 1$ par (loss). Boundaries certain hain — $0$ par tum already haar chuke, $5$ par already jeet chuke.

Step 2. Gap relation mein rearrange karo. $g_{i} = h_{i + 1} - h_{i}$ likho aur $p + q = 1$ use karo: $p g_{i} = q g_{i - 1} \Rightarrow g_{i} = r g_{i - 1}, r = \frac{q}{p} = \frac{0.4}{0.6} = \frac{2}{3} .$ Ye step kyun? $h_{i} = (p + q) h_{i}$ right mein move karo aur group karo. Successive gaps constant factor $r$ se shrink karte hain — ek geometric sequence, woh constant gaps nahi jo fair-game linear rule deta tha.

Step 3. $0$ se $i$ tak geometric gaps sum karo. Kyunki $h_{i} = h_{0} + \sum_{k = 0}^{i - 1} g_{k} = g_{0} (1 + r + \dots + r^{i - 1})$ aur $h_{5} = 1$ se $g_{0}$ fix hota hai, standard result nikalti hai: $h_{i} = \frac{1 - r ^{i}}{1 - r ^{N}}, N = 5.$ Ye step kyun? Finite geometric sum $1 + r + \dots + r^{i - 1} = \frac{1 - r ^{i}}{1 - r}$ ; wahi $\frac{1}{1 - r}$ upar aur neeche appear karta hai aur cancel ho jaata hai, clean ratio chhodhta hai.

Step 4. $i = 2$ , $N = 5$ , $r = 2/3$ plug karo: $h_{2} = \frac{1 - ( 2/3 ) ^{2}}{1 - ( 2/3 ) ^{5}} = \frac{1 - 4/9}{1 - 32/243} = \frac{5/9}{211/243} = \frac{5}{9} \cdot \frac{243}{211} = \frac{135}{211} \approx 0.640.$ Ye step kyun? Direct substitution. Answer $\approx 0.640 > 0.4$ — favourable edge help karta hai, jaisa forecast kiya tha.

Step 5 — part (b). $i / N$ kyun fail karta hai: fair-game derivation ne equal gaps assume ki thi $h_{i + 1} - h_{i} = h_{i} - h_{i - 1}$ , jo ek straight line force karti hai $h_{i} = i / N$ . Woh equality sirf tab holds karti hai jab $p = q$ ho (toh $r = 1$ ). Bias ke saath $r \neq = 1$ , gaps ek geometric sequence banate hain, $h_{i}$ ko favourable end ki taraf curve karte hue — walk far goal tak "linear" se zyada aasaani se pahunchta hai. Ye step kyun? Ye exactly woh assumption point karta hai jo break hoti hai, taaki tum jaano kab kaun sa formula legal hai.

$P (reach $5 ∣ $2) = \frac{135}{211} \approx 0.640.$

Example 8 — Cell H: exam twist — expected number of steps (first-passage)

Forecast: ye duration ke baare mein poochh raha hai, kaun si end ke baare mein nahi. Guess karo: kuch steps, ya bahut?

Step 1. Maano $τ_{i}$ = state $i$ se absorption tak expected steps. Count par first-step analysis: $τ_{i} = 1 + \frac{1}{2} τ_{i - 1} + \frac{1}{2} τ_{i + 1}, τ_{0} = τ_{3} = 0.$ Ye step kyun? Har move ek step cost karta hai (" $+ 1$ "), phir naye state se hum abhi bhi $τ_{i \pm 1}$ aur steps expect karte hain. Absorbing states $0$ cost karte hain (already done). Ye first-step analysis hai duration par apply hua — probability ki jagah — ye exam twist hai.

Step 2. Dono interior equations likho ( $i = 1, 2$ ): $τ_{1} = 1 + \frac{1}{2} (0) + \frac{1}{2} τ_{2}, τ_{2} = 1 + \frac{1}{2} τ_{1} + \frac{1}{2} (0) .$ Ye step kyun? Boundary values $τ_{0} = τ_{3} = 0$ substitute karo; do equations, do unknowns.

Step 3. Solve karo. Pehle se, $τ_{1} = 1 + \frac{1}{2} τ_{2}$ . Doosre mein substitute karo: $τ_{2} = 1 + \frac{1}{2} (1 + \frac{1}{2} τ_{2}) = 1.5 + \frac{1}{4} τ_{2} \Rightarrow \frac{3}{4} τ_{2} = 1.5 \Rightarrow τ_{2} = 2, τ_{1} = 1 + 1 = 2.$ Ye step kyun? Linear substitution. Symmetry se $τ_{1} = τ_{2} = 2$ sense banata hai — states $1$ aur $2$ mirror images hain.

$Expected steps from 1 = 2.$

Active Recall

Recall Kaun si cell

second eigenvalue maangti hai, aur kyun? Cell D (convergence speed). Sabse bada eigenvalue $1$ $π$ deta hai; $∣ λ_{2} ∣^{t}$ govern karta hai ki total-variation distance $π$ tak kitni tezi se decay karti hai.

Recall Biased random walk mein kaun sa

$n$ ki tarah grow karta hai aur kaun sa $n$ ki tarah? Drift (mean) $n$ ki tarah grow karta hai; spread (std dev) $n$ ki tarah grow karta hai. Large $n$ ke liye drift dominate karta hai.

Recall

$i / N$ biased gambler ke liye wrong kyun hai? Ye equal gaps $h_{i + 1} - h_{i}$ assume karta hai, jo sirf $p = q$ par sach hota hai. Bias ke saath gaps geometric hain ratio $q / p$ ke saath, jo $h_{i} = \frac{1 - r ^{i}}{1 - r ^{N}}$ deta hai.

Recall Absorbing states ek chain ki stationary distribution ko…

Non-unique bana dete hain (chain reducible hai): absorbing states ka koi bhi mixture stationary hota hai.

Recall Symmetric walk se

$i$ se ${0, \dots, N}$ par expected absorption time? $τ_{i} = i (N - i)$ .

Connections

Parent topic (woh machinery jis par ye examples apply hote hain)
Linear Algebra — Eigenvalues and Eigenvectors (Ex 4: $λ_{2}$ aur convergence rate)
Perron–Frobenius Theorem (Ex 3 & 5: uniqueness fail hoti hai reducible / periodic chains ke liye)
Law of Total Probability (first-step analysis Ex 3, 7, 8 mein)
Central Limit Theorem (Ex 2: biased walk → Gaussian around drift $n p$ )
Diffusion and Brownian Motion (Ex 2 & 8: $n$ spread aur passage times)
Google PageRank (Ex 6: ek real steady-state = long-run fractions)