1.5. STATIONARY DISTRIBUTIONS 11 If G has the property that every vertex has the same degree d, we call G d-regular. In this case 2|E| = d|V | and the uniform distribution π(y) = 1/|V | for every y V is stationary. A central goal of this chapter and of Chapter 4 is to prove a general yet precise version of the statement that “finite Markov chains converge to their stationary distributions.” Before we can analyze the time required to be close to stationar- ity, we must be sure that it is finite! In this section we show that, under mild restrictions, stationary distributions exist and are unique. Our strategy of building a candidate distribution, then verifying that it has the necessary properties, may seem cumbersome. However, the tools we construct here will be applied in many other places. In Section 4.3, we will show that irreducible and aperiodic chains do, in fact, converge to their stationary distributions in a precise sense. 1.5.2. Hitting and first return times. Throughout this section, we assume that the Markov chain (X0, X1, . . . ) under discussion has finite state space and transition matrix P . For x Ω, define the hitting time for x to be τx := min{t 0 : Xt = x}, the first time at which the chain visits state x. For situations where only a visit to x at a positive time will do, we also define τx + := min{t 1 : Xt = x}. When X0 = x, we call τx + the first return time. Lemma 1.13. For any states x and y of an irreducible chain, Ex(τy +) ∞. Proof. The definition of irreducibility implies that there exist an integer r 0 and a real ε 0 with the following property: for any states z, w Ω, there exists a j r with P j (z, w) ε. Thus for any value of Xt, the probability of hitting state y at a time between t and t + r is at least ε. Hence for k 0 we have Px{τy + kr} (1 ε)Px{τy + (k 1)r}. (1.17) Repeated application of (1.17) yields Px{τy + kr} (1 ε)k. (1.18) Recall that when Y is a non-negative integer-valued random variable, we have E(Y ) = t≥0 P{Y t}. Since Px{τy + t} is a decreasing function of t, (1.18) suffices to bound all terms of the corresponding expression for Ex(τy +): Ex(τy +) = t≥0 Px{τy + t} k≥0 rPx{τy + kr} r k≥0 (1 ε)k ∞.
Previous Page Next Page