Introduction to Probability, Second Edition, 2nd Edition

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 $X_0,X_1,\dots ,X_n,\dots$ 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 $X_n$ provide absolutely no information about each other. At the other extreme, allowing arbitrary interactions between the $X_n$ makes it very difficult to compute even basic things. A Markov chain is a sequence of r.v.s that ...