37.05.04 · probability / 05-markov-chains

The Strong Markov Property and the Recurrence/Transience Dichotomy

shipped3 tiersLean: none

Anchor (Master): Norris 1997 *Markov Chains* (Cambridge) §1.3-1.5, §1.7-1.8; Durrett 2019 *Probability: Theory and Examples* 5e §5.3-5.4; Levin-Peres 2017 *Markov Chains and Mixing Times* 2e §1.5, Ch. 21; Spitzer 1976 *Principles of Random Walk* 2e §§7-8 (Pólya's theorem)

Intuition Beginner

A Markov chain forgets its past: where it goes next depends only on where it is now, not on how it got there. The strong Markov property is the same forgetfulness, but applied at a smarter moment than a fixed clock time. Suppose you watch the chain and wait until the first time it lands back on its starting state. That moment is random — you do not know it in advance — yet at the instant it happens the chain restarts as if brand new, with no memory of the loop it just completed. The walk from your home, the moment it returns home, begins a fresh and independent copy of the same walk.

This restarting is the engine behind the central question of this unit: if you start at a state and walk forever, do you come back? A state is called recurrent if return is certain — you will come home again, and having come home you will (by the fresh restart) come home again, and again, infinitely often. A state is transient if there is a real chance you never return: each time you are home you flip a biased coin to decide whether you will ever see home again, and eventually one of those flips says no, so you visit home only finitely many times and then wander off forever.

There is a clean way to tell which case you are in. Add up, over all future times, the chance of being back at the start exactly at that time. If this grand total is infinite, the state is recurrent; if it is finite, the state is transient. Infinite expected number of visits means certain return; a finite expected number means eventual escape.

The most famous example is a walker stepping randomly on a grid. On a line and on a flat plane the walker is recurrent: it always finds its way home. In three-dimensional space it is transient: there is enough room to get lost forever. This is Pólya's theorem, and its one-line slogan is that a drunk man finds his way home but a drunk bird may not.

The takeaway: the strong Markov property lets a chain restart at a random return time, and that fresh restart splits every state cleanly into recurrent (return is sure, visited infinitely often) or transient (escape is possible, visited finitely often), decided by whether the total return probability over all times is infinite or finite.

Visual Beginner

Picture a single path that keeps coming back to its home state, cut into independent loops at each homecoming.

Top: the walk is chopped at each return to the home state $H$ . The strong Markov property says the arched segments between returns — the excursions — are independent and identically distributed: each one is a fresh run of the chain started at $H$ and stopped when it next returns. Bottom: a walker on a line keeps drifting back to where it started (recurrent), while a walker in a three-dimensional lattice has enough directions to escape and never return (transient). The number of excursions is finite exactly when the state is transient.

Worked example Beginner

Take a chain on three states ${A, B, C}$ . From $A$ the walk goes to $B$ for certain. From $B$ it returns to $A$ with chance $\frac{1}{2}$ and goes on to $C$ with chance $\frac{1}{2}$ . State $C$ is a trap: once there, the walk stays at $C$ forever. We ask whether $A$ is recurrent and how many times we expect to visit it.

Step 1. Find the return probability for $A$ . Starting at $A$ , the walk must first step to $B$ (this is certain). From $B$ it comes back to $A$ with chance $\frac{1}{2}$ , and otherwise slips into the trap $C$ and never comes back. So the chance of ever returning to $A$ after leaving it is exactly $\frac{1}{2}$ .

Step 2. Decide recurrent or transient. The return probability is $\frac{1}{2}$ , which is less than $1$ . Return is not certain, so $A$ is transient. Each visit to $A$ is followed by a return with probability $\frac{1}{2}$ and a permanent escape with probability $\frac{1}{2}$ .

Step 3. Count the expected visits. Think of each stay at $A$ as a coin flip: heads (chance $\frac{1}{2}$ ) you will return and visit again, tails (chance $\frac{1}{2}$ ) you are done with $A$ forever. The number of visits to $A$ is therefore like the number of flips until the first tail. The expected number of visits when each return has probability $f = \frac{1}{2}$ is $\frac{1}{1 - f} = \frac{1}{1 - 1/2} = 2$ .

Step 4. Sanity check against the slogan. A finite expected number of visits, here $2$ , is the signature of a transient state. A recurrent state would have return probability exactly $1$ and an infinite expected number of visits.

What this tells us: the single number $f = \frac{1}{2}$ — the chance of ever returning — decides everything. Because $f < 1$ , state $A$ is transient and is visited on average $\frac{1}{1 - f} = 2$ times. We read off the entire long-run behavior from one return probability, exactly the bookkeeping the strong Markov property makes rigorous.

Check your understanding Beginner

Exercise (easy, multiple choice).

A state $i$ is recurrent when which condition holds?

A. The chain starts at $i$ B. Starting from $i$ , the chain is certain to return to $i$ at some later time C. The chain visits $i$ exactly once D. The chain never leaves $i$

Hint

Recurrence is about whether return is guaranteed, not about staying put or starting there.

Answer

B. Return is certain. A state is recurrent when, starting from it, the probability of ever returning equals $1$ ; by the fresh-restart property this forces infinitely many returns. Feedback-correct: certain return is what distinguishes recurrent from transient states. Feedback-wrong: D describes an absorbing state (a special recurrent case), C describes a transient state visited once, and A is just the starting condition and says nothing about return.

Formal definition Intermediate+

Throughout, $(X_{n})_{n \geq 0}$ is a time-homogeneous Markov chain on a countable state space $I$ with stochastic transition matrix $P = (p_{ij})$ and $n$ -step matrix $P^{n} = (p_{ij}^{(n)})$ , in the sense of 37.05.01; classes, accessibility, and irreducibility are as in 37.05.02. We write $P_{i}$ and $E_{i}$ for probability and expectation conditioned on $X_{0} = i$ . The natural filtration is $F_{n} = σ (X_{0}, \dots, X_{n})$ , and stopping times are as in 37.04.01: a map $T : Ω \to {0, 1, 2, \dots} \cup {\infty}$ with ${T = n} \in F_{n}$ for every $n$ .

Definition (hitting and first-return times). For a state $j \in I$ , the first passage time is $T_{j} := in f {n \geq 1 : X_{n} = j}$ (with $in f \emptyset = \infty$ ). When the chain starts at $j$ this is the first return time. The first-passage probabilities are $f_{ij}^{(n)} := P_{i} (T_{j} = n)$ and the eventual-hitting probability is $f_{ij} := P_{i} (T_{j} < \infty) = n \geq 1 \sum f_{ij}^{(n)} .$ The quantity $f_{ii}$ is the return probability of state $i$ .

Definition (shift operator). On the canonical path space $I^{{0, 1, 2, \dots}}$ the shift $θ_{m}$ acts by $(θ_{m} ω)_{n} = ω_{m + n}$ , so $X_{n} \circ θ_{m} = X_{m + n}$ . For a stopping time $T$ , the shift at $T$ is $θ_{T} := θ_{T (ω)}$ on ${T < \infty}$ .

Definition (strong Markov property). The chain has the strong Markov property if for every stopping time $T$ , every state $j$ , and every event $H$ measurable with respect to the post- $T$ process, on the event ${T < \infty, X_{T} = j}$ the conditional law of $(X_{T + n})_{n \geq 0}$ given $F_{T}$ is $P_{j}$ . Concretely, for every bounded function $F$ on path space and every $A \in F_{T}$ , $E_{i} [1_{A} 1_{{T < \infty}} F (θ_{T} ω)] = E_{i} [1_{A} 1_{{T < \infty}} E_{X_{T}} [F]] .$ Every discrete-time Markov chain on a countable state space has this property (proved in the Key theorem by summing the ordinary Markov property over the disjoint events ${T = m}$ ).

Definition (number of visits and Green function). The number of visits to $i$ is $V_{i} := \sum_{n \geq 0} 1_{{X_{n} = i}}$ , counting the time- $0$ visit, and the number of visits after time $0$ is $V_{i}^{'} := \sum_{n \geq 1} 1_{{X_{n} = i}}$ . The Green function (or potential) is $G_{ij} := E_{i} [V_{j}] = n \geq 0 \sum p_{ij}^{(n)} .$ The diagonal $G_{ii} = \sum_{n \geq 0} p_{ii}^{(n)}$ is the expected number of visits to $i$ starting from $i$ .

Definition (recurrence and transience). A state $i$ is recurrent if $f_{ii} = P_{i} (T_{i} < \infty) = 1$ and transient if $f_{ii} < 1$ . The Key theorem shows this is equivalent to $G_{ii} = \infty$ (recurrent) versus $G_{ii} < \infty$ (transient), and to $P_{i} (V_{i} = \infty) = 1$ versus $P_{i} (V_{i} = \infty) = 0$ . A recurrent state is positive recurrent if the expected return time $m_{i} := E_{i} [T_{i}]$ is finite and null recurrent if $m_{i} = \infty$ ; this finer split is the subject of 37.05.05 and is not needed here.

Counterexamples to common slips Intermediate+

Hitting time uses $n \geq 1$ , not $n \geq 0$ . If $T_{j}$ were defined with $in f {n \geq 0}$ , then $T_{i} = 0$ automatically under $P_{i}$ and recurrence would become vacuous. The first return must take at least one step; the convention $T_{j} = in f {n \geq 1 : X_{n} = j}$ is what makes $f_{ii}$ a genuine return probability.
A stopping time can be infinite, and the strong Markov restart is asserted only on ${T < \infty}$ . Forgetting the indicator $1_{{T < \infty}}$ produces false identities: there is no "restart" on the paths that never hit $j$ .
Recurrence is about certainty of return, not speed of return. A null-recurrent state has $f_{ii} = 1$ (certain return) yet $E_{i} [T_{i}] = \infty$ (infinite mean return time); the symmetric walk on $Z$ is the standard example. Certain return and finite mean return time are different conditions.
Transience is not the same as having an escape route to an absorbing trap. A state can be transient inside an infinite irreducible chain with no absorbing states at all — the simple random walk on $Z^{3}$ — where transience comes from dimensional room to wander, not from a trapping class.

Key theorem with proof Intermediate+

Theorem (strong Markov property and the recurrence dichotomy). Let $(X_{n})$ be a Markov chain on $I$ with matrix $P$ .

(a) (Strong Markov property.) For every stopping time $T$ , on ${T < \infty}$ the process $(X_{T + n})_{n \geq 0}$ is, conditionally on $F_{T}$ and on ${X_{T} = j}$ , a Markov chain started at $j$ with matrix $P$ , independent of $F_{T}$ .

(b) (Geometric visit law and the dichotomy.) Write $f = f_{ii}$ . Under $P_{i}$ the number of visits $V_{i}$ satisfies $P_{i} (V_{i} \geq 1 + r) = f^{r}$ for $r \geq 0$ , so $V_{i}$ is geometric. Consequently $G_{ii} = E_{i} [V_{i}] = \frac{1}{1 - f _{ii}} (= \infty when f_{ii} = 1),$ and the following are equivalent: (i) $i$ is recurrent ( $f_{ii} = 1$ ); (ii) $P_{i} (V_{i} = \infty) = 1$ ; (iii) $G_{ii} = \sum_{n \geq 0} p_{ii}^{(n)} = \infty$ . When any (hence all) fail, $i$ is transient, $V_{i}$ is finite a.s. with $E_{i} [V_{i}] = (1 - f_{ii})^{- 1} < \infty$ , and $p_{ii}^{(n)} \to 0$ .

Proof. Part (a). Fix $A \in F_{T}$ , a state $j$ , and a bounded path functional $F$ . Decompose ${T < \infty}$ over the disjoint events ${T = m}$ , $m \geq 0$ . On ${T = m}$ the shift $θ_{T}$ equals $θ_{m}$ and $X_{T} = X_{m}$ , and the event $A \cap {T = m} \in F_{m}$ since $A \in F_{T}$ . The ordinary Markov property of 37.05.01 at the fixed time $m$ states that, conditionally on $F_{m}$ , the future $(X_{m + n})_{n}$ is a chain started at $X_{m}$ with matrix $P$ ; hence $E_{i} [1_{A \cap {T = m, X_{m} = j}} F (θ_{m} ω)] = E_{i} [1_{A \cap {T = m, X_{m} = j}}] E_{j} [F] .$ Summing over $m \geq 0$ collapses the left side to $E_{i} [1_{A} 1_{{T < \infty, X_{T} = j}} F (θ_{T} ω)]$ and the right side to $P_{i} (A \cap {T < \infty, X_{T} = j}) E_{j} [F]$ , which is the asserted restart identity. Taking $F$ a function of $(X_{0}, \dots, X_{k})$ and varying $k$ identifies the conditional law as $P_{j}$ .

Part (b). Let $T_{i}^{(1)} = T_{i}$ be the first return time and, recursively, let $T_{i}^{(r + 1)}$ be the first time after $T_{i}^{(r)}$ that the chain is again at $i$ ; each is a stopping time. The event ${V_{i} \geq 1 + r}$ — at least $r$ returns after time $0$ — equals ${T_{i}^{(r)} < \infty}$ . We show $P_{i} (T_{i}^{(r)} < \infty) = f^{r}$ by induction. For $r = 1$ this is the definition $f = f_{ii} = P_{i} (T_{i} < \infty)$ . Assume $P_{i} (T_{i}^{(r)} < \infty) = f^{r}$ . On ${T_{i}^{(r)} < \infty}$ the chain is at $i$ at time $T_{i}^{(r)}$ , so by the strong Markov property (a) the post- $T_{i}^{(r)}$ process is a fresh chain started at $i$ , and the event of one further return is ${T_{i} \circ θ_{T_{i}^{(r)}} < \infty}$ , which has probability $f$ and is independent of $F_{T_{i}^{(r)}}$ . Hence $P_{i} (T_{i}^{(r + 1)} < \infty) = P_{i} (T_{i}^{(r)} < \infty) \cdot f = f^{r} \cdot f = f^{r + 1} .$

Thus $P_{i} (V_{i} \geq 1 + r) = f^{r}$ . If $f = 1$ then $P_{i} (V_{i} \geq 1 + r) = 1$ for all $r$ , so $P_{i} (V_{i} = \infty) = 1$ and $G_{ii} = E_{i} [V_{i}] = \infty$ . If $f < 1$ then $V_{i} - 1$ is geometric with $P_{i} (V_{i} = 1 + r) = f^{r} (1 - f)$ , so $P_{i} (V_{i} < \infty) = 1$ and $G_{ii} = E_{i} [V_{i}] = r \geq 0 \sum P_{i} (V_{i} \geq 1 + r) = r \geq 0 \sum f^{r} = \frac{1}{1 - f} .$ Finally $G_{ii} = \sum_{n \geq 0} p_{ii}^{(n)}$ because $E_{i} [V_{i}] = E_{i} [\sum_{n} 1_{{X_{n} = i}}] = \sum_{n} P_{i} (X_{n} = i) = \sum_{n} p_{ii}^{(n)}$ by monotone convergence. The three conditions are therefore equivalent, and in the transient case the summability of $\sum_{n} p_{ii}^{(n)}$ forces $p_{ii}^{(n)} \to 0$ . $□$

Bridge. This theorem builds toward the entire stationary-distribution and convergence theory of 37.05.05 and appears again in every hitting-time and Green-function computation for Markov chains, because the geometric visit law and the series criterion $\sum_{n} p_{ii}^{(n)}$ are the precise gateway from a one-step matrix to long-run behavior. The foundational reason the visit count is geometric is the strong Markov restart: each return to $i$ launches an independent fresh copy of the chain, so successive returns are independent Bernoulli $(f)$ trials, and this is exactly the excursion decomposition that underlies the renewal-theoretic proof of the ergodic theorem. The series criterion $G_{ii} = (1 - f_{ii})^{- 1}$ is dual to the optional-stopping identity of 37.04.01, where the same restart-at-a-stopping-time mechanism turns a martingale into a hitting-time calculus; here the predictable stake is replaced by the indicator of "still to return," and the central insight is that recurrence is the statement that the geometric series of return probabilities diverges. Putting these together, the strong Markov property converts a question about an infinite path into independent excursions, and the bridge is that recurrence versus transience is decided entirely by whether the return probability $f_{ii}$ equals $1$ or is strictly less.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the first-passage decomposition of the diagonal generating function: for $n \geq 1$ , $p_{ii}^{(n)} = m = 1 \sum n f_{ii}^{(m)} p_{ii}^{(n - m)},$ and deduce that the generating functions $P_{ii} (s) = \sum_{n \geq 0} p_{ii}^{(n)} s^{n}$ and $F_{ii} (s) = \sum_{n \geq 1} f_{ii}^{(m)} s^{m}$ satisfy $P_{ii} (s) = 1 + F_{ii} (s) P_{ii} (s)$ for $∣ s ∣ < 1$ .

Hint

Condition on the time $m$ of the first return to $i$ and apply the strong (or ordinary) Markov property at that time; then multiply by $s^{n}$ and sum.

Answer

Fix $n \geq 1$ . Partition ${X_{n} = i}$ (under $P_{i}$ ) by the time $m = T_{i}$ of the first return, $1 \leq m \leq n$ . On ${T_{i} = m}$ the strong Markov property restarts the chain at $i$ at time $m$ , so $P_{i} (X_{n} = i ∣ T_{i} = m) = p_{ii}^{(n - m)}$ , giving $p_{ii}^{(n)} = \sum_{m = 1}^{n} P_{i} (T_{i} = m) p_{ii}^{(n - m)} = \sum_{m = 1}^{n} f_{ii}^{(m)} p_{ii}^{(n - m)}$ . Multiply by $s^{n}$ and sum over $n \geq 1$ : the right side is the Cauchy product $F_{ii} (s) P_{ii} (s)$ , while the left side is $P_{ii} (s) - p_{ii}^{(0)} = P_{ii} (s) - 1$ . Hence $P_{ii} (s) = 1 + F_{ii} (s) P_{ii} (s)$ , i.e. $P_{ii} (s) = (1 - F_{ii} (s))^{- 1}$ . Letting $s ↑ 1$ and applying Abel's theorem recovers $G_{ii} = (1 - f_{ii})^{- 1}$ , the analytic form of the dichotomy.

Exercise 4 (medium, symbolic).

Using the Green-function relation $G_{ij} = f_{ij} G_{j j}$ for $i \neq = j$ , prove that if $j$ is transient then $\sum_{n \geq 0} p_{ij}^{(n)} < \infty$ for every $i$ , and hence $p_{ij}^{(n)} \to 0$ .

Hint

First establish $G_{ij} = f_{ij} G_{j j}$ by conditioning on the first hitting time $T_{j}$ and using the strong Markov property at $T_{j}$ .

Answer

Condition on $T_{j}$ . Under $P_{i}$ a visit to $j$ at time $n$ requires $T_{j} \leq n$ , and on ${T_{j} = m}$ the strong Markov property restarts the chain at $j$ , so $P_{i} (X_{n} = j) = \sum_{m = 1}^{n} f_{ij}^{(m)} p_{j j}^{(n - m)}$ . Summing over $n \geq 0$ and exchanging the (nonnegative) sums, $G_{ij} = \sum_{m \geq 1} f_{ij}^{(m)} \sum_{k \geq 0} p_{j j}^{(k)} = f_{ij} G_{j j}$ . If $j$ is transient then $G_{j j} = (1 - f_{j j})^{- 1} < \infty$ by the dichotomy, so $G_{ij} = f_{ij} G_{j j} \leq G_{j j} < \infty$ . A convergent series has vanishing terms, so $p_{ij}^{(n)} \to 0$ for every starting state $i$ .

Exercise 5 (medium, numeric).

For the symmetric simple random walk on $Z$ , the return-to-origin probabilities are $p_{00}^{(2 n)} = (n 2 n) 2^{- 2 n}$ and $p_{00}^{(2 n + 1)} = 0$ . Using Stirling's approximation $(n 2 n) 2^{- 2 n} \sim (π n)^{- 1/2}$ , decide whether $\sum_{n} p_{00}^{(n)}$ converges, and state whether the walk is recurrent or transient.

Hint

Compare $\sum_{n} n^{- 1/2}$ with the $p$ -series threshold $p = 1$ .

Answer

By Stirling, $p_{00}^{(2 n)} \sim (π n)^{- 1/2} = π^{- 1/2} n^{- 1/2}$ . The series $\sum_{n} n^{- 1/2}$ is a $p$ -series with $p = 1/2 \leq 1$ , hence diverges. Therefore $G_{00} = \sum_{n} p_{00}^{(n)} = \infty$ , and by the dichotomy the origin is recurrent. By the solidarity theorem the whole (irreducible) walk on $Z$ is recurrent. This is the $d = 1$ case of Pólya's theorem: the return probability decays like $n^{- 1/2}$ , just slowly enough to keep the walk recurrent.

Exercise 7 (hard, symbolic).

Prove the solidarity theorem: if $i \leftrightarrow j$ (they communicate) and $i$ is recurrent, then $j$ is recurrent. Conclude that recurrence and transience are class properties.

Hint

Pick $r, s$ with $p_{ij}^{(r)} > 0$ and $p_{j i}^{(s)} > 0$ , then bound $p_{j j}^{(s + n + r)} \geq p_{j i}^{(s)} p_{ii}^{(n)} p_{ij}^{(r)}$ and sum over $n$ .

Answer

Since $i \leftrightarrow j$ , choose $r, s \geq 1$ with $α := p_{ij}^{(r)} > 0$ and $β := p_{j i}^{(s)} > 0$ . For every $n \geq 0$ , concatenating the three legs $j \to i$ (length $s$ ), $i \to i$ (length $n$ ), $i \to j$ (length $r$ ) and keeping a single term of each Chapman-Kolmogorov sum 37.05.01 gives $p_{j j}^{(s + n + r)} \geq p_{j i}^{(s)} p_{ii}^{(n)} p_{ij}^{(r)} = β p_{ii}^{(n)} α .$ Summing over $n \geq 0$ , $G_{j j} = \sum_{m \geq 0} p_{j j}^{(m)} \geq \sum_{n \geq 0} p_{j j}^{(s + n + r)} \geq α β \sum_{n \geq 0} p_{ii}^{(n)} = α β G_{ii}$ . Recurrence of $i$ means $G_{ii} = \infty$ by the dichotomy, and $α β > 0$ , so $G_{j j} = \infty$ , i.e. $j$ is recurrent. Contrapositively, if $j$ is transient so is $i$ ; hence within a communicating class all states are recurrent or all are transient, and recurrence/transience is a class property. Thus one may speak of a recurrent class or transient class, and an irreducible chain is recurrent or transient as a whole.

Exercise 8 (hard, symbolic).

Let $C$ be a recurrent communicating class. Prove that $C$ is closed (no state of $C$ leads out of $C$ ), and that from any $i \in C$ every $j \in C$ is hit with probability one: $f_{ij} = 1$ .

Hint

For closure, suppose $i \in C$ , $i \to k$ , $k \in / C$ and derive a positive escape probability contradicting $f_{ii} = 1$ . For $f_{ij} = 1$ , use the strong Markov property at successive returns to $i$ as independent trials each having a chance to reach $j$ .

Answer

Closure. Suppose $i \in C$ and $p_{ik}^{(m)} > 0$ for some $k \in / C$ and minimal $m$ . Then $k \neq \to i$ (else $k \leftrightarrow i$ , contradicting $k \in / C$ ), so from $k$ the chain never returns to $i$ . Hence with probability at least $p_{ik}^{(m)} > 0$ the chain started at $i$ reaches $k$ and thereafter never returns to $i$ , giving $f_{ii} \leq 1 - p_{ik}^{(m)} < 1$ , contradicting recurrence. So no such $k$ exists and $C$ is closed.

Certainty of hitting. Fix $i, j \in C$ . Since $i \to j$ , there is $r$ with $ρ := p_{ij}^{(r)} > 0$ ; restricting to the closed class, from $i$ within $r$ steps the chain reaches $j$ with probability at least $ρ$ . By recurrence the chain returns to $i$ infinitely often a.s., and the strong Markov property makes the excursions between successive returns to $i$ independent and identically distributed. Each excursion has probability at least some $ρ^{'} > 0$ of hitting $j$ before the next return to $i$ (it can follow a fixed positive-probability path to $j$ ). With infinitely many independent excursions each succeeding with probability $\geq ρ^{'} > 0$ , the probability that $j$ is never hit is at most $lim_{N} (1 - ρ^{'})^{N} = 0$ . Hence $f_{ij} = P_{i} (T_{j} < \infty) = 1$ .

Advanced results Master

The excursion decomposition delivered by the strong Markov property is the organizing structure: it reduces an infinite trajectory to an i.i.d. sequence of loops, and every recurrence statement is a statement about that sequence. The series criterion, the solidarity theorem, and Pólya's dichotomy are three readings of the same decomposition.

Theorem 1 (Green-function / potential characterisation). For all $i, j$ , the Green function factors as $G_{ij} = δ_{ij} + f_{ij} G_{j j}$ , and $G_{j j} = (1 - f_{j j})^{- 1}$ . Hence $G_{j j} = \infty$ iff $j$ is recurrent, and for transient $j$ the matrix $G = (G_{ij}) = (I - P)^{- 1}$ in the sense $G = \sum_{n \geq 0} P^{n}$ is finite off any recurrent class and satisfies $(I - P) G = I$ on the transient states. The Green function is the discrete potential kernel: $G_{ij}$ is the expected number of visits to $j$ from $i$ , and on $Z^{d}$ for $d \geq 3$ it is the lattice analogue of the Newtonian potential $∣ x ∣^{- (d - 2)}$ , the source of the connection between transient random walks and classical potential theory.

Theorem 2 (recurrence is a closed class property; chain decomposition). Recurrence and transience are constant on communicating classes (solidarity), every recurrent class is closed, and a finite chain has at least one recurrent class with the transient states forming the strictly-upper part of the canonical block form of 37.05.02. On a finite state space transient classes are exactly the open (non-closed) classes, and every closed class is positive recurrent. The chain enters a recurrent class in finite expected time and is thereafter confined to it, visiting each of its states infinitely often a.s.; the long-run behavior is therefore governed entirely by the recurrent closed blocks, exactly the blocks to which the stationary theory of 37.05.05 applies.

Theorem 3 (Pólya's theorem). The simple symmetric random walk on $Z^{d}$ is recurrent for $d \in {1, 2}$ and transient for $d \geq 3$ . The proof is the series test applied to the local central limit asymptotics $p_{00}^{(2 n)} \sim c_{d} (4 π n)^{- d /2} \cdot 2^{d} \cdot \frac{1}{2}$ — more precisely $p_{00}^{(2 n)} \sim 2 (4 π n / d)^{- d /2}$ with a dimension-dependent constant — so that $\sum_{n} p_{00}^{(n)} ≍ \sum_{n} n^{- d /2}$ , which diverges for $d \leq 2$ and converges for $d \geq 3$ . An equivalent characterisation via Fourier analysis writes $G_{00} = (2 π)^{- d} \int_{[- π, π]^{d}} (1 - \hat{ϕ} (θ))^{- 1} d θ$ with $\hat{ϕ} (θ) = d^{- 1} \sum_{k} cos θ_{k}$ , and the singularity of $(1 - \hat{ϕ})^{- 1}$ at $θ = 0$ is integrable iff $d \geq 3$ , recovering the same dichotomy. The borderline $d = 2$ is null recurrent: $f_{00} = 1$ but $E_{0} [T_{0}] = \infty$ .

Theorem 4 (recurrence and the absence of nonconstant bounded harmonic functions). For an irreducible recurrent chain, every bounded $P$ -harmonic function ( $P h = h$ , $h$ bounded) is constant; equivalently the tail $σ$ -algebra is degenerate (only null and conull events) and the chain has a unique (up to scaling) invariant measure. Transience is precisely the regime where nonconstant bounded harmonic functions and a rich Martin boundary appear, and the Green function $G_{ij}$ becomes the kernel generating them. This is the entry point to discrete potential theory: recurrence is the discrete analogue of the parabolicity of a Riemannian manifold, and transience of its hyperbolicity, with $Z^{d}$ marking the transition at $d = 3$ .

Synthesis. The foundational reason the whole subject reduces to a single number is the strong Markov property: each return to a state launches an independent fresh excursion, so the number of returns is a sum of i.i.d. Bernoulli trials and the visit count is geometric, which is exactly why the recurrence dichotomy is the dichotomy of a geometric series. Putting these together, $G_{ii} = (1 - f_{ii})^{- 1}$ is dual to the optional-stopping identity of 37.04.01: there a predictable stake against a fair increment had zero conditional mean, here the indicator "still to return" against the restart kernel produces independent excursions, and both are the non-anticipation principle in different dress. This is exactly the central insight that organises the chapter: the support pattern and period of 37.05.02 decide which states communicate and with what rhythm, the return probability $f_{ii}$ decides whether a class is visited forever, and the stationary theory of 37.05.05 decides how often — and the bridge across all three is the excursion decomposition, since the expected return time $E_{i} [T_{i}]$ that splits null from positive recurrence is the expected length of a single excursion, whose reciprocal is the stationary mass at $i$ . The solidarity theorem generalises the dichotomy from a state to a class, Pólya's theorem instantiates it on the lattice through the local-central-limit decay of $p_{00}^{(2 n)}$ , and the Green-function characterisation lifts it into potential theory, where transience is the existence of a finite potential kernel and recurrence its divergence.

Full proof set Master

Proposition 1 (strong Markov property). For every stopping time $T$ , state $j$ , event $A \in F_{T}$ , and bounded path functional $F$ , $E_{i} [1_{A} 1_{{T < \infty, X_{T} = j}} F (θ_{T})] = P_{i} (A \cap {T < \infty, X_{T} = j}) E_{j} [F]$ .

Proof. Decompose over ${T = m}$ , $m \geq 0$ . Since $A \in F_{T}$ , $A \cap {T = m} \in F_{m}$ , and on this event $θ_{T} = θ_{m}$ , $X_{T} = X_{m}$ . The ordinary Markov property at the fixed time $m$ gives $E_{i} [1_{A \cap {T = m, X_{m} = j}} F (θ_{m})] = P_{i} (A \cap {T = m, X_{m} = j}) E_{j} [F]$ . Summing the nonnegative (or bounded, by dominated convergence) terms over $m$ and recombining ${T < \infty} = ⨆_{m} {T = m}$ yields the claim. $□$

Proposition 2 (geometric visit law). Under $P_{i}$ , with $f = f_{ii}$ , $P_{i} (V_{i} \geq 1 + r) = f^{r}$ for all $r \geq 0$ ; hence $G_{ii} = (1 - f)^{- 1}$ if $f < 1$ and $G_{ii} = \infty$ if $f = 1$ .

Proof. Let $T^{(r)}$ be the time of the $r$ -th return to $i$ (a stopping time), with $T^{(0)} = 0$ . Then ${V_{i} \geq 1 + r} = {T^{(r)} < \infty}$ . Induct: $P_{i} (T^{(0)} < \infty) = 1 = f^{0}$ , and on ${T^{(r)} < \infty}$ the chain sits at $i$ , so Proposition 1 makes ${T^{(r + 1)} < \infty} = {T_{i} \circ θ_{T^{(r)}} < \infty}$ independent of $F_{T^{(r)}}$ with probability $f$ , giving $P_{i} (T^{(r + 1)} < \infty) = f^{r + 1}$ . Summing the tail, $G_{ii} = E_{i} [V_{i}] = \sum_{r \geq 0} P_{i} (V_{i} \geq 1 + r) = \sum_{r \geq 0} f^{r}$ , which is $(1 - f)^{- 1}$ for $f < 1$ and $\infty$ for $f = 1$ . The identity $G_{ii} = \sum_{n} p_{ii}^{(n)}$ is Tonelli applied to $V_{i} = \sum_{n} 1_{{X_{n} = i}}$ . $□$

Proposition 3 (first-passage / Green factorisation). For $i \neq = j$ , $G_{ij} = f_{ij} G_{j j}$ ; for all $i, j$ , $G_{ij} = δ_{ij} + f_{ij} G_{j j}$ .

Proof. Under $P_{i}$ a visit to $j$ occurs only after $T_{j}$ . Conditioning on $T_{j} = m < \infty$ and applying Proposition 1 at $T_{j}$ (where $X_{T_{j}} = j$ ), $P_{i} (X_{m + k} = j ∣ T_{j} = m) = p_{j j}^{(k)}$ . Hence $E_{i} [V_{j}^{'}] = \sum_{m \geq 1} f_{ij}^{(m)} \sum_{k \geq 0} p_{j j}^{(k)} = f_{ij} G_{j j}$ , where $V_{j}^{'} = \sum_{n \geq 1} 1_{{X_{n} = j}}$ . Adding the time- $0$ term $δ_{ij}$ gives $G_{ij} = δ_{ij} + f_{ij} G_{j j}$ ; for $i \neq = j$ the $δ_{ij}$ drops. $□$

Proposition 4 (series criterion and solidarity). State $i$ is recurrent iff $\sum_{n} p_{ii}^{(n)} = \infty$ , and recurrence is constant on each communicating class.

Proof. The criterion is Proposition 2 combined with $G_{ii} = \sum_{n} p_{ii}^{(n)}$ : $f_{ii} = 1 \Leftrightarrow G_{ii} = \infty \Leftrightarrow \sum_{n} p_{ii}^{(n)} = \infty$ . For solidarity, let $i \leftrightarrow j$ with $α = p_{ij}^{(r)} > 0$ , $β = p_{j i}^{(s)} > 0$ . Then $p_{j j}^{(s + n + r)} \geq β p_{ii}^{(n)} α$ for every $n$ , so $\sum_{m} p_{j j}^{(m)} \geq α β \sum_{n} p_{ii}^{(n)}$ ; if the right side diverges so does the left, transferring recurrence from $i$ to $j$ . Symmetrically transience transfers, so the property is constant on the class. $□$

Proposition 5 (a recurrent class is closed and hit with certainty). If $C$ is recurrent then $C$ is closed, and $f_{ij} = 1$ for all $i, j \in C$ .

Proof. If some $i \in C$ had $p_{ik}^{(m)} > 0$ with $k \in / C$ , then $k \neq \to i$ , so escaping to $k$ (probability $\geq p_{ik}^{(m)} > 0$ ) precludes return, giving $f_{ii} < 1$ against recurrence; hence $C$ is closed. For $f_{ij} = 1$ : recurrence returns the chain to $i$ infinitely often, and by Proposition 1 the excursions between returns are i.i.d.; each has probability $\geq ρ^{'} > 0$ of reaching $j$ (follow a fixed positive-probability path inside the closed class), so among infinitely many independent excursions $j$ is hit a.s., $f_{ij} = 1$ . $□$

Proposition 6 (Pólya's dichotomy for $Z^{d}$ ). Simple symmetric random walk on $Z^{d}$ is recurrent for $d \leq 2$ and transient for $d \geq 3$ .

Proof. By the inversion formula $p_{00}^{(n)} = (2 π)^{- d} \int_{[- π, π]^{d}} \hat{ϕ} (θ)^{n} d θ$ with characteristic function $\hat{ϕ} (θ) = d^{- 1} \sum_{k = 1}^{d} cos θ_{k}$ . Summing the geometric series formally (justified by monotone convergence on $0 \leq s < 1$ and Abel's theorem), $G_{00} = n \geq 0 \sum p_{00}^{(n)} = (2 π)^{- d} \int_{[- π, π]^{d}} \frac{d θ}{1 - ϕ ^ ( θ )} .$ Near $θ = 0$ , $1 - \hat{ϕ} (θ) = d^{- 1} \sum_{k} (1 - cos θ_{k}) \sim (2 d)^{- 1} ∣ θ ∣^{2}$ , so the integrand behaves like $∣ θ ∣^{- 2}$ . In $d$ dimensions $\int_{∣ θ ∣ \leq ϵ} ∣ θ ∣^{- 2} d θ ≍ \int_{0}^{ϵ} ρ^{d - 1} ρ^{- 2} d ρ = \int_{0}^{ϵ} ρ^{d - 3} d ρ$ , finite iff $d - 3 > - 1$ , i.e. $d \geq 3$ . Thus $G_{00} = \infty$ for $d \leq 2$ (recurrent) and $G_{00} < \infty$ for $d \geq 3$ (transient). Equivalently, the local central limit theorem gives $p_{00}^{(2 n)} \sim c_{d} n^{- d /2}$ , and $\sum_{n} n^{- d /2}$ diverges iff $d \leq 2$ . $□$

Connections Master

The Markov property, transition matrices, and Chapman-Kolmogorov 37.05.01 supply the ordinary Markov property summed over ${T = m}$ to produce the strong Markov property, and the $n$ -step probabilities $p_{ii}^{(n)}$ whose series $\sum_{n} p_{ii}^{(n)} = G_{ii}$ is the recurrence criterion; every excursion bound in this unit is the single-term Chapman-Kolmogorov lower bound $p_{a c}^{(m + n)} \geq p_{ab}^{(m)} p_{b c}^{(n)}$ established there.
Class structure, irreducibility, and periodicity 37.05.02 is refined here: the solidarity theorem makes recurrence a class property exactly as period invariance made the period a class property, both proved by the same path-concatenation inequality, and a recurrent class is shown to be closed, locating it in the canonical block decomposition where the recurrent closed blocks carry all long-run behavior.
Discrete martingales, stopping times, and optional stopping 37.04.01 provide the stopping-time and shift machinery the strong Markov property is built on, and the Green-function identity $G_{ii} = (1 - f_{ii})^{- 1}$ is the excursion-theoretic twin of optional stopping: both compute a long-run quantity by restarting the process at a stopping time, and the asymmetric-walk martingale $(q / p)^{X_{n}}$ used there to find ruin probabilities is the analytic counterpart of the transience of the biased walk computed here.
The stationary-distribution and ergodic theory 37.05.05 consumes this unit's dichotomy directly: a stationary distribution exists on a recurrent class, and the positive/null split is decided by whether the expected excursion length $E_{i} [T_{i}]$ is finite, with the stationary mass at $i$ equal to its reciprocal — the strong-Markov excursion is the object the ergodic theorem averages over.

Historical & philosophical context Master

The recurrence/transience dichotomy for random walks was settled by George Pólya in 1921 ^{[Polya 1921]}, who proved that the simple symmetric walk returns to its origin with probability one in dimensions one and two but with probability strictly less than one in dimension three and higher; the popular summary that "a drunk man finds his way home but a drunk bird may not" condenses his result. Pólya's original argument estimated the return probabilities combinatorially; the Fourier-analytic form, integrating $(1 - \hat{ϕ} (θ))^{- 1}$ over the torus and reading off the dichotomy from the integrability of the singularity at the origin, is due to the later random-walk school and is presented systematically by Spitzer ^{[Spitzer 1976]}.

The strong Markov property was isolated as a theorem requiring proof — not a definitional given — in the work of Joseph Doob and Eugene Dynkin in the 1950s, with the countable-state discrete-time case being the elementary instance where summation over ${T = m}$ suffices and no regularity of paths is needed; the subtleties appear only in continuous time, where Dynkin's formulation and Hunt's theory of Markov processes made the strong Markov property the cornerstone of probabilistic potential theory. The systematic use of first-passage decompositions and taboo probabilities to organize recurrence is due to Kai Lai Chung ^{[Chung 1967]}, and the modern textbook synthesis on countable state spaces, defining recurrence through $f_{ii} = 1$ and the visit series, follows Norris ^{[Norris 1997]}. The identification of transience with the existence of a finite Green function, and hence with a substantive discrete potential theory and Martin boundary, links this elementary dichotomy to the harmonic analysis of the lattice and to the classification of Riemannian manifolds as parabolic or hyperbolic.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Polya1921,
  author  = {P\'olya, George},
  title   = {\"Uber eine {A}ufgabe der {W}ahrscheinlichkeitsrechnung betreffend die {I}rrfahrt im {S}trassennetz},
  journal = {Mathematische Annalen},
  volume  = {84},
  year    = {1921},
  pages   = {149--160}
}

@book{Spitzer1976,
  author    = {Spitzer, Frank},
  title     = {Principles of Random Walk},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976}
}

@book{Durrett2019mc,
  author    = {Durrett, Rick},
  title     = {Probability: Theory and Examples},
  edition   = {5},
  publisher = {Cambridge University Press},
  year      = {2019}
}

@book{Chung1967,
  author    = {Chung, Kai Lai},
  title     = {Markov Chains with Stationary Transition Probabilities},
  edition   = {2},
  series    = {Grundlehren der mathematischen Wissenschaften},
  publisher = {Springer},
  year      = {1967}
}

@book{LevinPeres2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {2},
  publisher = {American Mathematical Society},
  year      = {2017}
}

Prerequisites

37.05.01
37.05.02
37.04.01

Tier anchors

beginner: Norris 1997 *Markov Chains* (Cambridge) §1.3-1.5; informal picture of a walker restarting fresh each time it returns home, and the gambler's-ruin walk on the integers
intermediate: Norris 1997 *Markov Chains* (Cambridge) §1.3 (strong Markov property), §1.5 (recurrence and transience); Durrett 2019 *Probability: Theory and Examples* 5e §5.2-5.4
master: Norris 1997 *Markov Chains* (Cambridge) §1.3-1.5, §1.7-1.8; Durrett 2019 *Probability: Theory and Examples* 5e §5.3-5.4; Levin-Peres 2017 *Markov Chains and Mixing Times* 2e §1.5, Ch. 21; Spitzer 1976 *Principles of Random Walk* 2e §§7-8 (Pólya's theorem)

References

Norris — Markov Chains · Cambridge University Press 1997, §1.3 (strong Markov property), §1.5 (recurrence/transience), §1.7 (random walks)
Polya — Uber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz · Mathematische Annalen 84 (1921), 149-160
Durrett — Probability: Theory and Examples, 5e · §5.2-5.4 (strong Markov property, recurrence, transience)
Spitzer — Principles of Random Walk, 2e · Springer 1976, §§7-8 (recurrence of random walks, Pólya's theorem)
Chung — Markov Chains with Stationary Transition Probabilities, 2e · Springer 1967, Part I §§3-4 (taboo probabilities, recurrence)

Estimated time

beginner: 18m
intermediate: 52m
master: 90m