Markov chains

Se basa en

Requisitos previos obligatorios, hasta el fondo: 42

Aprenderás a

• Model processes with transition matrices and compute n-step transition probabilities.
• Classify states as recurrent or transient and find stationary distributions.
• Prove convergence to equilibrium for irreducible aperiodic finite chains.

Definición

• A Markov chain is a sequence of random variables in which the conditional distribution of the next state, given the past, depends only on the current state.
• A probability distribution π (as a row vector) is stationary for transition matrix P if πP = π.
• A chain is irreducible if every state can be reached from every other state.

Teorema

• An irreducible Markov chain on a finite state space has a unique stationary distribution.
• If it is also aperiodic, the distribution at time n converges to the stationary distribution from any starting distribution.
• Pólya: simple random walk is recurrent on ℤ and ℤ² and transient on ℤ³.

Errores frecuentes

• Reading 'memoryless' as 'forgets everything'; it means the future depends on the past only through the present.

Conduce a

Descubrimientos opcionales

• Mathematical biology Stochastic models of populations and of genetic drift, such as the Wright–Fisher model, are Markov chains.
• Random structures: walks, percolation and random geometry Simple random walk on ℤᵈ returns to its start with probability 1 in dimensions 1 and 2 but not in dimension 3 (Pólya).
• ← Probability

Lecturas complementarias

• J. R. Norris, Markov Chains (1997)