Chapter 3 · Markov Chains and Stochastic Processes

3.1 Markov Chains and Classification of States

Random processes with a one-step memory: transition matrices and the Chapman–Kolmogorov equations, communicating classes, recurrence and transience through $f_{ii}$ and $\sum_n p_{ii}^{(n)}$, periodicity, absorption probabilities and expected absorption times, and the random walk on $\mathbb{Z}$ that is recurrent exactly when it is fair.

Many random systems forget their history quickly. Tomorrow's weather depends mainly on today's, not on last week's. The number of customers in a queue after the next arrival or departure depends only on how many are there now. The credit rating of a bond next year, the allele count of a gene in the next generation, the position of a gambler's fortune after the next bet and the page a web surfer clicks next all follow the same pattern. Each is a sequence of random states in which the present carries all the information about the future that the past could give. Such a sequence is a Markov chain. Andrei Markov introduced it in 1906 to show that the law of large numbers does not need independence, and it has since become the most widely used model of random evolution, in queueing, genetics, finance, physics and computing (Google's PageRank and the Markov chain Monte Carlo methods of Bayesian statistics are both built on it).

This section sets up the theory for a finite or countable state space. A chain is described by its transition matrix $P$; the $n$-step probabilities are the entries of $P^n$ (the Chapman–Kolmogorov equations). States then split into communicating classes, and each class is either recurrent (the chain returns to it with probability one, infinitely often) or transient (it visits only finitely often). The test $\sum_n p_{ii}^{(n)}=\infty$ decides which, and it shows that the simple random walk on $\mathbb{Z}$ returns to its starting point with probability one exactly when it is fair. We also study the period of a state and compute absorption probabilities and expected absorption times, which include the gambler's ruin problem. In CSIR NET these ideas appear in almost every paper. Typical tasks are to classify the states of a given matrix, to find a period, to compute $p_{ij}^{(2)}$ or an absorption probability, or to judge statements about recurrence. Section 3.2 then studies what happens to $P^n$ as $n\to\infty$.

Markov Chains and Transition Matrices

Throughout, $S$ is a finite or countably infinite set, the state space, and $X_0,X_1,X_2,\dots$ are random variables on one probability space $(\Omega,\mathcal F,P)$ with values in $S$. Elements of $S$ are labelled $i,j,k,\dots$. A stochastic process is simply such a family $(X_n)_{n\ge0}$, indexed by time $n$.

📘 Definition 3.1 — Markov chain, transition matrix

A matrix $P=(p_{ij})_{i,j\in S}$ is stochastic if $p_{ij}\ge0$ for all $i,j$ and every row sums to one: $\sum_{j\in S}p_{ij}=1$. A probability vector $\lambda=(\lambda_i)_{i\in S}$ ($\lambda_i\ge0$, $\sum_i\lambda_i=1$) is written as a row vector.

The process $(X_n)_{n\ge0}$ is a (time-homogeneous) Markov chain with initial distribution $\lambda$ and transition matrix $P$, written Markov$(\lambda,P)$, if $P(X_0=i)=\lambda_i$ for all $i$ and, for every $n\ge0$ and all states $i_0,\dots,i_{n-1},i,j$ with $P(X_0=i_0,\dots,X_{n-1}=i_{n-1},X_n=i)\gt0$,

$$P(X_{n+1}=j\mid X_0=i_0,\dots,X_{n-1}=i_{n-1},X_n=i)=p_{ij}.$$

The left side therefore depends neither on the past states $i_0,\dots,i_{n-1}$ (the Markov property) nor on $n$ (time homogeneity). We write $P_i(\cdot)=P(\cdot\mid X_0=i)$ and $E_i$ for the corresponding expectation.

A transition matrix is conveniently drawn as a transition diagram: one node per state and an arrow $i\to j$ labelled $p_{ij}$ whenever $p_{ij}\gt0$. Every row of $P$ is a probability distribution (where the chain goes next from state $i$); columns have no such constraint.

📐 Theorem 3.1 — Path probabilities and the Markov property

(a) $(X_n)$ is Markov$(\lambda,P)$ if and only if, for every $n\ge0$ and all states $i_0,\dots,i_n$,

$$P(X_0=i_0,X_1=i_1,\dots,X_n=i_n)=\lambda_{i_0}\,p_{i_0i_1}\,p_{i_1i_2}\cdots p_{i_{n-1}i_n}.$$

(b) (Markov property) Let $(X_n)$ be Markov$(\lambda,P)$, $m\ge0$ and $i\in S$ with $P(X_m=i)\gt0$. Conditional on $X_m=i$, the process $(X_{m+n})_{n\ge0}$ is Markov$(\delta_i,P)$ (where $\delta_i$ puts mass one on $i$) and is independent of $X_0,\dots,X_m$: for every event $A$ determined by $(X_0,\dots,X_m)$ and every event $B$ determined by $(X_m,X_{m+1},\dots)$, $P(A\cap B\mid X_m=i)=P(A\mid X_m=i)\,P_i(B')$, where $B'$ is the same event written for the chain started afresh at time $0$.

Proof. (a) If $(X_n)$ is Markov$(\lambda,P)$, the multiplication rule of §1.2 gives $$P(X_0=i_0,\dots,X_n=i_n)=P(X_0=i_0)\prod_{k=1}^{n}P(X_k=i_k\mid X_0=i_0,\dots,X_{k-1}=i_{k-1}),$$ and each factor equals $p_{i_{k-1}i_k}$ by Definition 3.1. (If some prefix has probability $0$, both sides are $0$: the left because it is contained in a null event, the right because the first vanishing factor of the product already vanishes.) Conversely, if the product formula holds, then $P(X_0=i_0)=\lambda_{i_0}$ (take $n=0$), and dividing the formula for $n+1$ by the formula for $n$ gives $P(X_{n+1}=j\mid X_0=i_0,\dots,X_n=i)=p_{ij}$ whenever the condition has positive probability.

(b) Take first $A=\{X_0=i_0,\dots,X_m=i_m\}$ and $B=\{X_m=j_0,\dots,X_{m+n}=j_n\}$. Both events force $X_m=i$, so we may assume $i_m=j_0=i$. By (a), $$P(A\cap B)=\lambda_{i_0}p_{i_0i_1}\cdots p_{i_{m-1}i}\cdot p_{ij_1}p_{j_1j_2}\cdots p_{j_{n-1}j_n}=P(A)\,P_i(X_0=i,X_1=j_1,\dots,X_n=j_n).$$ Dividing by $P(X_m=i)$ gives the claim for these elementary events. A general event determined by $(X_0,\dots,X_m)$ is a countable disjoint union of events of the form $A$, and a general event determined by finitely many of $X_m,X_{m+1},\dots$ is a countable disjoint union of events of the form $B$; countable additivity extends the identity to them. Events depending on infinitely many coordinates are handled by the standard extension (π–λ) argument, which we do not repeat. ∎

Part (b) is the form in which the Markov property is used: "given the present, the future is a fresh copy of the chain started at the present state, independent of the past." Note that the conditioning must be on an exact present state $X_m=i$; conditioning on a set of present states such as $X_m\in\{1,2\}$ does not make the past irrelevant in general (see the ⚠️ box).

📘 Definition 3.2 — $n$-step transition probabilities
For $n\ge0$ the $n$-step transition probability from $i$ to $j$ is $p_{ij}^{(n)}=P(X_{m+n}=j\mid X_m=i)$, which by Theorem 3.1(b) equals $P_i(X_n=j)$ and does not depend on $m$. By convention $p_{ij}^{(0)}=\delta_{ij}$ ($1$ if $i=j$, $0$ otherwise), and $p_{ij}^{(1)}=p_{ij}$. We write $P^{(n)}=(p_{ij}^{(n)})$.
📐 Theorem 3.2 — Chapman–Kolmogorov equations
For all $m,n\ge0$ and $i,j\in S$, $$p_{ij}^{(m+n)}=\sum_{k\in S}p_{ik}^{(m)}\,p_{kj}^{(n)}.$$ Consequently $P^{(n)}=P^n$, the $n$-th matrix power of $P$, and if $(X_n)$ is Markov$(\lambda,P)$ then the distribution of $X_n$ is the row vector $\lambda P^n$: $P(X_n=j)=\sum_i\lambda_i\,p_{ij}^{(n)}$.

Proof. By the law of total probability over the value of $X_m$, and the Markov property at time $m$, $$p_{ij}^{(m+n)}=P_i(X_{m+n}=j)=\sum_{k}P_i(X_m=k)\,P_i(X_{m+n}=j\mid X_m=k)=\sum_kp_{ik}^{(m)}\,p_{kj}^{(n)},$$ where the terms with $P_i(X_m=k)=0$ are simply omitted. In matrix language $P^{(m+n)}=P^{(m)}P^{(n)}$, and induction from $P^{(1)}=P$ gives $P^{(n)}=P^n$. (For infinite $S$ the matrix product is a series of nonnegative terms, so it is always well defined, and $P^n$ is again stochastic.) Finally $P(X_n=j)=\sum_iP(X_0=i)P_i(X_n=j)=(\lambda P^n)_j$. ∎

Two inequalities that follow at once are used constantly in the classification of states: $p_{ij}^{(m+n)}\ge p_{ik}^{(m)}p_{kj}^{(n)}$ for every single $k$, and $p_{ii}^{(m+n+r)}\ge p_{ij}^{(m)}p_{jj}^{(r)}p_{ji}^{(n)}$.

✏️ Example 1 — A weather chain
Each day is sunny (S), cloudy (C) or rainy (R), and the next day's weather depends only on today's, with transition matrix (rows and columns in the order S, C, R) $$P=\begin{pmatrix}0.6&0.3&0.1\\0.3&0.4&0.3\\0.2&0.4&0.4\end{pmatrix}.$$ (a) Given a sunny Monday, find the probability that Wednesday is rainy. (b) Given a sunny Monday, find the probability that Tuesday is cloudy and both Wednesday and Thursday are rainy. (c) If Monday is sunny or cloudy with probability $\tfrac12$ each, find the distribution of Wednesday's weather.
Two steps Wednesday is two steps after Monday, so we need $p_{SR}^{(2)}=\sum_kp_{Sk}p_{kR}=0.6(0.1)+0.3(0.3)+0.1(0.4)=0.06+0.09+0.04=0.19$. The whole of $P^2$ is $$P^2=\begin{pmatrix}0.47&0.34&0.19\\0.36&0.37&0.27\\0.32&0.38&0.30\end{pmatrix}.$$
A path By Theorem 3.1(a) a path probability is a product along the path: $P_S(X_1=C,X_2=R,X_3=R)=p_{SC}\,p_{CR}\,p_{RR}=0.3\times0.3\times0.4=0.036$.
Distribution With $\lambda=(0.5,0.5,0)$, Wednesday's distribution is $\lambda P^2=\tfrac12(0.47+0.36,\ 0.34+0.37,\ 0.19+0.27)=(0.415,\ 0.355,\ 0.23)$.
Check Each row of $P^2$ and the vector $\lambda P^2$ sum to $1$, as they must. Iterating further, the rows of $P^n$ approach $(\tfrac{24}{61},\tfrac{22}{61},\tfrac{15}{61})\approx(0.393,0.361,0.246)$, the stationary distribution of §3.2.
📐 Theorem 3.3 — The two-state chain
Let $S=\{1,2\}$ and $P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}$ with $0\le a,b\le1$ and $a+b\gt0$. Put $\alpha=1-a-b$. Then for every $n\ge0$ $$P^n=\frac1{a+b}\begin{pmatrix}b&a\\b&a\end{pmatrix}+\frac{\alpha^n}{a+b}\begin{pmatrix}a&-a\\-b&b\end{pmatrix}.$$ In particular, if $|\alpha|\lt1$ (that is, unless $a=b=1$), every row of $P^n$ converges to $\left(\frac{b}{a+b},\frac{a}{a+b}\right)$, at the geometric rate $|\alpha|^n$.

Proof. Conditioning on the state at time $n$, and using $p_{12}^{(n)}=1-p_{11}^{(n)}$, $$p_{11}^{(n+1)}=p_{11}^{(n)}(1-a)+p_{12}^{(n)}b=b+\alpha\,p_{11}^{(n)}.$$ The constant $c=\frac{b}{a+b}$ solves $c=b+\alpha c$, so $p_{11}^{(n+1)}-c=\alpha\left(p_{11}^{(n)}-c\right)$, and since $p_{11}^{(0)}=1$, $p_{11}^{(n)}=c+\alpha^n(1-c)=\frac{b}{a+b}+\frac{a}{a+b}\alpha^n$. Then $p_{12}^{(n)}=1-p_{11}^{(n)}$, and the second row follows by exchanging the roles of the states ($a\leftrightarrow b$). Alternatively: $P$ has eigenvalues $1$ and $\alpha$ (trace $2-a-b$), and the two matrices in the formula are the spectral projections. ∎

✏️ Example 2 — A machine that breaks and is repaired
A machine is either working (state 1) or under repair (state 2) at the start of each day. A working machine breaks down during the day with probability $0.1$; a machine under repair is fixed during the day with probability $0.6$. It is working today. Find the probability that it is working in $5$ days' time, and the long-run probability that it is working.
Model A two-state chain with $a=0.1$, $b=0.6$, so $a+b=0.7$ and $\alpha=1-0.7=0.3$.
Formula By Theorem 3.3, $p_{11}^{(5)}=\frac{0.6}{0.7}+\frac{0.1}{0.7}(0.3)^5=\frac67+\frac17(0.00243)=0.857143+0.000347=0.85749$.
Long run $p_{11}^{(n)}\to\frac{b}{a+b}=\frac67\approx0.857$, whatever the initial state. The memory of the starting state decays like $0.3^n$: after five days it affects only the fourth decimal place.
Check Direct multiplication gives $P^5=\begin{pmatrix}0.85749&0.14251\\0.85506&0.14494\end{pmatrix}$, in agreement.

Many first questions about a process are of the form "is this a Markov chain?" The test is Definition 3.1: compute the conditional law of the next state given the whole past and see whether it depends only on the present state.

✏️ Example 3 — Markov or not?
(a) A fair die is rolled repeatedly and $M_n$ is the largest score in the first $n$ rolls. Show that $(M_n)_{n\ge1}$ is a Markov chain and find its transition matrix. (b) Let $(X_n)$ be the chain on $\{1,2,3\}$ that moves deterministically $1\to2\to3\to1$, started from the uniform distribution, and let $Y_n=a$ if $X_n\in\{1,2\}$, $Y_n=b$ if $X_n=3$. Show that $(Y_n)$ is not a Markov chain.
(a) Recursion Let $\xi_1,\xi_2,\dots$ be the iid scores. Then $M_{n+1}=\max(M_n,\xi_{n+1})$, and $\xi_{n+1}$ is independent of $(M_1,\dots,M_n)$, which are functions of $\xi_1,\dots,\xi_n$. Hence $P(M_{n+1}=j\mid M_1=i_1,\dots,M_n=i)=P(\max(i,\xi_{n+1})=j)$, which depends only on $i$ and $j$.
(a) Matrix $\max(i,\xi)=i$ iff $\xi\le i$, with probability $\frac i6$; and $\max(i,\xi)=j\gt i$ iff $\xi=j$, with probability $\frac16$. So $p_{ii}=\frac i6$, $p_{ij}=\frac16$ for $j\gt i$, and $p_{ij}=0$ for $j\lt i$: an upper triangular stochastic matrix with $p_{66}=1$. State $6$ is absorbing, as one expects.
(b) Two pasts If $Y_0=a$ and $Y_1=a$, then $X_0=1$, $X_1=2$, so $X_2=3$ and $Y_2=b$ with certainty: $P(Y_2=b\mid Y_1=a,Y_0=a)=1$. If $Y_0=b$ and $Y_1=a$, then $X_0=3$, $X_1=1$, $X_2=2$ and $Y_2=a$: $P(Y_2=b\mid Y_1=a,Y_0=b)=0$. The conditional law of $Y_2$ given $Y_1=a$ depends on $Y_0$, so $(Y_n)$ is not Markov.
Lesson A function of a Markov chain is usually not a Markov chain: lumping states together loses the information that the merged state was hiding. The merged process is Markov for every initial distribution exactly when $\sum_{j\in B}p_{ij}$ is the same for all $i$ in each block $A$, for every pair of blocks $A,B$ (Dynkin's lumpability criterion; Exercise I.8). Here the rows of states $1$ and $2$ give mass $0$ and $1$ to the block $\{3\}$.

The Markov property at a fixed time $m$ is not always enough. We often want to restart the chain at a random time, such as the first time it visits a state. This is legitimate exactly for random times that do not look into the future.

📘 Definition 3.3 — Stopping times and hitting times

A random variable $T$ with values in $\{0,1,2,\dots\}\cup\{\infty\}$ is a stopping time for $(X_n)$ if, for every $n$, the event $\{T=n\}$ is determined by $X_0,\dots,X_n$. For $A\subseteq S$ the hitting time $H^A=\inf\{n\ge0:X_n\in A\}$ and, for a state $j$, the first passage time $T_j=\inf\{n\ge1:X_n=j\}$ are stopping times (with $\inf\varnothing=\infty$).

The last time the chain visits $j$ before time $100$ is not a stopping time: to know that a visit at time $n$ is the last one we must look at $X_{n+1},\dots,X_{100}$.

📐 Theorem 3.4 — Strong Markov property
Let $(X_n)$ be Markov$(\lambda,P)$ and $T$ a stopping time. Conditional on $T\lt\infty$ and $X_T=i$, the process $(X_{T+n})_{n\ge0}$ is Markov$(\delta_i,P)$ and is independent of $X_0,X_1,\dots,X_T$.

Proof. Let $B$ be an event determined by $X_0,\dots,X_T$, which means that $B\cap\{T=m\}$ is determined by $X_0,\dots,X_m$ for each $m$. For states $j_1,\dots,j_n$, split according to the value of $T$ and apply the ordinary Markov property (Theorem 3.1(b)) at each fixed time $m$: $$P\left(\{X_T=i,X_{T+1}=j_1,\dots,X_{T+n}=j_n\}\cap B\cap\{T\lt\infty\}\right)=\sum_{m=0}^{\infty}P\left(\{X_m=i,X_{m+1}=j_1,\dots,X_{m+n}=j_n\}\cap B\cap\{T=m\}\right)$$ $$=\sum_{m=0}^{\infty}P_i(X_1=j_1,\dots,X_n=j_n)\,P\left(B\cap\{T=m\}\cap\{X_m=i\}\right)=P_i(X_1=j_1,\dots,X_n=j_n)\,P\left(B\cap\{T\lt\infty,\ X_T=i\}\right).$$ Dividing by $P(T\lt\infty,X_T=i)$ gives exactly the claimed conditional independence and the Markov$(\delta_i,P)$ path probabilities. ∎

Communicating Classes and Closed Sets

The transition diagram tells us which states can be reached from which, and this coarse information, ignoring the actual values of the probabilities, already determines a great deal of the long-run behaviour.

📘 Definition 3.4 — Accessibility, communication, classes
  • State $j$ is accessible from $i$, written $i\to j$, if $p_{ij}^{(n)}\gt0$ for some $n\ge0$; equivalently, there is a chain of states $i=i_0,i_1,\dots,i_n=j$ with $p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{n-1}i_n}\gt0$ (a path of arrows in the diagram).
  • States $i$ and $j$ communicate, $i\leftrightarrow j$, if $i\to j$ and $j\to i$. The equivalence classes of $\leftrightarrow$ (Theorem 3.5) are the communicating classes.
  • A set $C\subseteq S$ is closed if $p_{ij}=0$ whenever $i\in C$ and $j\notin C$: once in $C$, the chain never leaves. A state $i$ with $p_{ii}=1$ (so that $\{i\}$ is closed) is absorbing.
  • The chain (or $P$) is irreducible if $S$ is a single communicating class, that is, $i\leftrightarrow j$ for all $i,j$.
📐 Theorem 3.5 — Communicating classes partition $S$
(a) $\leftrightarrow$ is an equivalence relation on $S$, so the communicating classes partition $S$. (b) A communicating class $C$ is closed if and only if no state outside $C$ is accessible from a state of $C$. (c) If $S$ is finite, there is at least one closed communicating class, and from every state some closed class is accessible.

Proof. (a) $i\leftrightarrow i$ because $p_{ii}^{(0)}=1$, and symmetry is built into the definition. If $i\to j$ and $j\to k$, choose $m,n$ with $p_{ij}^{(m)}\gt0$ and $p_{jk}^{(n)}\gt0$; Chapman–Kolmogorov gives $p_{ik}^{(m+n)}\ge p_{ij}^{(m)}p_{jk}^{(n)}\gt0$, so $i\to k$. Applying this in both directions gives transitivity of $\leftrightarrow$. Equivalence classes of an equivalence relation partition the set.

(b) If $C$ is closed, the chain started in $C$ stays in $C$ for ever, so $p_{ij}^{(n)}=0$ for $i\in C$, $j\notin C$ and all $n$. Conversely, if $C$ is not closed there are $i\in C$ and $j\notin C$ with $p_{ij}\gt0$, so $i\to j$.

(c) Write $C\preceq D$ for classes if some (hence every) state of $D$ is accessible from some (hence every) state of $C$. This relation is reflexive and transitive, and it is antisymmetric: $C\preceq D\preceq C$ means that the states of $C$ and $D$ communicate, so $C=D$. Start from any class $C_0$. If $C_0$ is not closed, (b) gives a class $C_1\ne C_0$ with $C_0\preceq C_1$; if $C_1$ is not closed, continue. By antisymmetry and transitivity, the classes $C_0,C_1,C_2,\dots$ are all different, and there are only finitely many classes, so the procedure stops at a closed class accessible from $C_0$. ∎

Part (c) fails for infinite $S$: the chain on $\mathbb{Z}$ that moves deterministically $i\mapsto i+1$ has every singleton as a class and no closed class at all. Note also that a closed set need not be a class; $S$ itself is always closed, and so is any union of closed classes.

Recurrence and Transience

The central question about a state is whether the chain, started there, is sure to come back. If it is, the strong Markov property restarts the chain at the return, so it comes back again and again, infinitely often. If it is not, each return has a fixed chance of being the last, and the number of visits is finite.

📘 Definition 3.5 — First passage probabilities; recurrent and transient states

For states $i,j$ and $n\ge1$ let $f_{ij}^{(n)}=P_i(T_j=n)=P_i(X_n=j,\ X_k\ne j\text{ for }1\le k\lt n)$ be the probability that the first visit to $j$ after time $0$ happens at time $n$, and

$$f_{ij}=P_i(T_j\lt\infty)=\sum_{n=1}^{\infty}f_{ij}^{(n)}.$$

State $i$ is recurrent (persistent) if $f_{ii}=1$ and transient if $f_{ii}\lt1$. We also write $N_j=\sum_{n\ge1}\mathbf 1\{X_n=j\}$ for the number of visits to $j$ at times $n\ge1$.

📐 Theorem 3.6 — The recurrence criterion

For all states $i,j$ and $k\ge1$: $P_i(N_j\ge k)=f_{ij}\,f_{jj}^{\,k-1}$, and $E_i(N_j)=\sum_{n=1}^{\infty}p_{ij}^{(n)}$. Consequently:

  1. If $i$ is recurrent, then $P_i(N_i=\infty)=1$ and $\displaystyle\sum_{n=1}^{\infty}p_{ii}^{(n)}=\infty$.
  2. If $i$ is transient, then $P_i(N_i\ge k)=f_{ii}^{\,k}$, so $N_i$ is geometric and finite almost surely, and $\displaystyle\sum_{n=1}^{\infty}p_{ii}^{(n)}=E_i(N_i)=\frac{f_{ii}}{1-f_{ii}}\lt\infty$.

Hence $i$ is recurrent if and only if $\sum_np_{ii}^{(n)}=\infty$; and if $j$ is transient, $\sum_np_{ij}^{(n)}=\frac{f_{ij}}{1-f_{jj}}\lt\infty$ for every $i$, so $p_{ij}^{(n)}\to0$.

Proof. Let $T^{(1)}=T_j$ and, inductively, $T^{(k+1)}=\inf\{n\gt T^{(k)}:X_n=j\}$ be the successive visit times to $j$; each is a stopping time, and $\{N_j\ge k\}=\{T^{(k)}\lt\infty\}$. For $k=1$, $P_i(N_j\ge1)=P_i(T_j\lt\infty)=f_{ij}$. Given $T^{(k)}\lt\infty$, we have $X_{T^{(k)}}=j$, and by the strong Markov property (Theorem 3.4) the chain after $T^{(k)}$ is a fresh chain started at $j$; it makes a further visit with probability $f_{jj}$. Hence $$P_i(N_j\ge k+1)=P_i(T^{(k)}\lt\infty)\,f_{jj}=P_i(N_j\ge k)\,f_{jj},$$ and induction gives $P_i(N_j\ge k)=f_{ij}f_{jj}^{\,k-1}$. Next, since all terms are nonnegative we may exchange expectation and sum (Tonelli): $$E_i(N_j)=E_i\sum_{n\ge1}\mathbf 1\{X_n=j\}=\sum_{n\ge1}P_i(X_n=j)=\sum_{n\ge1}p_{ij}^{(n)}.$$ Now take $j=i$. If $f_{ii}=1$, $P_i(N_i\ge k)=1$ for all $k$, so $P_i(N_i=\infty)=\lim_kP_i(N_i\ge k)=1$ (continuity of probability) and $E_i(N_i)=\infty$. If $f_{ii}\lt1$, $P_i(N_i=\infty)=\lim_kf_{ii}^{\,k}=0$ and $E_i(N_i)=\sum_{k\ge1}P_i(N_i\ge k)=\sum_{k\ge1}f_{ii}^{\,k}=\frac{f_{ii}}{1-f_{ii}}$. For transient $j$ and any $i$, $E_i(N_j)=\sum_{k\ge1}f_{ij}f_{jj}^{\,k-1}=\frac{f_{ij}}{1-f_{jj}}\lt\infty$, and the terms of a convergent series tend to $0$. ∎

So a recurrent state is visited infinitely often, and a transient one finitely often, with probability one: there is no third possibility. The theorem also gives a second way to find $f_{ii}$ when the $p_{ii}^{(n)}$ are known: $f_{ii}=G/(1+G)$ with $G=\sum_{n\ge1}p_{ii}^{(n)}$. The link between the sequences $(p^{(n)})$ and $(f^{(n)})$ is made precise by generating functions.

📐 Theorem 3.7 — First-passage decomposition
For $n\ge1$ and all states $i,j$, $$p_{ij}^{(n)}=\sum_{k=1}^{n}f_{ij}^{(k)}\,p_{jj}^{(n-k)}.$$ Hence, with $P_{ij}(s)=\sum_{n\ge0}p_{ij}^{(n)}s^n$ and $F_{ij}(s)=\sum_{n\ge1}f_{ij}^{(n)}s^n$ for $0\le s\lt1$, $$P_{ii}(s)=\frac{1}{1-F_{ii}(s)},\qquad P_{ij}(s)=F_{ij}(s)\,P_{jj}(s)\quad(i\ne j).$$

Proof. The event $\{X_n=j\}$ is the disjoint union over $k=1,\dots,n$ of the events $\{T_j=k,\ X_n=j\}$. By the strong Markov property at $T_j$, $$P_i(T_j=k,X_n=j)=P_i(T_j=k)\,P_j(X_{n-k}=j)=f_{ij}^{(k)}p_{jj}^{(n-k)}.$$ Multiply the decomposition by $s^n$ and sum over $n\ge1$: the right side is a Cauchy product, so $P_{ij}(s)-\delta_{ij}=F_{ij}(s)P_{jj}(s)$. For $i=j$ this reads $P_{ii}(s)-1=F_{ii}(s)P_{ii}(s)$; since $F_{ii}(s)\le s\lt1$ we can solve for $P_{ii}(s)$. ∎

Letting $s\uparrow1$ (Abel's theorem for series of nonnegative terms) gives $\sum_np_{ii}^{(n)}=1/(1-f_{ii})$, with the convention $1/0=\infty$: a second proof of Theorem 3.6. The generating-function form is the efficient tool for random walks (Theorem 3.10).

📐 Theorem 3.8 — Recurrence is a class property
  1. If $i\leftrightarrow j$, then $i$ is recurrent if and only if $j$ is recurrent. So in each communicating class either every state is recurrent or every state is transient, and we call the class recurrent or transient.
  2. If $i$ is recurrent and $i\to j$, then $j\to i$ and $f_{ji}=f_{ij}=1$. In particular every recurrent class is closed, and a class that is not closed is transient.

Proof. (1) Choose $m,n$ with $p_{ij}^{(m)}\gt0$ and $p_{ji}^{(n)}\gt0$. For every $r\ge0$, $p_{jj}^{(n+r+m)}\ge p_{ji}^{(n)}\,p_{ii}^{(r)}\,p_{ij}^{(m)}$, so $$\sum_{r\ge0}p_{jj}^{(n+r+m)}\ \ge\ p_{ji}^{(n)}p_{ij}^{(m)}\sum_{r\ge0}p_{ii}^{(r)}.$$ If $i$ is recurrent the right side is infinite (Theorem 3.6), hence so is the left, and $j$ is recurrent. Exchange $i$ and $j$ for the converse.

(2) Choose $m$ with $p_{ij}^{(m)}\gt0$. On the event $\{X_m=j\}\cap\{X_n\ne i\text{ for all }n\gt m\}$ the chain visits $i$ at most $m$ times, so this event lies inside $\{N_i\lt\infty\}$, which has $P_i$-probability $0$ by Theorem 3.6. By the Markov property at time $m$ the event has probability $p_{ij}^{(m)}(1-f_{ji})$. Hence $f_{ji}=1$; in particular $j\to i$, so $j$ lies in the class of $i$. Since $i\to j$ was arbitrary, nothing outside the class is accessible from it, and by Theorem 3.5(b) the class is closed. Finally $j$ is recurrent by (1), and the same argument with the roles of $i$ and $j$ exchanged gives $f_{ij}=1$. ∎

📐 Theorem 3.9 — Finite chains
Let $S$ be finite. Then (a) not all states are transient; (b) every closed class is recurrent; (c) a class is transient if and only if it is not closed; (d) every irreducible chain on a finite state space is recurrent, and for every transient state $j$ and every $i$, $p_{ij}^{(n)}\to0$ geometrically fast.

Proof. (b) Let $C$ be a closed class and suppose its states are transient. For $i\in C$ and every $n$, $\sum_{j\in C}p_{ij}^{(n)}=1$ because the chain cannot leave $C$. Each term tends to $0$ by Theorem 3.6 and the sum is finite, so the left side tends to $0$: a contradiction. (a) follows from (b) and Theorem 3.5(c), which provides a closed class. (c) combines (b) with Theorem 3.8(2). (d) The first claim is (b) with $C=S$. For the rate, let $T$ be the set of transient states. From each $i\in T$ some closed class is accessible (Theorem 3.5(c)) within $|S|$ steps, so $\varepsilon=\min_{i\in T}P_i(\text{leave }T\text{ within }|S|\text{ steps})\gt0$, and by the Markov property applied every $|S|$ steps, $P_i(X_n\in T)\le(1-\varepsilon)^{\lfloor n/|S|\rfloor}$. ∎

For finite chains, therefore, recurrence and transience are read off the transition diagram: closed classes are recurrent, all other classes are transient. For infinite chains this is false. A closed class, even the whole of an irreducible chain, can be transient, and deciding recurrence then needs the criterion $\sum_np_{ii}^{(n)}=\infty$. The basic example is the random walk.

📐 Theorem 3.10 — Recurrence of the simple random walk

Let $X_n=X_0+\xi_1+\cdots+\xi_n$ on $S=\mathbb{Z}$, where the steps $\xi_k$ are iid with $P(\xi_k=1)=p$, $P(\xi_k=-1)=q=1-p$, $0\lt p\lt1$. The chain is irreducible with period $2$, and

$$p_{00}^{(2n)}=\binom{2n}{n}(pq)^n,\qquad F_{00}(s)=1-\sqrt{1-4pq\,s^2},\qquad f_{00}=1-|p-q|.$$

Hence the walk is recurrent if and only if $p=q=\tfrac12$; for $p\ne\tfrac12$ the expected number of returns to $0$ is $\sum_{n\ge1}p_{00}^{(n)}=\frac{1}{|p-q|}-1$.

(Pólya) The symmetric nearest-neighbour random walk on $\mathbb{Z}^d$ (each of the $2d$ neighbours with probability $\frac1{2d}$) is recurrent for $d=1,2$ and transient for $d\ge3$.

Proof. From any $i$ the walk reaches $j$ in $|j-i|$ steps with positive probability, so it is irreducible. A return to $0$ needs as many up-steps as down-steps, hence an even number of steps; and $2$ steps suffice, so the period is $2$. In $2n$ steps the walk is back at $0$ iff exactly $n$ steps are up, which gives $p_{00}^{(2n)}=\binom{2n}{n}p^nq^n$.

The binomial series gives $\sum_{n\ge0}\binom{2n}{n}x^n=(1-4x)^{-1/2}$ for $|x|\lt\frac14$ (expand $(1-4x)^{-1/2}$ and use $\binom{-1/2}{n}(-4)^n=\binom{2n}{n}$). With $x=pqs^2\le\frac{s^2}4\lt\frac14$ for $0\le s\lt1$, $$P_{00}(s)=\sum_{n\ge0}\binom{2n}{n}(pqs^2)^n=\frac{1}{\sqrt{1-4pqs^2}},\qquad F_{00}(s)=1-\frac1{P_{00}(s)}=1-\sqrt{1-4pqs^2}$$ by Theorem 3.7. Letting $s\uparrow1$, $f_{00}=1-\sqrt{1-4pq}$. Now $1-4pq=(p+q)^2-4pq=(p-q)^2$, so $f_{00}=1-|p-q|$, which equals $1$ iff $p=q$. For $p\ne q$, Theorem 3.6 gives $\sum_{n\ge1}p_{00}^{(n)}=\frac{f_{00}}{1-f_{00}}=\frac{1-|p-q|}{|p-q|}$.

For Pólya's theorem with $d=2$: write the walk as $(X_n,Y_n)$ and put $U_n=X_n+Y_n$, $V_n=X_n-Y_n$. Each step changes $(U,V)$ by one of $(\pm1,\pm1)$, each of the four with probability $\frac14$, so $U$ and $V$ are independent symmetric simple random walks on $\mathbb{Z}$, and the walk is at the origin iff $U_n=V_n=0$. Hence $p_{00}^{(2n)}=\left[\binom{2n}{n}4^{-n}\right]^2\sim\frac{1}{\pi n}$ by Stirling's formula $\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi n}}$, and $\sum\frac1n=\infty$. For $d=3$ one shows $p_{00}^{(2n)}\le Cn^{-3/2}$ by a multinomial estimate; the series converges and the walk is transient. ∎

