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

Kaunsa rule? Ek transition matrix row-stochastic hona chahiye: har row ek list hai probabilities ki kahi bhi jaane ki, isliye har row ka sum $1$ hona chahiye (parent note, §1). Entries bhi $\ge 0$ honi chahiyein.

Row by row check karo:

• Row 1 (state 1 se): $0.5+0.5=1$ ✔
• Row 2 (state 2 se): $0.3+0.7=1$ ✔
• Sabhi entries $\ge 0$ ✔

Answer: Haan, yeh ek valid transition matrix hai.

Kaun sa product? Update rule hai ${\pi }^{(t+1)}={\pi }^{(t)}P$ — ek row vector times the matrix (parent, §1, "Row times P"). Hum current state $i$ par sum karte hain, jo $P$ ka row index hai, aur woh summation exactly ek row-vector–matrix product hai. Toh correct product hai ${\pi }^{(0)}P$.

Compute karo (row vector rule: naya $j$-th entry $={\sum }_i{\pi }_i^{(0)}{P}_{ij}$): ${\pi }_1^{(1)}=0.6(0.5)+0.4(0.3)=0.30+0.12=0.42$ ${\pi }_2^{(1)}=0.6(0.5)+0.4(0.7)=0.30+0.28=0.58$ Answer: ${\pi }^{(1)}=(0.42,0.58)$. (Sanity: yeh $1$ mein sum hota hai. Achha — probability conserved hai.)

Hum kya chahte hain: woh row vector $\pi$ jo ek step baad bhi unchanged rahe, yaani $\pi =\pi P$ with $a+b=1$ (parent, §2). "In equals There."

$\pi P=\pi$ ko component by component likhte hain: $a=0.5a+0.3b(\text{state 1 mein inflow})$ $b=0.5a+0.7b(\text{state 2 mein inflow})$

Pehli equation use karo (dono equations $2\times 2$ chain ke liye hamesha redundant hoti hain; isliye hume normalisation bhi chahiye): $a-0.5a=0.3b\Rightarrow 0.5a=0.3b\Rightarrow a=0.6b.$

Normalise karo $a+b=1$ se: $0.6b+b=1\Rightarrow 1.6b=1\Rightarrow b=\frac{1}{1.6}=0.625,a=\mathrm{0.375.}$

Answer: $\pi =(0.375,0.625)=\left(\frac{3}{8},\frac{5}{8}\right)$.

Plan: "Row times P" do baar apply karo: ${\pi }^{(1)}={\pi }^{(0)}P$, phir ${\pi }^{(2)}={\pi }^{(1)}P$. (Equivalently ${\pi }^{(2)}={\pi }^{(0)}{P}^2$.)

Day 1: ${\pi }_1^{(1)}=1(0.8)+0(0.4)=0.8,{\pi }_2^{(1)}=1(0.2)+0(0.6)=\mathrm{0.2.}$ So ${\pi }^{(1)}=(0.8,0.2)$.

Day 2: ${\pi }_1^{(2)}=0.8(0.8)+0.2(0.4)=0.64+0.08=0.72,$ ${\pi }_2^{(2)}=0.8(0.2)+0.2(0.6)=0.16+0.12=\mathrm{0.28.}$

Answer: ${\pi }^{(2)}=(0.72,0.28)$. Notice karo yeh already stationary $(\frac{2}{3},\frac{1}{3})\approx (0.667,0.333)$ ki taraf creep kar raha hai jo parent note mein hai — convergence in action.

Let each step be $S_k\in \{+1,-1\}$ and $X_n={\sum }_{k=1}^n{S}_k$ (parent, §3).

(a) Mean. $E[S_k]=(+1)\frac{1}{2}+(-1)\frac{1}{2}=0$. Means ka sum: $E[X_{100}]={\sum }_{k=1}^{100}0=\boxed{0}$.

(b) Variance. $E[S_k^2]=(+1{)}^2\frac{1}{2}+(-1{)}^2\frac{1}{2}=1$, toh $\mathrm{Var}(S_k)=1-0^2=1$. Steps independent hain, aur independent cheezein ki variances add hoti hain: $\mathrm{Var}(X_{100})={\sum }_{k=1}^{100}1=\boxed{100}$.

(c) Typical distance $=$ standard deviation $=\sqrt{\mathrm{Var}(X_{100})}=\sqrt{100}=\boxed{10}$.

