Markov Chains for the Long Term
Robert P. Dobrow · 2016
In many cases, a Markov chain exhibits a long-term limiting behavior. The chain settles down to an equilibrium distribution, which is independent of its initial state. The long-term behavior of a Markov chain is related to how often states are visited. This chapter addresses the relationship between states and how reachable, or accessible, groups of states are from each other. A Markov chain is called ergodic if it is irreducible, aperiodic, and all states have finite expected return times. Some Markov chains exhibit a directional bias in their evolution. The chapter explains the property of time reversibility of the Markov chain. Many popular board games can be modeled as Markov chains. The children's game Chutes and Ladders is based on an ancient Indian game called Snakes and Ladders. The chapter proves the main limit theorems. Each proof is given after restating the corresponding theorem.