Stirling's formula also gives the recurrence criterion directly for $d=1$: $p_{00}^{(2n)}\sim\frac{(4pq)^n}{\sqrt{\pi n}}$, and $4pq\lt1$ unless $p=\frac12$, so the series converges by comparison with a geometric series exactly when $p\ne\frac12$. Note one more consequence of the formula for $F_{00}$: in the symmetric case $F_{00}'(s)=\frac{s}{\sqrt{1-s^2}}\to\infty$ as $s\uparrow1$, so the expected return time $E_0(T_0)=\sum_nnf_{00}^{(n)}$ is infinite although the return is certain. This is null recurrence, studied in §3.2.

Interactive 1 — Does the Random Walk Come Home? Recurrence versus Transience on $\mathbb{Z}$

Twelve independent walks start at $0$ and step $+1$ with probability $p$ (a seeded generator). The top panel shows their paths; a dot marks every return to $0$. The bottom panel plots the exact expected number of returns by time $n$, $G_n=\sum_{k\le n}p_{00}^{(k)}$ (blue), against its limit $\frac{1}{|p-q|}-1$ (green dashed). For $p=\frac12$ the curve grows like $\sqrt{2n/\pi}$ without bound and every walk keeps returning (recurrence); for $p\ne\frac12$ it levels off, the walks drift away and their returns stop (transience). Move $p$ slowly towards $\frac12$ and watch the limit blow up.

