Introduction to Probability

Chapter 11

Markov chains

Markov chains were first introduced in 1906 by Andrey Markov (of Markov’s inequality), with the goal of showing that the law of large numbers can apply to random variables that are not independent. To see where the Markov model comes from, start by considering an i.i.d. sequence of random variables X0, X1, ... , Xn, ... where we think of n as time. This is the setting we worked in throughout Chapter 10, but for modeling real-world phenomena, independence can be an excessively restrictive assumption; it means that the Xn provide absolutely no information about each other. At the other extreme, allowing arbitrary interactions between the Xn makes it very difficult to compute even basic things. A Markov chain is a sequence ...