Kyun antar hai: Mean ek signed average hai — leftward aur rightward wanderings cancel ho jaati hain, giving $0$. Lekin spread sign ki parwah nahi karta; har step variance mein $+1$ contribute karta hai chahe woh left gaya ho ya right. Toh possible positions ka cloud $\sqrt{n}$ ki tarah wider hota jaata hai, bhale hi uska center $0$ par hi atka raha ho. Figure dekho — center (amber line) flat hai jabki $\pm \sqrt{n}$ envelope (cyan) fan out ho raha hai.

Recurrence ko rearrange karo shape expose karne ke liye: $h_i=\frac{1}{2}{h}_{i-1}+\frac{1}{2}{h}_{i+1}⟹2h_i=h_{i-1}+h_{i+1}⟹h_{i+1}-h_i=h_i-h_{i-1}.$

Ise zor se padho: consecutive values ke beech ka gap, $d_i:=h_{i+1}-h_i$, satisfy karta hai $d_i=d_{i-1}$. Toh har gap ek same constant $d$ hai. Constant steps wali sequence ek arithmetic progression hai — yaani ek straight line: $h_i=h_0+id=0+id=id$.

Constant pin karo doosri boundary $h_N=1$ use karke: $h_N=Nd=1\Rightarrow d=\frac{1}{N}\Rightarrow \boxed{h_i=\frac{i}{N}}.$

Geometry: constant gaps = $(0,0)$ se $(N,1)$ tak ek ramp. Neeche straight amber line dekho.

(a) Stationary $\pi =(a,b)$, $a+b=1$, solve $\pi P=\pi$: $\pi P=(a,b)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=(b,a).$ Set karo $(b,a)=(a,b)\Rightarrow a=b$. $a+b=1$ se: $\boxed{\pi =(\frac{1}{2},\frac{1}{2})}$. Ek stationary distribution exist karti hai.

(b) ${\pi }^{(0)}=(1,0)$ se iterate karo: ${\pi }^{(1)}=(1,0)P=(0,1),{\pi }^{(2)}=(0,1)P=(1,0),{\pi }^{(3)}=(0,1),\dots$ Yeh oscillate karta rehta hai $(1,0)\to (0,1)\to (1,0)\to \cdots$ forever, kabhi $(\frac{1}{2},\frac{1}{2})$ ke paas nahi aata. Toh ${\pi }^{(t)}\nrightarrow \pi$.

(c) Kaun si condition fail hoti hai? Aperiodicity. Is chain ki period 2 hai: state 1 se tum state 1 par sirf even number of steps ($2,4,6,\dots$) ke baad wapas aa sakte ho. Forced cycle length $>1$ hai, toh chain periodic hai. Irreducibility holds (har state doosre tak pahunch sakti hai), lekin Perron–Frobenius convergence guarantee (Perron–Frobenius Theorem) ko dono irreducible aur aperiodic chahiye. Aperiodicity missing hone par ⇒ ek $\pi$ jo exist karti hai lekin kabhi reach nahi hoti.

(Eigenvalue view: $P$ ke eigenvalues $+1$ aur $-1$ hain. $-1$ eigenvalue ki magnitude $1$ hai, isliye uska contribution kabhi decay nahi karta — woh har step sign flip karta hai, eternal oscillation produce karta hai. Aperiodicity exactly woh condition hai ki $1$ hi only eigenvalue ho magnitude $1$ wala. Dekho Linear Algebra — Eigenvalues and Eigenvectors.)

(a) Row sums: har row mein ek single $1$ aur do $0$ hain → sum $=1$. ✔ Row-stochastic.

(b) Stationary $\pi =(a,b,c)$, solve $\pi P=\pi$. $\pi P$ compute karo (row vector rule, column by column):

• $P$ ka Column 1 hai $(0,0,1{)}^{\top }$: $(\pi P{)}_1=a(0)+b(0)+c(1)=c$.
• Column 2 hai $(1,0,0{)}^{\top }$: $(\pi P{)}_2=a$.
• Column 3 hai $(0,1,0{)}^{\top }$: $(\pi P{)}_3=b$.

Toh $\pi P=(c,a,b)$. Setting $=(a,b,c)$: $c=a,a=b,b=c\Rightarrow a=b=c.$ Normalise $a+b+c=1\Rightarrow 3a=1\Rightarrow \boxed{\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})}$. Symmetry se frog har pad par equal time spend karta hai.

