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

A quick vocabulary refresh so nothing below is a surprise:

State = one of the possible "places" the system can be in (a lily pad, a weather type, a position on a line).
Transition matrix $P$ = the table of jump probabilities; entry $P_{ij}$ is the chance of going from state $i$ to state $j$ in one step.
Distribution $π^{(t)}$ = a row vector listing, for the current moment, the probability of being in each state.
Stationary distribution $π$ = the special distribution that satisfies $π = π P$ : run one more step and nothing about the probabilities changes.

True or false — justify

The chain still jumps around forever once it reaches stationarity

True — stationarity freezes the distribution, not the wandering; individual trajectories keep hopping every step, the fractions of time on each state just stop changing.

Every transition matrix has

1

as an eigenvalue

True — the all-ones column vector

1

satisfies

P 1 = 1

because each row sums to

1

, so

1

is always a right eigenvalue (and hence a left one too).

A stochastic matrix can have eigenvalue

2

False — no eigenvalue can exceed

1

in magnitude for a row-stochastic matrix, since probabilities never amplify total mass; the spectral radius is exactly

1

π = π P

holds, then

π

is automatically a valid probability distribution

False — you also need

π_{i} \geq 0

and

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

; the equation alone is satisfied by scalar multiples and even sign-mixed left eigenvectors.

Every Markov chain converges to a unique stationary distribution

False — you need irreducibility (all states reachable) and aperiodicity; a periodic or reducible chain can fail to converge or have many stationary vectors.

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

False — the signed average position is exactly

0

for all

n

; what grows is the spread

n

, so it strays far but with no directional bias.

For the fair gambler's ruin on

{0, \dots, N}

, the probability of reaching

N

from state

i

i / N

True — first-step analysis gives

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

, whose only solution with

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

is the straight line

i / N

Multiplying

P π

(column style) gives the next distribution

False — because we summed the law of total probability over the current state (the row index), the update is

π P

with

π

a row vector;

P π

answers a different, wrong question.

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

True — under Perron–Frobenius the stationary

π

is unique and globally attracting, so the starting point is forgotten in the limit.

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

P_{ii} > 0

) can still be periodic

False — any self-loop lets you "stay put" for one step, breaking every forced cycle, so a self-loop guarantees aperiodicity at that state.

Spot the error

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

Wrong — the frog keeps hopping; only the fraction of time spent on each pad settles. Stationarity is a statement about the distribution, never about a frozen frog.

π = π P

π

is a right eigenvector of

P

with eigenvalue

1

Wrong direction —

π P = π

makes

π

a left eigenvector; the right eigenvector for eigenvalue

1

is the all-ones column

1

, a different object.

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

Wrong — the mean is

0

but the variance is

n

, so a typical walker is about

n

away; cancellation of the average is not the same as staying home.

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

Wrong — memoryless means independent of the past path given the present, not independent of the present; the next state depends entirely on the current state through

P

"To get

π^{(t)}

multiply

π^{(0)}

tP

Wrong — you multiply by

P

repeated $t$ times, i.e. the matrix power

P^{t}

, not by the scalar-times-matrix

tP

; repeated stepping is composition, not scaling.

"Rows of

P

sum to

1

, so columns must too."

Wrong — only rows are guaranteed to sum to

1

(row-stochastic); columns summing to

1

(doubly stochastic) is a special extra property, e.g. the uniform

π

then being stationary.

"Because variance adds, the walker's position after

n

steps grows linearly like

n

Wrong — variance grows like

n

, but distance is the standard deviation

Var = n

; confusing variance with spread inflates the growth rate.

Why questions

Why is memorylessness what makes a Markov chain computable at all

Because it collapses the entire unbounded history into a single current state, so the whole dynamics fit into one fixed matrix

P

instead of a rule that grows with time.

Why must every row of the transition matrix sum to exactly

1

From any state you must land somewhere next step, and the probabilities of all destinations exhaust certainty:

\sum_{j} P_{ij} = 1

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

The balance

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

says the total probability flowing into

j

from all states equals the probability already at

j

; that equality is exactly what makes the distribution stop changing.

Why do we use eigenvalues to find the steady state

Because

π = π P

literally is the eigenvector equation for eigenvalue

1

, so the tool that finds "vectors a matrix leaves unchanged" is precisely the tool that finds stationary distributions.

Why does the random-walk spread grow like

n

rather than

n

The steps have mean

0

so their sum has mean

0

, but independent variances add to

n

; spread is the square root of variance, giving

n

— the diffusion signature linked to the Central Limit Theorem.

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

Conditioning on the first coin flip and using memorylessness restarts an identical chain at

i \pm 1

, turning the problem into the recurrence

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

Why is the update

π P

and not

P π

We applied the Law of Total Probability summing over the current state

i

, which is the row index; summing a row vector against columns of

P

is exactly the left product

π P

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

The state space is infinite and the walk is not positive-recurrent; there is no way to assign nonnegative numbers summing to

1

that stay balanced, so probability "leaks to infinity."

Edge cases

If a chain is periodic with period

2

, does a stationary distribution exist

Yes,

π

can still solve

π = π P

, but

π^{(t)}

oscillates between two patterns and never converges to

π

— existence and convergence are separate guarantees.

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

0

or at

N

Those are absorbing boundary cases:

h_{0} = 0

and

h_{N} = 1

by definition, since you have already lost or already won before any step.

For a symmetric walk, what is

E [X_{0}]

and

Var (X_{0})

at zero steps

Both are

0

— with no steps taken the walker is deterministically at the origin, so there is no mean displacement and no spread yet.

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

Infinitely many — each sub-chain has its own stationary vector, and any weighted average of them is also stationary, destroying uniqueness.

What does the identity matrix

P = I

describe as a Markov chain

A chain where every state is absorbing (you never leave), so every probability distribution is stationary and nothing ever converges to a single one.

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

π

Yes — the stationary distribution lives entirely on the closed recurrent class and assigns probability

0

to the transient states, and it is unique despite the chain not being fully irreducible.

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

To force irreducibility and aperiodicity on a web graph full of dangling and disconnected pages, guaranteeing a unique, convergent stationary distribution — the 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)