0.50
time n—
G_n (exact)—
f₀₀ = 1 − |p − q|—
returns seen (12 walks)—
walks still returning after n/2—
✏️ Example 4 — Random walks: prove or disprove
Prove or disprove: (a) the walk on $\mathbb{Z}$ with $P(\xi=1)=0.6$, $P(\xi=-1)=0.4$ returns to $0$ with probability $0.8$, and the expected number of returns is $4$; (b) the "lazy" walk on $\mathbb{Z}$ with $P(\xi=1)=p$, $P(\xi=-1)=q$, $P(\xi=0)=r$ ($p,q\gt0$, $p+q+r=1$) is recurrent if and only if $p=q$; (c) every irreducible Markov chain on an infinite state space is transient; (d) for the walk of (a), the probability of ever visiting $-1$ from $0$ is $\frac23$.
(a) True By Theorem 3.10, $f_{00}=1-|0.6-0.4|=0.8$, and the expected number of returns is $\frac{f_{00}}{1-f_{00}}=\frac{0.8}{0.2}=4$. Check: $\frac1{|p-q|}-1=\frac1{0.2}-1=4$.
(b) True If $r=1-p-q\gt0$, watch the walk only at the times it actually moves. Each move is up with probability $\frac{p}{p+q}$, and the moves form a simple random walk, recurrent iff $\frac p{p+q}=\frac12$, i.e. $p=q$. The pauses do not change the number of visits to $0$ from finite to infinite or back (each visit lasts a geometric, hence finite, number of steps). Alternatively, $\sum_np_{00}^{(n)}$ can be computed directly; it diverges iff $p=q$.
(c) False The symmetric simple random walk on $\mathbb{Z}$ is irreducible, infinite and recurrent (Theorem 3.10); so is the symmetric walk on $\mathbb{Z}^2$. Infinite irreducible chains can be recurrent or transient; only for finite chains is recurrence automatic (Theorem 3.9).
(d) True Let $h=P_0(\text{ever visit }-1)$. To go from $0$ to $-2$ the walk must first reach $-1$ and then, starting afresh (strong Markov property), go one further step down; so $P_0(\text{ever visit }-2)=h^2$. Conditioning on the first step: $h=q+p\,h^2$, i.e. $0.6h^2-h+0.4=0$, with roots $h=1$ and $h=\frac{q}{p}=\frac23$. The walk drifts to $+\infty$ (strong law), so $h\lt1$ and $h=\frac23$ (rigorously: $h$ is the minimal nonnegative root, Theorem 3.13 below). Consistency check: $f_{00}=p\,P_1(\text{hit }0)+q\,P_{-1}(\text{hit }0)=0.6\cdot\frac23+0.4\cdot1=0.8$, as in (a).

