Markov chain

A Markov chain is a stochastic process describing a sequence of possible events in which the probability of the next state depends only on the present state, i.e. it is "memoryless", where history is independent from the future. This is known as the Markov property.

A Markov chain is said to be regular if some power $P^k$ of the transition matrix $P$ has all positive entries. Equivalently, there is some $k>0$ for which every pair of states, there is a path of exactly $k$ steps.