What is the difference between a recurrent and a transient state?

A recurrent state is one the chain is certain to return to, and so visits infinitely often, whereas a transient state is visited only finitely many times before the chain wanders away for good.

Why is simple random walk recurrent in low dimensions but not in high ones?

In one and two dimensions the walk returns to the origin with probability one, but from three dimensions onward there is enough room to escape, so the walk returns only finitely often and is transient; this is Polya's classical result.

Discrete-Time Markov Chains

A discrete-time Markov chain moves among a countable set of states at integer times, choosing its next state from probabilities that depend only on the current one, encoded compactly in a transition matrix.

Nájsť tému v PaperMindČoskoroFind papers & topics

Tools & resources

Stiahnuť snímky

Learn & explore

VideoČoskoro

Definition

A discrete-time Markov chain is a sequence of random states in a countable set such that the probability of the next state depends only on the current state, with these one-step probabilities collected in a transition matrix.

Scope

The topic covers transition matrices and the Chapman-Kolmogorov equations, the strong Markov property, classification of states into communicating classes and into transient, null-recurrent, and positive-recurrent, periodicity, hitting probabilities and expected hitting times computed by first-step analysis, and the recurrence dichotomy for random walks on the integer lattice.

Core questions

How does a transition matrix encode the dynamics of a chain over many steps?
How are states classified by their communication structure and their recurrence?
How are hitting probabilities and expected hitting times computed?
Which random walks return to their starting point with certainty and which escape to infinity?

Key concepts

transition matrix
Chapman-Kolmogorov equations
communicating classes
recurrence and transience
hitting times

Key theories

Strong Markov property: The Markov property continues to hold at suitable random times called stopping times, so a chain restarts afresh from its state at such a time, which is the key tool for analyzing returns, excursions, and hitting times.
Recurrence dichotomy: Each state is either recurrent, visited infinitely often with probability one, or transient, visited only finitely often; for simple symmetric random walk this depends on dimension, with recurrence in one and two dimensions and transience in three and higher.

Clinical relevance

Discrete-time Markov chains model board games, inventory and queueing systems, web navigation through the PageRank chain, and genetic and ecological succession; their hitting-time and recurrence theory answers practical questions about how long until a system reaches a target state or returns to a reference condition.

History

Markov introduced these chains in 1906, applying them to the sequence of vowels and consonants in a Pushkin poem to show the law of large numbers holds for dependent variables. Polya's 1921 analysis of random walks established the dimension-dependent recurrence dichotomy that bears his influence.

Key figures

Andrey Markov
George Polya
Joseph L. Doob

Seminal works

norris1997

Frequently asked questions

What is the difference between a recurrent and a transient state?: A recurrent state is one the chain is certain to return to, and so visits infinitely often, whereas a transient state is visited only finitely many times before the chain wanders away for good.
Why is simple random walk recurrent in low dimensions but not in high ones?: In one and two dimensions the walk returns to the origin with probability one, but from three dimensions onward there is enough room to escape, so the walk returns only finitely often and is transient; this is Polya's classical result.