(c) Aperiodic? Nahi. Frog forced hai $1\to 2\to 3\to 1\to \cdots$; woh kisi bhi pad par sirf $3$ steps ke multiples ke baad wapas aata hai. Period 3 hai jo $>1$ hai ⇒ periodic. Toh $\pi$ exist karti hai aur unique hai (chain irreducible hai), lekin ${\pi }^{(t)}$ converge hone ki jagah cycle karta hai.

(a) First-step analysis set up karo. Position $i$ se (interior, $0<i<N$) tum ek step lete ho (isliye ek $+1$ appear hota hai), phir $i-1$ ya $i+1$ par land karte ho har ek probability $\frac{1}{2}$ se, aur Markov property se process restart hoti hai jahan bhi tum land karo. Us first step par condition karte hue (law of total expectation, cousin of Law of Total Probability): $m_i=1+\frac{1}{2}{m}_{i-1}+\frac{1}{2}{m}_{i+1},m_0=0,m_N=0.$ (Woh $1$ = woh step jo tum ne abhi spend kiya; boundaries $0$ hain kyunki absorb hone ke baad, aur koi steps nahi chahiye.)

(b) Solve karo. Rearrange karo: $2m_i=2+m_{i-1}+m_{i+1}⟹m_{i+1}-m_i=(m_i-m_{i-1})-2.$ Toh gaps $d_i=m_{i+1}-m_i$ har step $2$ se decrease hote hain: $d_i=d_0-2i$ — ek arithmetic progression. $0$ se $i$ tak gaps sum karte hain: $m_i=m_0+{\sum }_{k=0}^{i-1}{d}_k=i{d}_0-2{\sum }_{k=0}^{i-1}k=i{d}_0-i(i-1).$ Yeh $i$ mein ek quadratic hai; ansatz try karo $m_i=Ai-i^2$ (ek downward parabola jo sensibly vanish hoti hai). $m_N=0$ impose karo: $AN-N^2=0\Rightarrow A=N.$ Phir $m_i=Ni-i^2=i(N-i)$. Check karo $m_0=0$ ✔, $m_N=N\cdot N-N^2=0$ ✔, aur yeh recurrence satisfy karta hai: $1+\frac{1}{2}(i-1)(N-i+1)+\frac{1}{2}(i+1)(N-i-1)=i(N-i)$ ✔. $\boxed{m_i=i(N-i)}$

(c) $i=3,N=10$ ke saath: $m_3=3(10-3)=3\times 7=\boxed{21}$ steps expected. Ek fair $3-vs-$10 game, on average, 21 rounds chalta hai — surprisingly long, kyunki walk linger karti hai kisi bhi barrier ke pakadne se pehle.

Parent note ke absorption probability $h_i=i/N=3/10$ se compare karo: "kaun sa end" ke liye ek linear answer, lekin "kitna time" ke liye ek quadratic answer. Same first-step trick, different inhomogeneous term (woh $+1$).

Web as a Markov chain. Har web page ko ek state maano. Ek "random surfer" ek page par us page ke outgoing links mein se ek uniformly at random click karta hai — yeh ek row-stochastic transition matrix $P$ define karta hai (har row = "is page se ek click kahan ja sakta hai"). Surfer memoryless hai: next click sirf current page par depend karta hai. Toh surfer ek giant graph par random walk hai.

PageRank = stationary distribution. Ek page ki importance = fraction of time jo random surfer us par spend karta hai long run mein = stationary vector $\pi$ ki entry jo $\pi =\pi P$ solve karta hai (eigenvalue $1$ ke liye left eigenvector, parent §2). "In equals There": ek page important hai agar usme bahut saari importance flow in hoti hai.

Woh ingredient jo Google add karta hai — teleportation (damping). Raw web-link $P$ reducible ho sakta hai (dead-end pages, disconnected clusters) aur periodic, toh Exercises 4.1–4.2 se ek unique, reachable $\pi$ guaranteed nahi hai. Google ek small probability (roughly $0.15$) mix karta hai uniformly random page par jump karne ki, link follow karne ki jagah: $G=0.85P+0.15\frac{1}{N}11^{\top }.$ Ab har page har doosre page tak ek step mein pahunch sakta hai (irreducible) aur koi forced cycles nahi hain (aperiodic). Perron–Frobenius Theorem se, $G$ ka ek unique stationary $\pi$ hai jis par power iteration ${\pi }^{(t+1)}={\pi }^{(t)}G$ converge hoti hai kisi bhi start se — exactly woh guarantee jo Exercises 4.1–4.2 ne dikhaya tha ki uske bina missing thi.