20 1. INTRODUCTION TO FINITE MARKOV CHAINS Notes Markov first studied the stochastic processes that came to be named after him in Markov (1906). See Basharin, Langville, and Naumov (2004) for the early history of Markov chains. The right-hand side of (1.1) does not depend on t. We take this as part of the definition of a Markov chain note that other authors sometimes regard this as a special case, which they call time homogeneous. (This simply means that the transition matrix is the same at each step of the chain. It is possible to give a more general definition in which the transition matrix depends on t. We will not consider such chains in this book.) Aldous and Fill (1999, Chapter 2, Proposition 4) present a version of the key computation for Proposition 1.14 which requires only that the initial distribution of the chain equals the distribution of the chain when it stops. We have essentially followed their proof. The standard approach to demonstrating that irreducible aperiodic Markov chains have unique stationary distributions is through the Perron-Frobenius theo- rem. See, for instance, Karlin and Taylor (1975) or Seneta (2006). See Feller (1968, Chapter XV) for the classification of states of Markov chains. Complements. The following lemma is needed for the proof of Proposition 1.7. We include a proof here for completeness. Lemma 1.27. If S ⊂ Z+ has gcd(S) = gS , then there is some integer mS such that for all m ≥ mS the product mgS can be written as a linear combination of elements of S with non-negative integer coeﬃcients. Proof. Step 1. Given S ⊂ Z+ nonempty, define gS as the smallest positive integer which is an integer combination of elements of S (the smallest positive element of the additive group generated by S). Then gS divides every element of S (otherwise, consider the remainder) and gS must divide gS , so gS = gS . Step 2. For any set S of positive integers, there is a finite subset F such that gcd(S) = gcd(F ). Indeed the non-increasing sequence gcd(S ∩ [1, n]) can strictly decrease only finitely many times, so there is a last time. Thus it suﬃces to prove the fact for finite subsets F of Z+ we start with sets of size 2 (size 1 is a tautology) and then prove the general case by induction on the size of F . Step 3. Let F = {a, b} ⊂ Z+ have gcd(F ) = g. Given m 0, write mg = ca+db for some integers c, d. Observe that c, d are not unique since mg = (c + kb)a + (d − ka)b for any k. Thus we can write mg = ca + db where 0 ≤ c b. If mg (b − 1)a − b, then we must have d ≥ 0 as well. Thus for F = {a, b} we can take mF = (ab − a − b)/g + 1. Step 4 (The induction step). Let F be a finite subset of Z+ with gcd(F ) = gF . Then for any a ∈ Z+ the definition of gcd yields that g := gcd({a}∪F ) = gcd(a, gF ). Suppose that n satisfies ng ≥ m{a,gF }g + mF gF . Then we can write ng − mF gF = ca + dgF for integers c, d ≥ 0. Therefore ng = ca + (d + mF )gF = ca + ∑ f∈F cf f for some integers cf ≥ 0 by the definition of mF . Thus we can take m{a}∪F = m{a,gF } + mF gF /g.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.