Markov Chains

Andrei Andreevich Markov

Andrei Andreevich Markov (1856–1922) formulated the seminal concept in the field of probability later known as the Markov chain. Markov was an eminent Russian mathematician who served as a professor in the Academy of Sciences at the University of St. Petersburg. One of Markov's teachers was Pafnuty Chebyshev, a noted mathematician who formulated the famous inequality termed the Chebyschev inequality, which is extensively used in probability and statistics. Markov was the first person to provide a clear proof of the central limit theorem, a pivotal theorem in probability and statistics that indicates that the sum of a large number of independent random variables is asymptotically distributed as a normal distribution.

Markov was a well-trained mathematician who after 1900 emphasized inquiry in probability. After studying sequences of independent chance events, he became interested in sequences of mutually dependent events. This inquiry led to the creation of Markov chains.

Sequences of Chance Events

Markov chains are sequences of chance events. A series of flips of a fair coin is a typical sequence of chance events. Each coin flip has two possible outcomes: Either a head (H) appears or a tail (T) appears. With a fair coin, a head will appear with a probability (p) of 1/2 and a tail will appear with a probability of 1/2.

Successive coin flips are independent of each other in the sense that the probability of a head or a tail on the first flip does not affect the probability of a head or a tail on the second flip. In the case of the sequence HT, the p(HT) = p(H) × p(T) = 1/2 × 1/2 = 1/4. Many sequences of chance events are composed of independent chance events such as coin flips or dice throws. However, some sequences of chance events are not composed of independent chance events. Some sequences of chance events are composed of events whose occurrences are influenced by prior chance events. Markov chains are such sequences of chance events.

As an example of a sequence of chance events that involves interdependence of events, let us consider a sequence of events E1,E2,E3,E4 such that the probability of any of the events after E1 is a function of the prior event. Instead of interpreting the p(E1,E2,E3,E4) as the product of probabilities of independent events, p(E1,E2,E3,E4) is the product of an initial event probability and the conditional probabilities of successive events. From this perspective,

Such a sequence of events is a Markov chain. Let us consider a sequence of chance events E1,

Ej-2,…, E1), then the sequence of chance events is a Markov chain. For a more formal definition, if X1, X2, …, Xn are random variables and

...