Markov chains are simple probabilistic models which model sequences of related events through time. In a Markov chain, events at the present time depend on the previous event in the sequence. The example above shows a model of a dynamical system with two states A and B and the events are either moving between states A and B, or staying put.

More formally, a Markov chain is a model of any sequence of events with the following relationship

.

That is, the event that the sequence is in state at time is conditionally independent of all of its past states given its immediate past. This simple relationship between past and present provides a useful simplifying assumption to model, to a surprising degree of accuracy, many real world systems. These range from air particles diffusing through a room, to the migration patterns of insects, to the evolution of your genome, and even your web browser activity. Given their broad use in describing natural phenomena, it is very curious that Markov first invented the Markov chain to settle a dispute in Mathematical Theology, one in which the atheist Markov was pitted against the devoutly Orthodox Pavel Nekrasov.

In this debate Nekrasov asserted that for any sample drawn from a system with inter-dependent observations, there was no way to divine its long term behaviour and that only the ‘near’ independence of real world events made statistical analysis of phenomena such as crop yields or deaths even possible. Nekrasov went on to claim that human action was therefore inherently unknowable, necessitating free will.

Nekrasov’s assertion is the logical inverse of the famous statistical Law of Large Numbers which states that if observations are independent, the average of the observations will approach a unique, stable fixed point, the true mean of the distribution, as the number of observations increases. More formally, for a random variable ,

where are independent observations of , is the true mean of , is the sample average of the observations.

Markov refuted Nekrasov’s assertion by showing that his Markov chains also approached a stable fixed point as the number of observed events increases. This is true despite the events in the chain being dependent on the previous event. This fixed point is known as the stationary distribution of the chain. Markov went on to mockingly deride Nekrasov’s error (of denying the antecedent) in a published letter stating

The unique service of P. A. Nekrasov, in my opinion, is namely this: he brings out sharply his delusion, shared, I believe, by many, that independence is a necessary condition for the law of large numbers. This circumstance prompted me to explain, in a series of articles, that the law of large numbers and Laplace’s formula can apply also to dependent variables. In this way a construction of a highly general character was actually arrived at, which P. A. Nekrasov can not even dream about. I considered variables connected in a simple chain and from this came the idea of the possibility of extending the limit theorems of the calculus of probability also to a complex chain. Independence is not required for the application of these theorems…
– Correspondence between A.A. Markov and A.A. Chuprov

Markov went on to apply his methods to better understand Russian poetry, with limited success. Today, Markov chains are widely applied in a range of fields, most notably Markov Chain Monte Carlo methods and Hidden Markov Models which are both prominently used in the fields of Machine Learning and Artificial Intelligence.

Further Reading:

First Links in the Markov Chain – Brain Hayes
E. Senata, 1996, Markov and the Birth of Chain Dependence Theory
Shape: The Hidden Geometry of Absolutely Everything – Jordan Ellenburg
Introduction to Markov Chains – Devon Soni
An Argument Settled with Markov Chains – Randy Schwartz