Probability: A Lively Introduction

In previous chapters we have dealt with sequences of independent random variables. However, many random systems evolving in time involve sequences of dependent random variables. Think of the outside weather temperature on successive days, or the price of IBM stock at the end of successive trading days.Many such systems have the property that the current state alone contains sufficient information to give the probability distribution of the next state. The probability model with this feature is called a Markov chain. The concepts of state and state transition are at the heart of Markov chain analysis. The line of thinking through the concepts of state and state transition is very useful to analyze many practical problems in applied probability.

Markov chains are named after the Russian mathematician Andrey A. Markov (1856–1922), who introduced the concept of the Markov chain in a 1906 publication. In a famous paper written in 1913, he used his probability model to analyze the frequencies with which vowels and consonants occur in Pushkin's novel Eugene Onegin. Markov showed empirically that adjacent letters in Pushkin's novel are not independent but obey his theory of dependent random variables. Markov's work helped launch the modern theory of stochastic processes (a stochastic process is a collection of random variables, indexed by an ordered time variable). The characteristic property of a Markov chain is that its memory goes back only to the most recent state. Knowledge of the current state only is sufficient to describe the future development of the process. A Markov model is the simplest model for random systems evolving in time when the successive states of the system are not independent. But this model is no exception to the rule that simple models are often the most useful models for analyzing practical problems. The theory of Markov chains has applications to a wide variety of fields, including biology, physics, engineering, operations research, and computer science. Markov chains are almost everywhere in science today. A similar method as used by Andrey Markov to study the alternation of vowels and consonants in Pushkin's novel helps identify genes in DNA. Markovian language models are nowadays used in speech recognition. In physics, Markov chains are used to simulate the macrobehavior of systems made up of many interacting particles.