Stochastic processes — Markov chains, steady-state, random walks: Question bank

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

Ek quick vocabulary refresh taaki neeche kuch bhi surprise na kare:

State = system jo possible "jagahon" mein se ek mein ho sakta hai (ek lily pad, ek weather type, ek line par position).
Transition matrix $P$ = jump probabilities ki table; entry $P_{ij}$ state $i$ se state $j$ mein ek step mein jaane ka chance hai.
Distribution $π^{(t)}$ = ek row vector jo current moment ke liye, har state mein hone ki probability list karta hai.
Stationary distribution $π$ = woh special distribution jo $π = π P$ satisfy karta hai: ek aur step chalao aur probabilities ke baare mein kuch nahi badalta.

True or false — justify karo

The chain still jumps around forever once it reaches stationarity

True — stationarity distribution ko freeze karta hai, wandering ko nahi; individual trajectories har step hop karte rehte hain, bas har state par time ka fraction badalna band ho jaata hai.

Every transition matrix has

1

as an eigenvalue

True — all-ones column vector

1

satisfy karta hai

P 1 = 1

kyunki har row sum hota hai

1

se, isliye

1

hamesha ek right eigenvalue hai (aur isliye left bhi).

A stochastic matrix can have eigenvalue

2

False — koi bhi eigenvalue magnitude mein

1

se zyada nahi ho sakta row-stochastic matrix ke liye, kyunki probabilities kabhi total mass ko amplify nahi karti; spectral radius exactly

1

hota hai.

π = π P

holds, then

π

is automatically a valid probability distribution

False — tumhe yeh bhi chahiye

π_{i} \geq 0

aur

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

; yeh equation akela scalar multiples aur sign-mixed left eigenvectors se bhi satisfy ho jaata hai.

Every Markov chain converges to a unique stationary distribution

False — tumhe irreducibility (saare states reachable) aur aperiodicity chahiye; ek periodic ya reducible chain converge karne mein fail ho sakti hai ya iske kai stationary vectors ho sakte hain.

A symmetric random walk on the integers drifts away from the origin on average

False — signed average position exactly

0

hoti hai sabhi

n

ke liye; jo badhta hai woh spread

n

hai, toh yeh door jaata hai lekin koi directional bias nahi.

For the fair gambler's ruin on

{0, \dots, N}

, the probability of reaching

N

from state

i

i / N

True — first-step analysis deta hai

h_{i} = \frac{1}{2} h_{i - 1} + \frac{1}{2} h_{i + 1}

, jiska

h_{0} = 0, h_{N} = 1

ke saath ek hi solution hai woh straight line

i / N

Multiplying

P π

(column style) gives the next distribution

False — kyunki humne law of total probability ko current state (row index) par sum kiya, update

π P

hai jahan

π

ek row vector hai;

P π

ek alag, galat sawaal ka jawab deta hai.

Two different starting distributions on an irreducible aperiodic chain end up at the same long-run distribution

True — Perron–Frobenius ke under stationary

π

unique aur globally attracting hota hai, toh starting point limit mein bhool jaata hai.

A chain with a self-loop at every state (each

P_{ii} > 0

) can still be periodic

False — koi bhi self-loop tumhe ek step ke liye "stay put" karne deta hai, har forced cycle ko tod ke, toh ek self-loop us state par aperiodicity guarantee karta hai.

Error dhundo

"Steady-state means the frog stops on one lily pad forever."

Galat — frog hopping karta rehta hai; sirf har pad par spent time ka fraction settle hota hai. Stationarity ek distribution ke baare mein statement hai, kabhi ek frozen frog ke baare mein nahi.

π = π P

π

is a right eigenvector of

P

with eigenvalue

1

Galat direction —

π P = π

π

ko ek left eigenvector banata hai; eigenvalue

1

ke liye right eigenvector all-ones column

1

hai, ek alag cheez.

"Since steps in a random walk cancel on average, the walker basically stays at the origin."

Galat — mean

0

hai lekin variance

n

hai, toh ek typical walker lagbhag

n

door hota hai; average ka cancellation ghar par rehne ke barabar nahi hai.

"The chain is memoryless, so its next state is independent of its current state."

Galat — memoryless ka matlab hai present diya hua past path se independent, current state se nahi; next state poori tarah current state par

P

ke through depend karta hai.

"To get

π^{(t)}

multiply

π^{(0)}

tP

Galat — tum

P

ko $t$ baar repeat karte ho, yaani matrix power

P^{t}

, scalar-times-matrix

tP

se nahi; repeated stepping composition hai, scaling nahi.

"Rows of

P

sum to

1

, so columns must too."

Galat — sirf rows guarantee hain ki

1

sum karti hain (row-stochastic); columns ka