Periodicity

A chain that alternates between two sets of states, such as the random walk on $\mathbb{Z}$, which moves between even and odd integers, can return to its starting point only at even times. Periodicity measures this rigidity. It will be the reason why $P^n$ may fail to converge in §3.2.

📘 Definition 3.6 — Period
The period of a state $i$ with $i\to i$ in at least one step is $$d(i)=\gcd\{n\ge1:\ p_{ii}^{(n)}\gt0\}.$$ State $i$ is aperiodic if $d(i)=1$ and periodic with period $d(i)$ if $d(i)\ge2$. (If $p_{ii}^{(n)}=0$ for all $n\ge1$, the period is left undefined; some texts put $d(i)=0$ or $\infty$.)

The period is a greatest common divisor, not a minimum. If the possible return times are $4,6,8,10,\dots$ then $d(i)=2$ although no return is possible in two steps, and a state with return times $3,4,6,7,\dots$ is aperiodic although it has no self-loop. A self-loop is a sufficient but not a necessary condition: $p_{ii}\gt0$ makes $1$ a return time, so $d(i)=1$.

📐 Theorem 3.11 — Period is a class property
If $i\leftrightarrow j$ then $d(i)=d(j)$. In particular all states of an irreducible chain have the same period, called the period of the chain.

Proof. Choose $m,n$ with $p_{ij}^{(m)}\gt0$ and $p_{ji}^{(n)}\gt0$. Then $p_{ii}^{(m+n)}\ge p_{ij}^{(m)}p_{ji}^{(n)}\gt0$, so $d(i)$ divides $m+n$. If $r$ is any time with $p_{jj}^{(r)}\gt0$, then $p_{ii}^{(m+r+n)}\ge p_{ij}^{(m)}p_{jj}^{(r)}p_{ji}^{(n)}\gt0$, so $d(i)$ divides $m+r+n$ and therefore divides $r$. Thus $d(i)$ is a common divisor of all return times of $j$, and $d(i)\mid d(j)$. By symmetry $d(j)\mid d(i)$, so they are equal. ∎

📐 Theorem 3.12 — Return times of an aperiodic state; cyclic classes
(a) (Number-theoretic lemma) If a set $A$ of positive integers is closed under addition and $\gcd A=1$, then $A$ contains every sufficiently large integer.
(b) If $d(i)=d$, there is $n_0$ such that $p_{ii}^{(nd)}\gt0$ for all $n\ge n_0$. If the chain is irreducible and aperiodic, then for all $i,j$ there is $n_0(i,j)$ with $p_{ij}^{(n)}\gt0$ for all $n\ge n_0(i,j)$; if moreover $S$ is finite, some power $P^m$ has all entries strictly positive.
(c) If the chain is irreducible with period $d\ge2$, then $S$ splits into $d$ disjoint cyclic classes $C_0,C_1,\dots,C_{d-1}$ such that $p_{ij}\gt0$ only if $i\in C_r$ and $j\in C_{r+1}$ (indices mod $d$). The chain cycles through $C_0\to C_1\to\cdots\to C_{d-1}\to C_0$.

Proof. (a) The gcd of $A$ is already the gcd of some finite subset $\{a_1,\dots,a_k\}$ (the gcds of the first $k$ elements form a non-increasing sequence of positive integers, which is eventually constant and equal to $\gcd A$). By Bézout, $1=\sum_rc_ra_r$ with integers $c_r$. Collect the terms with $c_r\gt0$ into $x$ and those with $c_r\lt0$ into $y$, so that $1=x-y$ with $x\in A$ and $y\in A\cup\{0\}$ (closure under addition). If $y=0$ then $1\in A$ and $A=\mathbb{N}$. Otherwise let $n\ge y^2$ and write $n=uy+v$ with $0\le v\lt y\le u$. Then $n=uy+v(x-y)=(u-v)y+vx$ with $u-v\ge1$, so $n\in A$.

(b) The set $A=\{n\ge1:p_{ii}^{(n)}\gt0\}$ is closed under addition by Chapman–Kolmogorov ($p_{ii}^{(m+n)}\ge p_{ii}^{(m)}p_{ii}^{(n)}$). Apply (a) to $\{n/d:n\in A\}$, whose gcd is $1$. In the irreducible aperiodic case, choose $m$ with $p_{ij}^{(m)}\gt0$; then $p_{ij}^{(n+m)}\ge p_{ii}^{(n)}p_{ij}^{(m)}\gt0$ for all large $n$. For finite $S$ take $m=\max_{i,j}n_0(i,j)$.

