Rows encode one-step probabilities

Key idea

With the row-vector convention, a current distribution \(p_n\) updates by \(p_{n+1}=p_nP\). The entry \(P_{ij}\) is the chance to move from state \(i\) to state \(j\) in one step.

Matrix rules

• Every entry satisfies \(0\le P_{ij}\le1\).
• Each row sums to \(1\), because the next state must be somewhere.
• A deterministic move has one row entry equal to \(1\) and the others \(0\).
• An absorbing state \(i\) has \(P_{ii}=1\).
• If \(p_0\) is a distribution, then \(p_0P^n\) is the distribution after \(n\) steps.
• If all rows are identical, one step sends every starting distribution to that common row.

Chapman-Kolmogorov

Multi-step transitions compose: \[P^{m+n}=P^mP^n.\] Entrywise, this sums over all possible intermediate states.

Worked example

Try it

A stationary distribution is unchanged by one step

Key idea

A row distribution \(\pi\) is stationary when \(\pi P=\pi\). In linear algebra terms, \(\pi\) is a left eigenvector of \(P\) with eigenvalue \(1\), normalized so its entries are nonnegative and sum to \(1\).

Solving checklist

• Write \(\pi=(\pi_1,\dots,\pi_k)\).
• Solve \(\pi P=\pi\).
• Add the normalization \(\pi_1+\cdots+\pi_k=1\).
• Check entries are nonnegative.
• A finite doubly stochastic matrix preserves the uniform distribution.
• For \(P=I\), every probability distribution is stationary.
• In reducible chains, stationary distributions may be nonunique.

Two-state shortcut

For \(P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}\) with positive \(a+b\), the stationary distribution is proportional to \((b,a)\), so \(\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)\).

Worked example

Try it

Reachability controls the structure of the chain

Key idea

Say \(i\) reaches \(j\) if \((P^n)_{ij}>0\) for some \(n\ge0\). States communicate when each reaches the other. An irreducible finite chain has one communicating class.

Classification language

• Closed class: once entered, the chain cannot leave the class.
• Absorbing state: a one-state closed class, equivalently \(P_{ii}=1\).
• Recurrent state: returned to with probability \(1\).
• Transient state: visited only finitely many times with probability \(1\).
• Irreducible chain: every state communicates with every other state.

Finite-chain facts

In a finite irreducible chain, every state is recurrent. In a finite reducible chain, states outside closed classes are often transient because probability eventually moves into a closed class and stays there.

Worked example

Try it

Return-time arithmetic decides aperiodicity

Key idea

The period of a state \(i\) is the gcd of all positive \(n\) such that \((P^n)_{ii}>0\). A state with period \(1\) is aperiodic. In an irreducible chain, all states have the same period.

Convergence picture

• If a finite chain is irreducible and aperiodic, it has a unique stationary distribution \(\pi\).
• For such a chain, \(P^n\) converges to a matrix whose rows are all \(\pi\).
• If the chain is periodic, a stationary distribution can exist while \(P^n\) still oscillates.
• If the chain is reducible, limiting behavior depends on the closed classes that can be reached.

Self-loops

A self-loop \(P_{ii}>0\) gives a possible return in one step, so the gcd of return times includes \(1\). That forces period \(1\).

Worked example

Try it

Closed states turn probability questions into equations

Key idea

An absorbing state traps the chain after it is entered. More generally, a closed communicating class cannot be left. Hitting questions ask whether and when the process enters a chosen set.

Hitting equations

• For a hitting probability \(h_i\), use boundary values \(h_i=1\) on the target and \(h_i=0\) on impossible closed classes.
• For other states, use \(h_i=\sum_j P_{ij}h_j\).
• For an expected hitting time \(t_i\), use \(t_i=0\) on the target and \(t_i=1+\sum_jP_{ij}t_j\) elsewhere.
• Keep equations small by using symmetry or obvious absorbing states.

Closed classes

An absorbing class is a communicating class that cannot be left. A single absorbing state is the smallest example of this idea.

Worked example

Try it

Conditional expectation tracks fair drift

Key idea

A stochastic process is any indexed family of random variables. A filtration \((\mathcal F_n)\) records the information available by time \(n\). Martingale statements are conditional expectations relative to this information.

Conditional-expectation dictionary

• Martingale: \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
• Submartingale: \(E[X_{n+1}\mid\mathcal F_n]\ge X_n\), so the conditional drift is nonnegative.
• Supermartingale: \(E[X_{n+1}\mid\mathcal F_n]\le X_n\), so the conditional drift is nonpositive.
• These are statements about conditional averages, not about every sample path increasing or decreasing.

Stopping times

A stopping time \(\tau\) must be decidable from information available up to time \(n\) when checking whether \(\tau\le n\). For example, the first time a process hits \(5\) is a stopping time; the last time before tomorrow that it hits \(5\) depends on future information.

Worked example

Try it

Most mistakes mix conventions or ignore assumptions

Common traps

• Row versus column convention: this lesson uses row distributions \(pP\). With column distributions, formulas transpose.
• Invalid matrix rows: probabilities must be nonnegative and each row must sum to \(1\).
• Stationary is not absorbing: \(\pi P=\pi\) describes a distribution, not necessarily a fixed state.
• Reducible chains can have many stationary distributions: closed classes can each support stationary mass.
• Period can block convergence: the two-state switch has a stationary distribution but \(P^n\) oscillates.
• Self-loop shortcut: \(P_{ii}>0\) gives period \(1\) for that recurrent class.
• Transient is eventual: a transient state may be visited several times, but only finitely many times with probability \(1\).
• Stopping times use available information: they cannot depend on unseen future outcomes.
• Martingale means fair conditional mean: it does not mean the path stays constant.

Worked example

Try it

Final recap

• Markov property: the next-state law depends on the current state once the current state is known.
• A transition matrix has nonnegative entries and rows summing to \(1\).
• With row vectors, \(p_n=p_0P^n\).
• Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
• Stationary distributions solve \(\pi P=\pi\) and \(\sum_i\pi_i=1\).
• Identical rows send every current distribution to the common row; doubly stochastic finite chains preserve the uniform distribution; \(P=I\) preserves every distribution.
• An absorbing state has \(P_{ii}=1\); a closed class cannot be left.
• Irreducible means every state can reach every other state.
• Period is the gcd of possible return times; a self-loop gives period \(1\).
• Finite irreducible aperiodic chains converge to stationary rows.
• Martingales satisfy \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
• Stopping times are decided from past and present information, not unseen future data.