1

sum karna (doubly stochastic) ek special extra property hai, jaise uniform

π

tab stationary hoti hai.

"Because variance adds, the walker's position after

n

steps grows linearly like

n

Galat — variance

n

ki tarah badhta hai, lekin distance standard deviation hai

Var = n

; variance ko spread se confuse karna growth rate ko inflate karta hai.

Why questions

Why is memorylessness what makes a Markov chain computable at all

Kyunki yeh poori unbounded history ko ek single current state mein collapse kar deta hai, toh poori dynamics ek fixed matrix

P

mein fit ho jaati hai ek aisi rule ki jagah jo time ke saath badhti hai.

Why must every row of the transition matrix sum to exactly

1

Kisi bhi state se tumhe kahin na kahin next step land karna hi hai, aur saare destinations ki probabilities certainty exhaust karti hain:

\sum_{j} P_{ij} = 1

Why does the stationary equation read "inflow = sitting there" for each state

Balance

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

kehta hai total probability jo saare states se

j

mein flow in karti hai woh probability ke barabar hai jo already $j$ par hai; wahi equality hai jo distribution ko badalna rokti hai.

Why do we use eigenvalues to find the steady state

Kyunki

π = π P

literally eigenvalue

1

ke liye eigenvector equation hai, toh woh tool jo "vectors jo ek matrix unchanged chhodti hai" dhundta hai exactly wahi tool hai jo stationary distributions dhundta hai.

Why does the random-walk spread grow like

n

rather than

n

Steps ka mean

0

hai toh unke sum ka mean

0

hai, lekin independent variances add hoti hain

n

tak; spread variance ka square root hai,

n

deta hai — diffusion signature Central Limit Theorem se linked.

Why does first-step analysis work for gambler's ruin

Pehle coin flip par condition karne se aur memorylessness use karne se ek identical chain

i \pm 1

par restart hoti hai, problem ko recurrence

h_{i} = \frac{1}{2} h_{i - 1} + \frac{1}{2} h_{i + 1}

mein badal deta hai.

Why is the update

π P

and not

P π

Humne Law of Total Probability apply kiya current state

i

par sum karte hue, jo row index hai; ek row vector ko

P

ke columns ke against sum karna exactly left product

π P

hai.

Why can a random walk on all integers have no stationary distribution

State space infinite hai aur walk positive-recurrent nahi hai; koi tarika nahi hai nonnegative numbers assign karne ka jo

1

sum karein aur balanced rahein, toh probability "infinity tak leak" ho jaati hai.

Edge cases

If a chain is periodic with period

2

, does a stationary distribution exist

Haan,

π

phir bhi

π = π P

solve kar sakta hai, lekin

π^{(t)}

do patterns ke beech oscillate karta hai aur kabhi

π

par converge nahi karta — existence aur convergence alag-alag guarantees hain.

What happens to gambler's ruin when the walk starts already at

0

or at

N

Woh absorbing boundary cases hain:

h_{0} = 0

aur

h_{N} = 1

definition se, kyunki tum already haar chuke ho ya pehle se hi jeet chuke ho kisi step se pehle.

For a symmetric walk, what is

E [X_{0}]

and

Var (X_{0})

at zero steps

Dono

0

hain — koi step nahi liye toh walker deterministically origin par hai, isliye koi mean displacement nahi aur koi spread nahi abhi tak.

If the chain is reducible into two isolated sub-chains, how many stationary distributions are there

Infinitely many — har sub-chain ka apna stationary vector hai, aur unka koi bhi weighted average bhi stationary hai, uniqueness ko khatam karta hai.

What does the identity matrix

P = I

describe as a Markov chain

Ek chain jahan har state absorbing hai (tum kabhi nahi jaate), toh har probability distribution stationary hai aur kuch bhi kabhi ek single par converge nahi karta.

Does a chain with a single closed communicating class but a transient state still have a unique

π

Haan — stationary distribution poori tarah closed recurrent class par rehti hai aur transient states ko probability

0

assign karti hai, aur yeh unique hai chain ke fully irreducible na hone ke bawajood.

In Google PageRank, why is a "damping"/teleport term added to the web transition matrix

Dangling aur disconnected pages se bhari web graph par irreducibility aur aperiodicity force karne ke liye, ek unique, convergent stationary distribution guarantee karta hai — PageRank vector.

Connections

Linear Algebra — Eigenvalues and Eigenvectors (why $π = π P$ is an eigen-problem)
Perron–Frobenius Theorem (uniqueness & convergence traps)
Law of Total Probability (why $π P$ , not $P π$ )
Central Limit Theorem (the $n$ spread)
Diffusion and Brownian Motion (variance-adds intuition)
Google PageRank (damping fixes the edge cases)