(c) Fix $i_0$. For each $j$ choose $a,b$ with $p_{i_0j}^{(a)}\gt0$ and $p_{ji_0}^{(b)}\gt0$. If also $p_{i_0j}^{(a')}\gt0$, then $d$ divides both $a+b$ and $a'+b$, so $a\equiv a'\pmod d$. Hence the residue $r(j)=a\bmod d$ is well defined, and $C_r=\{j:r(j)=r\}$. If $p_{jk}\gt0$ then $p_{i_0k}^{(a+1)}\gt0$, so $r(k)=r(j)+1$. Each $C_r$ is nonempty, since the path from $i_0$ back to $i_0$ passes through all residues. ∎

✏️ Example 5 — Classify every state
Classify the states of the chain on $\{1,\dots,6\}$ with transition matrix $$P=\begin{pmatrix}\tfrac12&\tfrac12&0&0&0&0\\[2pt]\tfrac14&0&\tfrac14&0&\tfrac12&0\\[2pt]0&0&0&1&0&0\\[2pt]0&0&1&0&0&0\\[2pt]0&0&0&0&\tfrac13&\tfrac23\\[2pt]0&0&0&0&\tfrac12&\tfrac12\end{pmatrix}:$$ find the communicating classes, say which are closed, which states are recurrent and which transient, and find the period of each class.
Arrows The positive entries give the arrows $1\to1$, $1\to2$, $2\to1$, $2\to3$, $2\to5$, $3\to4$, $4\to3$, $5\to5$, $5\to6$, $6\to5$, $6\to6$.
Classes $1\leftrightarrow2$; $3\leftrightarrow4$; $5\leftrightarrow6$. From $3,4$ the chain cannot reach $1,2,5,6$, and from $5,6$ it cannot reach $1,\dots,4$. So the classes are $\{1,2\}$, $\{3,4\}$, $\{5,6\}$. The class $\{1,2\}$ is not closed ($p_{23},p_{25}\gt0$); $\{3,4\}$ and $\{5,6\}$ are closed.
Recurrence The state space is finite, so by Theorem 3.9 the closed classes $\{3,4\}$ and $\{5,6\}$ are recurrent and $\{1,2\}$ is transient. (Directly: from $2$ the chain leaves $\{1,2\}$ for ever with probability $\frac34$ at the next step, so $f_{22}\lt1$.)
Periods $\{1,2\}$: $p_{11}\gt0$, so period $1$. $\{3,4\}$: the chain alternates $3,4,3,4,\dots$, so the return times of $3$ are $2,4,6,\dots$ and the period is $2$. $\{5,6\}$: $p_{55}\gt0$, so period $1$.
Preview Started at $1$, the chain is eventually trapped in $\{3,4\}$ with probability $\frac13$ and in $\{5,6\}$ with probability $\frac23$ (Theorem 3.13 below). Because $\{3,4\}$ is periodic, $p_{13}^{(n)}$ does not converge: numerically $p_{13}^{(50)}\approx0.212$ but $p_{13}^{(51)}\approx0.121$. Load this chain in Interactive 2.

Absorption Probabilities and the Gambler's Ruin

When a chain has transient states and several closed classes, two practical questions arise. Into which closed class will it eventually fall, and how long does that take? Both are answered by first-step analysis: condition on the first transition and use the Markov property.

📐 Theorem 3.13 — Hitting probabilities and expected hitting times

Let $A\subseteq S$, $H^A=\inf\{n\ge0:X_n\in A\}$, $h_i=P_i(H^A\lt\infty)$ and $k_i=E_i(H^A)$ (possibly $\infty$).

  1. $(h_i)$ is the minimal nonnegative solution of $\ h_i=1\ (i\in A)$, $\ h_i=\sum_{j}p_{ij}h_j\ (i\notin A)$.
  2. $(k_i)$ is the minimal nonnegative solution of $\ k_i=0\ (i\in A)$, $\ k_i=1+\sum_{j\notin A}p_{ij}k_j\ (i\notin A)$.
  3. (Fundamental matrix) Let $S$ be finite, $T$ the set of transient states and order the states so that $P=\begin{pmatrix}Q&R\\0&P_{\mathrm{rec}}\end{pmatrix}$ with $Q$ indexed by $T\times T$. Then $I-Q$ is invertible, $N=(I-Q)^{-1}=\sum_{n\ge0}Q^n$, and for $i,j\in T$ and recurrent $k$: $N_{ij}$ is the expected number of visits to $j$ (counting time $0$) starting from $i$; $B=NR$ has entries $B_{ik}=P_i(\text{the first recurrent state entered is }k)$; and $t=N\mathbf 1$ gives the expected time spent in $T$, i.e. the expected time to absorption.

Proof. (1) The equations. If $i\in A$ then $H^A=0$ and $h_i=1$. If $i\notin A$ then $H^A\ge1$, and by the Markov property at time $1$, $P_i(H^A\lt\infty\mid X_1=j)=h_j$; total probability gives $h_i=\sum_jp_{ij}h_j$.

Minimality. Let $x\ge0$ be any solution. For $i\notin A$, $$x_i=\sum_{j\in A}p_{ij}+\sum_{j\notin A}p_{ij}x_j=\sum_{j\in A}p_{ij}+\sum_{j\notin A}p_{ij}\Big(\sum_{k\in A}p_{jk}+\sum_{k\notin A}p_{jk}x_k\Big)=P_i(H^A=1)+P_i(H^A=2)+\sum_{j,k\notin A}p_{ij}p_{jk}x_k.$$ Repeating the substitution $n$ times and dropping the last (nonnegative) term gives $x_i\ge P_i(H^A\le n)$ for every $n$, so $x_i\ge\lim_nP_i(H^A\le n)=h_i$.

(2) The same argument with "one more step" counted: for $i\notin A$, $E_i(H^A\mid X_1=j)=1+k_j$, hence $k_i=1+\sum_{j\notin A}p_{ij}k_j$. If $y\ge0$ is a solution, $n$ substitutions give $y_i\ge\sum_{m=1}^{n}P_i(H^A\ge m)$, and the right side increases to $\sum_{m\ge1}P_i(H^A\ge m)=E_i(H^A)$.

(3) $(Q^n)_{ij}$ is the probability of being at the transient state $j$ at time $n$ having stayed in $T$, which is at most $p_{ij}^{(n)}\to0$ (geometrically, Theorem 3.9(d)). So $Q^n\to0$, and $(I-Q)(I+Q+\cdots+Q^n)=I-Q^{n+1}\to I$: the series $\sum Q^n$ converges and is the inverse of $I-Q$. Its $(i,j)$ entry is $\sum_nP_i(X_n=j,\ X_0,\dots,X_n\in T)=E_i(\text{visits to }j)$, since a chain that leaves $T$ never returns (Theorem 3.8(2): recurrent classes are closed). The first recurrent state entered is $k$ at time $n+1$ when the chain is at some $j\in T$ at time $n$ and jumps to $k$; summing over $n$ and $j$ gives $B=\sum_nQ^nR=NR$. Finally the time to absorption is the total number of visits to $T$, with expectation $\sum_{j\in T}N_{ij}$. ∎

For the chain of Example 5 with $A=\{3,4\}$: $h_1=\frac12h_1+\frac12h_2$ and $h_2=\frac14h_1+\frac14\cdot1+\frac12\cdot0$ (since $h_5=0$: the closed class $\{5,6\}$ never reaches $A$). The first equation gives $h_1=h_2$, and then $h_2=\frac14h_2+\frac14$, so $h_1=h_2=\frac13$. The expected time to leave $\{1,2\}$ solves $k_1=1+\frac12k_1+\frac12k_2$, $k_2=1+\frac14k_1$, so $k_1=4$, $k_2=2$. In matrix form $Q=\begin{pmatrix}\frac12&\frac12\\\frac14&0\end{pmatrix}$ and $N=(I-Q)^{-1}=\begin{pmatrix}\frac83&\frac43\\\frac23&\frac43\end{pmatrix}$, whose row sums are $4$ and $2$.

Minimality matters on infinite state spaces, where the system may have several nonnegative solutions; it singles out the correct one, as in Example 4(d) and in Theorem 3.14(b). On a finite state space from which $A$ is reached with probability one, the bounded solution is unique.

✏️ Example 6 — Deuce in tennis
At deuce, the server wins each point independently with probability $p$ ($q=1-p$). From deuce the game moves to "advantage server" or "advantage receiver"; from an advantage the game either ends (if the player with the advantage wins the point) or returns to deuce. For $p=0.6$ find, starting from deuce, (a) the probability that the server wins the game and (b) the expected number of further points played. Then (c) find both quantities for general $p$.
Chain Transient states $D$ (deuce), $A_s$ (advantage server), $A_r$ (advantage receiver); absorbing states $W_s$, $W_r$. In the order $D,A_s,A_r$, $$Q=\begin{pmatrix}0&p&q\\q&0&0\\p&0&0\end{pmatrix},\qquad R=\begin{pmatrix}0&0\\p&0\\0&q\end{pmatrix}.$$
(c) Win probability With $h$ the probability that the server wins: $h_D=p\,h_{A_s}+q\,h_{A_r}$, $h_{A_s}=p+q\,h_D$, $h_{A_r}=p\,h_D$. Substituting, $h_D=p^2+pq\,h_D+qp\,h_D$, so $h_D=\dfrac{p^2}{1-2pq}=\dfrac{p^2}{p^2+q^2}$.
(c) Duration $k_D=1+p\,k_{A_s}+q\,k_{A_r}$, $k_{A_s}=1+q\,k_D$, $k_{A_r}=1+p\,k_D$. Then $k_D=1+(p+q)+2pq\,k_D$, so $k_D=\dfrac{2}{1-2pq}=\dfrac{2}{p^2+q^2}$. (Each "round" of two points ends the game with probability $p^2+q^2$, so the number of rounds is geometric with mean $\frac1{p^2+q^2}$.)
(a), (b) Numbers For $p=0.6$: $p^2+q^2=0.36+0.16=0.52$, so $h_D=\frac{0.36}{0.52}=\frac9{13}\approx0.692$ and $k_D=\frac2{0.52}=\frac{50}{13}\approx3.85$ points. The fundamental matrix confirms it: $N=(I-Q)^{-1}=\frac1{13}\begin{pmatrix}25&15&10\\10&19&4\\15&9&19\end{pmatrix}$, the first row of $NR$ is $(\frac9{13},\frac4{13})$, and the first row sum of $N$ is $\frac{50}{13}$.
Insight A $60\%$ edge on single points becomes a $69\%$ edge from deuce; the structure of the game amplifies small advantages.

The gambler's ruin problem of §1.2 is the absorbing chain on $\{0,1,\dots,N\}$ with $p_{i,i+1}=p$, $p_{i,i-1}=q$ for $0\lt i\lt N$ and $0$, $N$ absorbing. There we found the probability $P_i=\frac{1-\rho^i}{1-\rho^N}$ ($\rho=q/p\ne1$) or $\frac iN$ ($p=q$) of reaching $N$ before $0$. Theorem 3.13 now gives the expected length of the game and the case of an infinitely rich opponent.

📐 Theorem 3.14 — Gambler's ruin: duration and the infinite casino

(a) The expected duration $D_i=E_i\big(H^{\{0,N\}}\big)$ of the game is

$$D_i=i(N-i)\ \ (p=q=\tfrac12),\qquad D_i=\frac{i}{q-p}-\frac{N}{q-p}\cdot\frac{1-\rho^i}{1-\rho^N}\ \ (p\ne q).$$

(b) Against an infinitely rich opponent (the chain on $\{0,1,2,\dots\}$ with $0$ absorbing), the probability of eventual ruin starting from $i\ge1$ is $1$ if $p\le q$ and $\rho^i=(q/p)^i$ if $p\gt q$. (c) If $p=q=\frac12$, ruin is certain but its expected time $E_i(H^{\{0\}})$ is infinite.

Proof. (a) By Theorem 3.13(2), $D_0=D_N=0$ and $D_i=1+pD_{i+1}+qD_{i-1}$ for $0\lt i\lt N$. On a finite state space this system has exactly one solution (the matrix $I-Q$ is invertible), so it suffices to check the formulas. For $p=q=\frac12$: $$1+\tfrac12(i+1)(N-i-1)+\tfrac12(i-1)(N-i+1)=1+\big(i(N-i)-1\big)=i(N-i).$$ For $p\ne q$: the homogeneous equation $D_i=pD_{i+1}+qD_{i-1}$ has the solutions $\alpha+\beta\rho^i$, and $\frac{i}{q-p}$ is a particular solution, since $1+\frac{p(i+1)+q(i-1)}{q-p}=1+\frac{i-(q-p)}{q-p}=\frac{i}{q-p}$. The stated formula is of the form $\frac{i}{q-p}+\alpha+\beta\rho^i$ and vanishes at $i=0$ and $i=N$.

(b) By Theorem 3.13(1), the ruin probabilities $r_i$ form the minimal nonnegative solution of $r_0=1$, $r_i=pr_{i+1}+qr_{i-1}$ ($i\ge1$). The general solution with $r_0=1$ is $r_i=\alpha+(1-\alpha)\rho^i$ if $\rho\ne1$ and $r_i=1+\beta i$ if $\rho=1$. If $\rho\gt1$ ($p\lt q$), nonnegativity for large $i$ forces $1-\alpha\ge0$, and $r_i=\rho^i-\alpha(\rho^i-1)$ is smallest at $\alpha=1$: $r\equiv1$. If $\rho=1$, nonnegativity forces $\beta\ge0$ and the minimum is at $\beta=0$: $r\equiv1$. If $\rho\lt1$ ($p\gt q$), letting $i\to\infty$ shows $\alpha\ge0$, and the minimum is at $\alpha=0$: $r_i=\rho^i$.

(c) Let $\tau_N$ be the duration of the game with the upper barrier at $N$ ($N\gt i$). The walk cannot reach $N$ before time $N-i$, and the times $\tau_N$ increase to the ruin time $H^{\{0\}}$ of the walk without upper barrier as $N\to\infty$. By monotone convergence $E_i(H^{\{0\}})=\lim_Ni(N-i)=\infty$. ∎

✏️ Example 7 — How long does the game last?
A gambler starts with ₹3 and plays ₹1 bets until she has ₹10 or nothing. (a) For a fair game find the expected number of bets. (b) For $p=0.45$ find the probability that she reaches ₹10 and the expected number of bets. (c) If instead she plays with $p=0.6$ against a casino with unlimited funds and stops only when ruined, what is the probability that she is never ruined?
(a) $D_3=3(10-3)=21$ bets.
(b) Winning $\rho=\frac{0.55}{0.45}=\frac{11}9$. The probability of reaching ₹10 is $\frac{1-\rho^3}{1-\rho^{10}}=\frac{1-1.8258}{1-7.4388}\approx0.1283$.
(b) Duration $D_3=\frac{3}{0.1}-\frac{10}{0.1}\times0.1283=30-12.83=17.17$ bets. The unfavourable game is shorter than the fair one: the downward drift ends it sooner.
(c) By Theorem 3.14(b), $P(\text{ruin})=(q/p)^3=(2/3)^3=\frac8{27}$, so she is never ruined with probability $\frac{19}{27}\approx0.704$. With $p=\frac12$ she would be ruined with certainty, but only after an infinite expected time.
Check Solving the $9\times9$ linear system $D_i=1+0.45D_{i+1}+0.55D_{i-1}$ numerically gives $D_3=17.1748$.
Interactive 2 — Classify a Chain: Classes, Recurrence, Periods and Absorption

Pick a chain, or generate a random sparse one. The lab computes the communicating classes from the arrows alone and colours them: green = closed (recurrent), amber = not closed (transient). It also finds each class's period and, by solving the equations of Theorem 3.13, the probability of being absorbed in each closed class from the start state. A token (red) then runs the chain from the start state. Each run is restarted once the token has spent $25$ steps in a closed class, and the tally of where the runs end up approaches the computed absorption probabilities. The visit counts under the nodes show transient states being left behind for good.

classes—
periods—
absorption probabilities (exact)—
runs finished: share per class—
⚠️ Counterexamples and pitfalls
  1. A function of a Markov chain need not be Markov. Lumping the states $\{1,2\}$ of the cycle $1\to2\to3\to1$ (Example 3(b)) gives a process whose next value depends on two past values. The same holds for $Y_n=\xi_n+\xi_{n+1}$ with iid Bernoulli $\xi_n$ (Exercise I.6).
  2. Condition on an exact present state. $P(X_{n+1}=j\mid X_n\in\{a,b\},\ \text{past})$ may depend on the past, because the past changes the odds between $a$ and $b$. The Markov property is about $X_n=i$ for a single $i$.
  3. Rows, not columns. Rows of $P$ sum to $1$; columns need not. A matrix with column sums $1$ but not row sums $1$ is not a transition matrix (in our row convention).
  4. Aperiodic does not need a self-loop. Return times $3$ and $4$ give period $\gcd(3,4)=1$ (Exercise II.2). Conversely, the period is a gcd and not the shortest return time: return times $4$ and $6$ give period $2$, not $4$ (Exam corner E2).
  5. Irreducible does not mean aperiodic. The walk on $\mathbb{Z}$ and the Ehrenfest chain are irreducible with period $2$.
  6. "Closed implies recurrent" is only for finite classes. The walk on $\mathbb{Z}$ with $p=0.6$ is irreducible (so $S$ is one closed class) and every state is transient.
  7. Recurrent does not mean $p_{ii}^{(n)}\not\to0$. For the symmetric walk on $\mathbb{Z}$, $p_{00}^{(2n)}\sim1/\sqrt{\pi n}\to0$, yet $\sum_np_{00}^{(n)}=\infty$ and $0$ is recurrent. The test is the divergence of the series, not the size of its terms.
  8. A recurrent state cannot lead to a transient one, but a transient state can lead to a recurrent one. Transient classes drain into closed classes; never the other way (Theorem 3.8(2)).
  9. Infinite chains may have no closed class and no recurrent state. The deterministic shift $i\mapsto i+1$ on $\mathbb{Z}$ has singleton classes, none closed. Theorems 3.5(c) and 3.9(a) need finiteness.
  10. Recurrence fails in dimension three. The symmetric walk returns to the origin with probability one on $\mathbb{Z}$ and $\mathbb{Z}^2$ but not on $\mathbb{Z}^3$ (Pólya).
  11. Certain absorption does not mean finite expected time. The fair gambler against an infinite casino is ruined with probability $1$, but the expected time to ruin is infinite (Theorem 3.14(c)).
  12. Take the minimal solution. For the walk with $p\gt q$, both $r_i\equiv1$ and $r_i=(q/p)^i$ solve the ruin equations; the ruin probability is the minimal nonnegative one, $(q/p)^i$.
  13. The last visit is not a stopping time. The strong Markov property may be applied at first passage times, not at the last exit from a set.

Exercises

I
Transition matrices and $n$-step probabilities.
  • 1 For $P=\begin{pmatrix}\frac12&\frac12&0\\\frac14&\frac12&\frac14\\0&\frac12&\frac12\end{pmatrix}$ on $\{1,2,3\}$, compute $P^2$, $P(X_2=3\mid X_0=1)$ and $p_{11}^{(3)}$.
  • 2 For the chain of part 1 with $X_0$ uniform on $\{1,2,3\}$, find the distributions of $X_1$ and $X_2$. What do you notice?
  • 3 In the weather chain of Example 1, find $P(X_1=C,\ X_3=R\mid X_0=S)$.
  • 4 A two-state chain has $p_{12}=0.3$ and $p_{21}=0.2$. Find a formula for $p_{11}^{(n)}$, compute $P^4$ and find $\lim_nP^n$.
  • 5 Show that an iid sequence $X_0,X_1,\dots$ with values in $S$ and common distribution $\nu$ is a Markov chain, and find its transition matrix. Conversely, find exactly when a Markov$(\lambda,P)$ chain is an iid sequence.
  • 6 Let $\xi_0,\xi_1,\dots$ be iid Bernoulli$(\frac12)$ and $Y_n=\xi_n+\xi_{n+1}$. Show that $(Y_n)$ is not a Markov chain, but that $Z_n=(\xi_n,\xi_{n+1})$ is, and find the transition matrix of $(Z_n)$.
  • 7 For the running maximum $M_n$ of die rolls (Example 3(a)), find $P(M_3=6\mid M_1=4)$ in two ways: from the matrix $P^2$ and directly.
  • 8 (Dynkin's criterion) Let $\{B_1,\dots,B_r\}$ be a partition of $S$ such that $\sum_{j\in B_t}p_{ij}=\hat p_{st}$ depends only on the block $B_s$ containing $i$. Prove that $Y_n=s$ when $X_n\in B_s$ defines a Markov chain with transition matrix $(\hat p_{st})$. Show that no partition of the weather chain of Example 1 into two blocks satisfies the criterion.
Check lab: the $n$-step matrix $P^n$ (Theorem 3.2)

Type a $3\times3$ transition matrix (decimals or fractions such as 1/4), choose $n$, and read off $P^n$. It starts with the weather chain of Example 1. Use it to check parts 1, 3 and 4 (enter the two-state chain as a $3\times3$ matrix with an isolated absorbing third state), and watch the rows of $P^n$ become equal as $n$ grows.

2
row sums of P—
largest gap between rows of Pⁿ—
1 $P^2=\begin{pmatrix}\frac38&\frac12&\frac18\\\frac14&\frac12&\frac14\\\frac18&\frac12&\frac38\end{pmatrix}$, so $P(X_2=3\mid X_0=1)=\frac18$ (the only path is $1\to2\to3$, probability $\frac12\cdot\frac14$). Then $p_{11}^{(3)}=\sum_kp_{1k}^{(2)}p_{k1}=\frac38\cdot\frac12+\frac12\cdot\frac14+\frac18\cdot0=\frac5{16}$.
2 $\lambda P=\frac13\left(\frac12+\frac14,\ \frac12+\frac12+\frac12,\ \frac14+\frac12\right)=\left(\frac14,\frac12,\frac14\right)$, and $\left(\frac14,\frac12,\frac14\right)P=\left(\frac14,\frac12,\frac14\right)$ again. After one step the distribution no longer changes: $(\frac14,\frac12,\frac14)$ is a stationary distribution (§3.2).
3 By the Markov property, $P_S(X_1=C,X_3=R)=p_{SC}\,p_{CR}^{(2)}=0.3\times0.27=0.081$, using the $(C,R)$ entry of $P^2$ from Example 1.
4 Theorem 3.3 with $a=0.3$, $b=0.2$, $\alpha=0.5$: $p_{11}^{(n)}=0.4+0.6(0.5)^n$, $p_{22}^{(n)}=0.6+0.4(0.5)^n$. So $P^4=\begin{pmatrix}0.4375&0.5625\\0.375&0.625\end{pmatrix}=\begin{pmatrix}\frac7{16}&\frac9{16}\\\frac38&\frac58\end{pmatrix}$ and $P^n\to\begin{pmatrix}0.4&0.6\\0.4&0.6\end{pmatrix}$.
5 By independence $P(X_{n+1}=j\mid X_0=i_0,\dots,X_n=i)=P(X_{n+1}=j)=\nu_j$, so the chain is Markov with every row of $P$ equal to $\nu$. Conversely, if every row of $P$ equals some $\nu$, the product formula of Theorem 3.1 gives $P(X_0=i_0,\dots,X_n=i_n)=\lambda_{i_0}\nu_{i_1}\cdots\nu_{i_n}$, so the $X_k$ are independent with $X_k\sim\nu$ for $k\ge1$. The chain is iid exactly when all rows of $P$ are equal (to $\nu$, say) and $\lambda=\nu$; if the rows differ, $X_{n+1}$ depends on $X_n$.
6 $Y_0=0$ forces $\xi_1=0$; with $Y_1=1$ this gives $\xi_2=1$, so $P(Y_2=2\mid Y_1=1,Y_0=0)=P(\xi_3=1)=\frac12$. But $Y_0=2$ forces $\xi_1=1$, then $Y_1=1$ gives $\xi_2=0$ and $Y_2=\xi_3\le1$: $P(Y_2=2\mid Y_1=1,Y_0=2)=0$. So $(Y_n)$ is not Markov. $Z_{n+1}=(\xi_{n+1},\xi_{n+2})$ shares its first coordinate with the second coordinate of $Z_n$ and has an independent fresh second coordinate: from $(x,y)$ the chain goes to $(y,0)$ or $(y,1)$ with probability $\frac12$ each.
7 From the matrix: $p_{46}^{(2)}=p_{44}p_{46}+p_{45}p_{56}+p_{46}p_{66}=\frac46\cdot\frac16+\frac16\cdot\frac16+\frac16\cdot1=\frac{11}{36}$. Directly: $M_3=\max(M_1,\xi_2,\xi_3)=6$ iff at least one of $\xi_2,\xi_3$ is $6$, which has probability $1-\left(\frac56\right)^2=\frac{11}{36}$.
8 Using the product formula, $P(Y_0=s_0,\dots,Y_n=s_n)=\sum\lambda_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}$ over $i_k\in B_{s_k}$. Sum first over $i_n\in B_{s_n}$: this gives the factor $\hat p_{s_{n-1}s_n}$, which does not depend on $i_{n-1}$. Then sum over $i_{n-1}$, and so on. The result is $P(Y_0=s_0)\,\hat p_{s_0s_1}\cdots\hat p_{s_{n-1}s_n}$, and Theorem 3.1(a) applies. Weather chain: the three two-block partitions are $\{S\}|\{C,R\}$, $\{C\}|\{S,R\}$, $\{R\}|\{S,C\}$. The criterion requires, respectively, $p_{CS}=p_{RS}$ ($0.3\ne0.2$), $p_{SC}=p_{RC}$ ($0.3\ne0.4$), $p_{SR}=p_{CR}$ ($0.1\ne0.3$). All fail.
II
Classes, closed sets and periods.
  • 1 Classify the states and find the periods for the chain on $\{1,\dots,5\}$ with $p_{12}=p_{23}=1$, $p_{31}=p_{34}=\frac12$, $p_{44}=\frac13$, $p_{45}=\frac23$, $p_{54}=1$.
  • 2 The chain on $\{0,1,2,3\}$ moves $0\to1\to2\to3$ deterministically and from $3$ goes to $0$ or to $1$ with probability $\frac12$ each. Show that it is irreducible and aperiodic although $p_{ii}=0$ for every $i$.
  • 3 (Ehrenfest urn) Four balls are distributed between two urns; at each step a ball chosen uniformly at random is moved to the other urn. Let $X_n$ be the number of balls in the first urn. Write down $P$ and show that the chain is irreducible with period $2$.
  • 4 Show that if $P$ is irreducible, $|S|\ge2$ and $P$ is symmetric ($p_{ij}=p_{ji}$), then the period is $1$ or $2$. Give an example of each.
  • 5 For the simple random walk on a finite connected graph (from a vertex, move to a uniformly chosen neighbour), show that the chain is irreducible, and that it is aperiodic if and only if the graph contains a cycle of odd length.
  • 6 Give an example of an irreducible chain in which every state is transient, and an example of a chain with infinitely many states and no closed class.
  • 7 Let $|S|=s$ be finite and $i\ne j$ with $i\to j$. Prove that $p_{ij}^{(n)}\gt0$ for some $n\le s-1$.
  • 8 Prove that if $C$ is a closed set then the restriction $(p_{ij})_{i,j\in C}$ is a stochastic matrix. Give an example of a closed set that is not a communicating class.
1 The arrows are $1\to2\to3\to1$, $3\to4$, $4\to4$, $4\to5$, $5\to4$. Classes: $\{1,2,3\}$, which is not closed ($3\to4$) and so is transient, with period $3$ (returns to $1$ only along the triangle, in multiples of $3$ steps); and $\{4,5\}$, which is closed and so recurrent, and aperiodic because $p_{44}\gt0$.
2 $0\to1\to2\to3\to0$ shows that all states communicate. State $1$ returns along $1\to2\to3\to1$ (length $3$) and along $1\to2\to3\to0\to1$ (length $4$); $\gcd(3,4)=1$, so the chain is aperiodic by Theorem 3.11.
3 $p_{i,i-1}=\frac i4$, $p_{i,i+1}=\frac{4-i}4$ for $i=0,\dots,4$. Consecutive states communicate, so the chain is irreducible. Each step changes the parity of $X_n$, so returns occur only at even times, and $0\to1\to0$ is a return in two steps: the period is $2$.
4 Irreducibility and $|S|\ge2$ give some $j\ne i$ with $p_{ij}\gt0$, and then $p_{ii}^{(2)}\ge p_{ij}p_{ji}=p_{ij}^2\gt0$. So $d(i)$ divides $2$. Period $2$: $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Period $1$: $P=\begin{pmatrix}\frac12&\frac12\\\frac12&\frac12\end{pmatrix}$.
5 Connectedness means every vertex can be reached along edges, which is irreducibility. Every edge gives a return of length $2$ ($i\to j\to i$), so $d\in\{1,2\}$. If there is an odd cycle through some vertex $v$, then $v$ has return times $2$ and an odd number, so $d=1$. If there is no odd cycle the graph is bipartite (colour each vertex by the parity of its distance from a fixed vertex), every step changes colour, and $d=2$.
6 The walk on $\mathbb{Z}$ with $p=0.6$: irreducible and transient (Theorem 3.10). The deterministic shift $i\mapsto i+1$ on $\mathbb{Z}$: each class is a singleton $\{i\}$ and none is closed.
7 Take a path $i=i_0\to i_1\to\cdots\to i_n=j$ of positive-probability steps with $n$ as small as possible. If two of the states were equal, say $i_a=i_b$ with $a\lt b$, deleting the loop between them would give a shorter path. So the $n+1$ states are distinct, $n+1\le s$, and $p_{ij}^{(n)}\ge p_{i_0i_1}\cdots p_{i_{n-1}i_n}\gt0$.
8 For $i\in C$, $\sum_{j\in C}p_{ij}=\sum_{j\in S}p_{ij}-\sum_{j\notin C}p_{ij}=1-0=1$. Example: in Example 5, $\{3,4,5,6\}$ is closed (a union of two closed classes) but is not a class. And $S$ is always closed.
III
Recurrence, transience and random walks.
  • 1 For the chain on $\{1,2,3\}$ with $p_{ij}=\frac12$ for all $i\ne j$, find $f_{11}^{(n)}$ for all $n$, verify $f_{11}=1$, and compute $E_1(T_1)=\sum_nnf_{11}^{(n)}$.
  • 2 For the two-state chain of Theorem 3.3 with $0\lt a\le1$, $0\lt b\le1$, find $f_{11}^{(n)}$ and verify that $f_{11}=1$.
  • 3 Using Stirling's formula, show $p_{00}^{(2n)}\sim\frac{(4pq)^n}{\sqrt{\pi n}}$ for the simple random walk and deduce Theorem 3.10's recurrence criterion without generating functions.
  • 4 For the simple random walk with $p=\frac34$, find $f_{00}$, the expected number of returns to $0$ and $P_0(N_0\ge3)$.
  • 5 For the walk with $p\gt\frac12$, show by first-step analysis that $P_0(\text{ever visit }-1)=\frac qp$, and recover $f_{00}=1-|p-q|$ from this.
  • 6 For the symmetric walk on $\mathbb{Z}^2$, verify that $U_n=X_n+Y_n$ and $V_n=X_n-Y_n$ are independent symmetric simple random walks, and deduce $p_{00}^{(2n)}=\left[\binom{2n}{n}4^{-n}\right]^2$.
  • 7 For the walk with $p=\frac34$ started at $0$, find the expected number of visits to $5$ and to $-1$.
  • 8 Prove that in an irreducible recurrent chain, $P_i(N_j=\infty)=1$ for all states $i,j$.
1 $f_{11}^{(1)}=0$. For $n\ge2$ a first return at time $n$ means leaving $1$, alternating $n-2$ times between $2$ and $3$, and returning: $f_{11}^{(n)}=1\cdot\left(\frac12\right)^{n-2}\cdot\frac12=\left(\frac12\right)^{n-1}$. (Check: $f_{11}^{(2)}=\frac12$, $f_{11}^{(3)}=\frac14$.) Then $f_{11}=\sum_{n\ge2}2^{-(n-1)}=1$ and $E_1(T_1)=\sum_{n\ge2}n\,2^{-(n-1)}=\sum_{n\ge1}n2^{-(n-1)}-1=4-1=3$, which is $1/\pi_1$ for the uniform stationary distribution (§3.2).
2 $f_{11}^{(1)}=1-a$; for $n\ge2$ the chain jumps to $2$, stays there $n-2$ steps and returns: $f_{11}^{(n)}=a(1-b)^{n-2}b$. Sum: $1-a+ab\sum_{m\ge0}(1-b)^m=1-a+ab\cdot\frac1b=1$.
3 Stirling, $m!\sim\sqrt{2\pi m}\,(m/e)^m$, gives $\binom{2n}n=\frac{(2n)!}{(n!)^2}\sim\frac{\sqrt{4\pi n}\,(2n/e)^{2n}}{2\pi n\,(n/e)^{2n}}=\frac{4^n}{\sqrt{\pi n}}$. So $p_{00}^{(2n)}\sim\frac{(4pq)^n}{\sqrt{\pi n}}$. If $p\ne\frac12$ then $4pq\lt1$ and the series converges by comparison with $\sum(4pq)^n$: transient. If $p=\frac12$ the terms are asymptotic to $\frac1{\sqrt{\pi n}}$, and $\sum n^{-1/2}=\infty$: recurrent (limit comparison).
4 $f_{00}=1-|\frac34-\frac14|=\frac12$. Expected returns $\frac{f}{1-f}=1$. $P_0(N_0\ge3)=f_{00}^3=\frac18$ (Theorem 3.6).
5 As in Example 4(d), $h=P_0(\text{visit }-1)$ satisfies $h=q+ph^2$, with roots $1$ and $\frac qp\lt1$. The walk drifts to $+\infty$ almost surely (strong law: $X_n/n\to p-q\gt0$), so it visits $-1$ with probability less than one and $h=\frac qp$ (it is also the minimal root, Theorem 3.13). From $0$, an up-step leads to $1$, from where the walk hits $0$ with probability $\frac qp$ (same computation shifted); a down-step leads to $-1$, from where it hits $0$ with probability $1$ (upward drift). Hence $f_{00}=p\cdot\frac qp+q=2q=1-(p-q)=1-|p-q|$.
6 The four moves $(\pm1,0),(0,\pm1)$ change $(U,V)$ by $(1,1)$, $(-1,-1)$, $(1,-1)$, $(-1,1)$, each with probability $\frac14$. These are exactly the four combinations of independent $\pm1$ steps of $U$ and of $V$, each with probability $\frac12\cdot\frac12$. Successive steps are independent, so $U$ and $V$ are independent symmetric walks. $(X_n,Y_n)=(0,0)$ iff $U_n=V_n=0$, so $p_{00}^{(2n)}=P(U_{2n}=0)P(V_{2n}=0)=\left[\binom{2n}n4^{-n}\right]^2$.
7 By Theorem 3.6, $E_0(N_j)=\frac{f_{0j}}{1-f_{jj}}$ with $f_{jj}=f_{00}=\frac12$. The walk drifts upwards and passes every level above $0$, so $f_{05}=1$ and $E_0(N_5)=\frac{1}{1/2}=2$. By part 5, $f_{0,-1}=\frac qp=\frac13$, so $E_0(N_{-1})=\frac{1/3}{1/2}=\frac23$.
8 By Theorem 3.8(2), $f_{ij}=1$ for all $i,j$. By Theorem 3.6, $P_i(N_j\ge k)=f_{ij}f_{jj}^{\,k-1}=1$ for every $k$, so $P_i(N_j=\infty)=1$.
IV
Absorption, duration and applications.
  • 1 Gambler's ruin with $N=5$ and $i=2$: find the expected duration for $p=\frac12$, and the winning probability and expected duration for $p=0.6$.
  • 2 For the walk on $\{0,1,2,3\}$ with $0,3$ absorbing, $p_{i,i+1}=\frac23$, $p_{i,i-1}=\frac13$ ($i=1,2$), compute the fundamental matrix $N$, the absorption matrix $B=NR$ and the expected absorption times.
  • 3 A fair coin is tossed until the pattern HH appears. Find the expected number of tosses with a two-state absorbing chain. Do the same for HT and explain why the answers differ.
  • 4 (Credit risk) A bond is rated A, B or in default D (absorbing). Yearly transitions: from A: to A $0.90$, to B $0.08$, to D $0.02$; from B: to A $0.10$, to B $0.80$, to D $0.10$. Find the expected time to default starting from A and from B, and the probability that an A-rated bond defaults within two years.
  • 5 (Moran model) A population of three genes contains $X_n$ copies of allele A. At each step one gene is chosen at random to reproduce and one, independently and at random, to die, so $p_{i,i+1}=p_{i,i-1}=\frac{i(3-i)}{9}$ for $i=1,2$ and $0,3$ are absorbing. Find the probability that A takes over the population starting from one copy, and the expected time until one allele is lost.
  • 6 For the walk on $\{0,1,2,\dots\}$ with $0$ absorbing and $p=0.6$ up, show that both $r_i\equiv1$ and $r_i=(2/3)^i$ solve the ruin equations. Which is the ruin probability, and why?
  • 7 A player with ₹3 plays with $p=0.6$ against an unlimited casino. Find the probability that she is ever ruined and the probability that she reaches ₹10 before being ruined.
  • 8 Let $S$ be finite and suppose that from every state some absorbing state is accessible. Prove that there are $m\ge1$ and $\delta\gt0$ with $P_i(H^A\gt km)\le(1-\delta)^k$ for all $i$ and $k$, where $A$ is the set of absorbing states. Deduce that $E_i(H^A)\lt\infty$.
1 $p=\frac12$: $D_2=2\cdot3=6$. $p=0.6$: $\rho=\frac23$, winning probability $\frac{1-\rho^2}{1-\rho^5}=\frac{5/9}{211/243}=\frac{135}{211}\approx0.640$; $D_2=\frac{2}{-0.2}-\frac{5}{-0.2}\cdot\frac{135}{211}=-10+25\cdot\frac{135}{211}=\frac{1265}{211}\approx5.995$ bets.
2 $Q=\begin{pmatrix}0&\frac23\\\frac13&0\end{pmatrix}$, $\det(I-Q)=1-\frac29=\frac79$, $N=\frac97\begin{pmatrix}1&\frac23\\\frac13&1\end{pmatrix}=\begin{pmatrix}\frac97&\frac67\\\frac37&\frac97\end{pmatrix}$. With $R=\begin{pmatrix}\frac13&0\\0&\frac23\end{pmatrix}$ (columns: absorbed at $0$, at $3$), $B=NR=\begin{pmatrix}\frac37&\frac47\\\frac17&\frac67\end{pmatrix}$. Expected times: row sums of $N$, $\frac{15}7$ from $1$ and $\frac{12}7$ from $2$. Check against §1.2: from $1$, $P(\text{reach }3)=\frac{1-\rho}{1-\rho^3}$ with $\rho=\frac12$: $\frac{1/2}{7/8}=\frac47$.
3 HH: states $0$ (no progress) and $1$ (last toss H). $k_0=1+\frac12k_1+\frac12k_0$, $k_1=1+\frac12\cdot0+\frac12k_0$. So $k_0=2+k_1$ and $k_1=1+\frac12k_0$, giving $k_0=6$. HT: $k_0=1+\frac12k_1+\frac12k_0$, $k_1=1+\frac12k_1$ (after H, a further H keeps the progress), so $k_1=2$, $k_0=4$. A failure after partial progress towards HH sends us back to the start, while for HT an extra H does not destroy the progress. This is the self-overlap of HH.
4 $Q=\begin{pmatrix}0.9&0.08\\0.1&0.8\end{pmatrix}$, $\det(I-Q)=0.1\cdot0.2-0.08\cdot0.1=0.012$, $N=\frac1{0.012}\begin{pmatrix}0.2&0.08\\0.1&0.1\end{pmatrix}=\begin{pmatrix}\frac{50}3&\frac{20}3\\\frac{25}3&\frac{25}3\end{pmatrix}$. Expected time to default: $\frac{70}3\approx23.3$ years from A, $\frac{50}3\approx16.7$ years from B. Within two years from A: $p_{AD}^{(2)}=0.9(0.02)+0.08(0.1)+0.02(1)=0.046$.
5 From $1$ and $2$ the chain moves up or down with probability $\frac29$ each and otherwise stays. Fixation: $h_1=\frac29h_2+\frac59h_1$ (with $h_0=0$), $h_2=\frac29+\frac29h_1+\frac59h_2$. So $h_1=\frac12h_2$, $h_2=\frac12+\frac12h_1$, giving $h_1=\frac13$, $h_2=\frac23$: the fixation probability equals the initial frequency, as for any neutral allele. Time: $k_1=1+\frac59k_1+\frac29k_2$ and by symmetry $k_1=k_2$, so $\frac29k_1=1$ and $k_1=\frac92$ steps. (Check: $N=\begin{pmatrix}3&\frac32\\\frac32&3\end{pmatrix}$, row sums $\frac92$.)
6 Both satisfy $r_0=1$ and $r_i=0.6r_{i+1}+0.4r_{i-1}$: for $r_i=\rho^i$, $0.6\rho^{i+1}+0.4\rho^{i-1}=\rho^{i-1}(0.6\rho^2+0.4)=\rho^{i-1}\cdot\frac23=\rho^i$ with $\rho=\frac23$. The ruin probability is the minimal nonnegative solution (Theorem 3.13), namely $(2/3)^i$; the solution $r\equiv1$ would say that ruin is certain, which contradicts the upward drift.
7 $P(\text{ruin})=(2/3)^3=\frac8{27}\approx0.296$. Reaching ₹10 before ruin is the finite gambler's ruin with $N=10$: $\frac{1-(2/3)^3}{1-(2/3)^{10}}=\frac{19/27}{58025/59049}=\frac{41553}{58025}\approx0.716$.
8 For each non-absorbing $i$ there are $m_i\le|S|$ and a path to $A$ of length $m_i$ with positive probability. Put $m=|S|$ and let $\delta\gt0$ be the smallest of the probabilities $P_i(H^A\le m)$ over the non-absorbing $i$. By the Markov property at times $m,2m,\dots$, $P_i(H^A\gt(k+1)m)\le P_i(H^A\gt km)(1-\delta)$, which gives the bound. Then $E_i(H^A)=\sum_{n\ge0}P_i(H^A\gt n)\le m\sum_{k\ge0}(1-\delta)^k=\frac m\delta\lt\infty$.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

E1. CSIR Part B A Markov chain on $\{1,2,3\}$ has transition matrix $P=\begin{pmatrix}0&\frac12&\frac12\\\frac13&\frac13&\frac13\\1&0&0\end{pmatrix}$. Then $P(X_2=1\mid X_0=1)$ equals (A) $\frac16$; (B) $\frac12$; (C) $\frac23$; (D) $\frac56$.

Idea $p_{11}^{(2)}=\sum_kp_{1k}p_{k1}$ (Chapman–Kolmogorov), summing over the intermediate state.
Computation $p_{11}p_{11}+p_{12}p_{21}+p_{13}p_{31}=0+\frac12\cdot\frac13+\frac12\cdot1=\frac16+\frac12=\frac23$. Option (A) keeps only the path through $2$, (B) only the path through $3$.
Answer (C).

E2. CSIR Part B A chain on $\{1,\dots,6\}$ has $p_{12}=p_{23}=p_{34}=1$, $p_{41}=p_{45}=\frac12$, $p_{56}=p_{61}=1$. The period of state $1$ is (A) $1$; (B) $2$; (C) $4$; (D) $6$.

Return times From $1$ the chain returns along $1\to2\to3\to4\to1$ (length $4$) or $1\to2\to3\to4\to5\to6\to1$ (length $6$), and every return is a sequence of these two loops. So the return times are the numbers $4a+6b$ with $a+b\ge1$.
gcd $\gcd(4,6)=2$, so $d(1)=2$, although no return is possible in exactly $2$ steps. (C) confuses the period with the shortest return time.
Answer (B).

E3. CSIR Part B GATE ST A simple random walk on $\mathbb{Z}$ starts at $0$ and moves up with probability $0.7$ and down with probability $0.3$ at each step. The expected number of returns to $0$ (at times $n\ge1$) is (A) $0.6$; (B) $1.5$; (C) $2.5$; (D) $\infty$.

Idea $f_{00}=1-|p-q|=1-0.4=0.6$ (Theorem 3.10); the number of returns $N_0$ satisfies $P(N_0\ge k)=f_{00}^k$.
Computation $E(N_0)=\frac{f_{00}}{1-f_{00}}=\frac{0.6}{0.4}=1.5$; equivalently $\frac1{|p-q|}-1=2.5-1$. Option (A) is the return probability, (C) forgets to subtract the $n=0$ term, and (D) would be the answer for a fair walk.
Answer (B).

E4. CSIR Part C Consider Markov chains with a finite state space. Which of the following statements are true? (One or more options may be correct.) (A) Every such chain has at least one recurrent state. (B) Every irreducible such chain is aperiodic. (C) If the chain is irreducible and $p_{ii}\gt0$ for some state $i$, then every state is aperiodic. (D) A transient state can be accessible from a recurrent state.

(A) True Theorem 3.9(a): a closed class exists and finite closed classes are recurrent.
(B) False $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ is irreducible with period $2$.
(C) True $p_{ii}\gt0$ gives $d(i)=1$, and the period is a class property (Theorem 3.11).
(D) False If $i$ is recurrent and $i\to j$, then $j$ is in the (closed) class of $i$ and is recurrent (Theorem 3.8(2)).
Answer (A) and (C).

E5. CSIR Part C A chain on $\{1,\dots,5\}$ has transition matrix $$P=\begin{pmatrix}1&0&0&0&0\\[2pt]\frac13&0&\frac23&0&0\\[2pt]0&\frac12&0&\frac12&0\\[2pt]0&0&0&\frac12&\frac12\\[2pt]0&0&0&\frac12&\frac12\end{pmatrix}.$$ Which of the following are true? (A) States $2$ and $3$ are transient. (B) Starting from $2$, the chain is absorbed at state $1$ with probability $\frac12$. (C) State $4$ has period $2$. (D) $\lim_{n\to\infty}p_{23}^{(n)}$ exists and is strictly positive.

Classes $\{1\}$ (absorbing), $\{2,3\}$ (not closed: $2\to1$, $3\to4$), $\{4,5\}$ (closed).
(A) True $\{2,3\}$ is a non-closed class of a finite chain, hence transient (Theorem 3.9(c)).
(B) True $h_2=\frac13+\frac23h_3$ and $h_3=\frac12h_2+\frac12\cdot0$, so $h_2=\frac13+\frac13h_2$ and $h_2=\frac12$. (Also $h_3=\frac14$, and the expected absorption time from $2$ is $\frac52$.)
(C) False $p_{44}=\frac12\gt0$, so state $4$ is aperiodic. (The transient class $\{2,3\}$ does have period $2$.)
(D) False $3$ is transient, so $p_{23}^{(n)}\to0$ (Theorem 3.6).
Answer (A) and (B).

E6. CSIR Part C GATE ST Let $(X_n)$ be the simple random walk on $\mathbb{Z}$ with $X_0=0$ and up-probability $p\in(0,1)$. Which of the following are true? (A) If $p=\frac12$, state $0$ is recurrent and $p_{00}^{(n)}\to0$. (B) If $p=\frac13$, then $\sum_{n\ge1}p_{00}^{(n)}=3$. (C) If $p\ne\frac12$, the walk visits $0$ only finitely often, almost surely. (D) The symmetric simple random walk on $\mathbb{Z}^3$ is recurrent.

(A) True Recurrent by Theorem 3.10, while $p_{00}^{(2n)}\sim\frac1{\sqrt{\pi n}}\to0$ and the odd terms are $0$.
(B) False $4pq=\frac89$, so $\sum_{n\ge0}p_{00}^{(n)}=(1-\frac89)^{-1/2}=3$ including the term $p_{00}^{(0)}=1$. The sum from $n=1$ is $2$ $(=\frac1{|p-q|}-1=3-1)$.
(C) True The walk is transient, and a transient state is visited finitely often almost surely (Theorem 3.6).
(D) False Pólya: transient in dimension $d\ge3$.
Answer (A) and (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Markov chains and $P^n$. Definition 3.1 with the weather chain drawn as a diagram; Theorems 3.1 and 3.2 (Example 1 on the board, then project the check lab with $n=1,2,5,20$). Theorem 3.3 and Example 2. Example 3: let students vote "Markov or not?" before revealing (b). Close with stopping times and the strong Markov property (state it, prove it at the end if time allows).
  2. Classes and recurrence. Definition 3.4 and Theorem 3.5 with a picture of classes as "boxes with one-way doors". Theorem 3.6 carefully: the geometric number of returns is the key idea. Theorems 3.8 and 3.9, then the random walk (Theorem 3.10) with Interactive 1 at $p=0.5$, $0.55$ and $0.6$. Example 4.
  3. Periods and absorption. Definition 3.6, Theorems 3.11 and 3.12 (the gcd lemma is short; do it). Example 5, then Interactive 2 on the same chain. Theorem 3.13 by first-step analysis, Example 6 (tennis) on the board, Theorem 3.14 and Example 7. Finish with E2 and E5 done live.

Discussion questions. (1) A drunkard on a line returns home with probability one; a drunk bird in space may never return. Why does dimension matter? (2) Is the sequence of daily closing prices of a stock plausibly a Markov chain? What would you need to know to decide? (3) Why is the minimal solution of the absorption equations the right one, and what does a non-minimal solution "mean"?

Misconceptions to watch for. Taking the period to be the shortest return time; believing a self-loop is needed for aperiodicity; "closed implies recurrent" on infinite spaces; "recurrent implies $p_{ii}^{(n)}$ does not tend to $0$"; summing columns of $P$ instead of rows; treating a lumped chain as Markov; counting the $n=0$ term in $\sum p_{ii}^{(n)}$; forgetting that the ruin probability is the minimal solution.

Suggested homework. I(1, 3, 4, 6, 8), II(1, 2, 5, 7), III(1, 4, 5, 6), IV(1, 3, 4, 6); Exam corner E3, E4, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 45 minutes

Research question. In a long random DNA sequence (each letter A, C, G, T independently with probability $\frac14$), every four-letter word occurs at a given position with the same probability $4^{-4}$. Why, then, does the motif TATA take longer on average to appear for the first time than GATA? And in a coin-tossing race between two patterns, why can one pattern beat another more than half the time although both are equally likely at every position?

Why it matters. Genome scientists look for short motifs such as transcription-factor binding sites and need to know how often a motif appears by chance alone before claiming that a match is biologically meaningful. Waiting times for patterns also matter in quality control (runs of defective items), in the design of error-detecting codes and in the analysis of streaks in sport. The tool in every case is the absorbing Markov chain whose state is "how much of the pattern has just been matched".

What to do.

  1. For a pattern $w$ of length $m$, build the chain on $\{0,1,\dots,m\}$ in which state $k$ means that the last $k$ letters read agree with the first $k$ letters of $w$ (the longest such $k$), with $m$ absorbing. Write down $Q$ for HH, HT, HTH and HHT and compute the expected waiting times with $N=(I-Q)^{-1}$ (Theorem 3.13).
  2. Do the same for the DNA motifs GATA, TATA, ACG, ACA and AAA (alphabet of size $4$), by hand for the short ones and by computer for the others.
  3. Compare your answers with Conway's formula $E(T_w)=\sum_kc^k$, where $c$ is the alphabet size and the sum is over the $k$ for which the last $k$ letters of $w$ equal its first $k$ letters (always including $k=m$). Explain in words why self-overlap delays the first occurrence.
  4. Penney's game: build a chain whose absorbing states are "HHT appeared first" and "HTH appeared first", and compute the probability that HHT wins. Check it by simulating $10^5$ races.

Tools: Python with numpy (or a spreadsheet with matrix inversion); a random number generator for the simulation.

Hand in: A one-page table of patterns, their overlap structure and their expected waiting times, with one paragraph explaining the result for TATA versus GATA, and your Penney's-game probability with its simulation check.

Going further. Read about the "martingale of gamblers" proof of Conway's formula (each gambler bets on the next letters of the pattern), and about Penney's non-transitive patterns: for every three-letter coin pattern there is another one that beats it.

Instructor note: expected waiting times are HH $6$, HT $4$, HTH $10$, HHT $8$, HHH $14$; for DNA, ACG $64$, ACA $68$, AAA $84$, GATA $256$, TATA $272$ (TATA overlaps itself in "TA", contributing an extra $4^2=16$). In the race, HHT beats HTH with probability $\frac23$, and THH beats HHT with probability $\frac34$. Both values are easily confirmed by simulation.

🧪 Self-check quiz

0/5 correct

Q1. For an irreducible Markov chain on a finite state space, which statement is always true?

Q2. In an irreducible chain, $p_{ii}\gt0$ for one state $i$. Then necessarily

Q3. A simple random walk on $\mathbb{Z}$ steps up with probability $0.8$. The probability that it ever returns to its starting point is

Q4. If state $i$ is recurrent and $i\to j$, then

Q5. Which condition is equivalent to state $i$ being transient?