Markov chain

A stochastic process that moves among states, with the probability of the next state determined by the current state rather than the full history.

Transition matrix: A matrix whose entries give the probabilities of moving between states in one step. Its rows or columns encode the chain’s one-step transition probabilities.
Stochastic process: A collection of random variables indexed by time or another parameter. A Markov chain is a stochastic process with a particular conditional-independence property.
PageRank: A link-analysis algorithm that ranks web pages using the stationary distribution of a random surfer’s movement. Its random-surfer model turns web links into transitions between page states.
Non-Markovian process: A stochastic process whose future can depend on its history beyond its current state. It violates the defining memoryless condition of a Markov chain.
Stationary distribution: A probability distribution unchanged by a stochastic process’s transition rule. It describes state probabilities that remain constant after each transition.
Markov property: The condition that a process’s future, given its present, is independent of its past. This memorylessness condition defines which stochastic processes qualify as Markov chains.
Conditional probability: The probability of an event given that another event has occurred. Transition probabilities condition the next state on the chain’s current state.
Hidden Markov model: A probabilistic model with hidden states that evolve as a Markov chain and generate observable outputs. It extends the chain to situations where states cannot be observed directly.
Renewal process: A process in which events recur after independent, identically distributed waiting times. Non-exponential waiting times can make event timing non-Markovian unless elapsed time is included in the state.
Ergodic Markov chain: A Markov chain whose states communicate and whose long-run averages converge to a unique stationary distribution. Ergodicity determines when long-run behavior becomes independent of the starting state.

Linked from 31 pages