What does it mean for a state to be recurrent?

Starting from that state, the chain returns to it with probability one, and therefore returns infinitely often; a transient state is one the chain may leave forever with positive probability.

Why does dimension matter for random walk recurrence?

The simple symmetric random walk is recurrent in dimensions one and two but transient in three and higher, because the probability of returning to the origin depends on how quickly the walk can escape, which grows with dimension.

Markov Chain Classification and Recurrence

Classifying the states of a Markov chain reveals which states are visited infinitely often and which are eventually abandoned, partitioning the state space into communicating classes with shared long-run behaviour.

Definition

State classification analyses a Markov chain by grouping states that can reach one another into communicating classes and labelling each state as recurrent if the chain returns to it with probability one or transient if there is positive probability of never returning.

Scope

This topic covers the accessibility and communication relations, the decomposition of the state space into communicating classes, irreducibility, the recurrence-transience dichotomy and its criteria, positive versus null recurrence, periodicity, and the use of first-passage and hitting probabilities to determine these properties.

Core questions

When do two states communicate, and how does this partition the state space?
What distinguishes a recurrent state from a transient one?
How is positive recurrence separated from null recurrence?
What role does periodicity play in the chain's long-run behaviour?

Key theories

Recurrence-transience dichotomy: A state is recurrent if and only if the expected number of returns is infinite, equivalently the sum of its return probabilities diverges; recurrence and transience are class properties shared by all states that communicate.
Positive versus null recurrence: A recurrent state is positive recurrent when the expected return time is finite and null recurrent when it is infinite; positive recurrence is necessary for the existence of a stationary probability distribution.

Clinical relevance

Determining recurrence settles whether a random walk returns to its origin, whether a queue empties infinitely often, and whether a population process persists or is absorbed; Polya's classic result that the simple symmetric random walk is recurrent in one and two dimensions but transient in three or more is a canonical consequence.

History

The recurrence question was crystallised by Polya's 1921 analysis of random walks on integer lattices, and the systematic class-based theory of recurrence and transience was developed in the mid-twentieth century by Chung, Feller, and others into the form found in modern textbooks.

Key figures

George Polya
Andrey Markov
Kai Lai Chung

Seminal works

norris1997

Frequently asked questions

What does it mean for a state to be recurrent?: Starting from that state, the chain returns to it with probability one, and therefore returns infinitely often; a transient state is one the chain may leave forever with positive probability.
Why does dimension matter for random walk recurrence?: The simple symmetric random walk is recurrent in dimensions one and two but transient in three and higher, because the probability of returning to the origin depends on how quickly the walk can escape, which grows with dimension.