In this problem, P is the transition matrix for an irreducible Markov process with period d. We are asked to find the number of communicating classes ...

0 downloads 68 Views 150KB Size

In this problem, P is the transition matrix for an irreducible Markov process with period d. We are asked to find the number of communicating classes and periods for P k . First note the following Lemma 0.1. Let d = HCF {a1 , a2 , . . . , an }, where the ai are positive integers. Write d = b1 a1 + · · · bn an P for bi ∈ Z. Put B = supi {|bi |} and let A = i ai . Then for all m > A2 B, we can write md = c1 a1 + c2 a2 + · · · + cn an with ci ∈ Z, ci ≥ 0. Proof. Suppose m > A2 B/d. Write m = qA + r with q ≥ AB/d and 0 ≤ r < A. Then X X X md = qAd + rd = qd( ai ) + r bi ai = (qd + rbi )ai . i

i

i

But qd ≥ AB ≥ r|bi | for each i. Hence, ci := qd + rbi ≥ 0 for each i. Let I be the state space for the Markov process. Recall that the period is the same for all x ∈ and it is by definition d = HCF {a | p(a) xx > 0}. (a)

As we go over an increasing sequence of finite subsets of elements in {a | pxx > 0}, the HCF of these subsets get smaller and smaller. Hence, d is actually the HCF of a finite set of ai in the set. Thus, with notation as in the lemma, for m > A2 B/d, (md) pxx ≥ (p(a1 ) )c1 (p(a2 ) )c2 · · · (p(an ) )cn > 0.

For n ∈ Z, denote by [n] its class in Z/d. For r ∈ Z/d, we denote by r0 an element of Z such that [r ] = r. For x ∈ I and r ∈ Z/d, let 0

Ir (x) = {y ∈ I | ∃n, p(n) xy > 0, n ≡ r

mod d}.

From the definition, it’s clear that if y ∈ Ir (x) and z ∈ Is (y), then z ∈ Ir+s (x). Proposition 0.2. Suppose y ∈ Ir (x). Then x ∈ I−r (y). (m)

Proof. We have pyx > 0 for some m by irreducibility. Thus, for some n such that [n] = r, we have (n+m) pxx > 0. But then, d|(n + m), and hence, [m] = −r. Proposition 0.3. If y, z ∈ Ir (x), then z ∈ I0 (y). Proof. Since x ∈ I−r (y) and z ∈ Ir (x), we have z ∈ I−r+r (y) = I0 (y). Proposition 0.4. For r 6= s ∈ Z/d, Ir (x) ∩ Is (x) = φ. Proof. Let y ∈ Ir (x) ∩ Is (x). Then x ∈ I−s (y). So x ∈ Ir−s (x). Thus for some n ∈ Z such that (n) [n] = r − s, we have pxx > 0. But then, d|n. So r − s = 0. By irreducibility, I = ∪r Ir (x), and we have just shown this is a disjoint union.

1

Proposition 0.5. Let y ∈ Ir (x). The for all m sufficiently large such that m ≡ r mod d, we have p(m) xy > 0. (n)

Proof. We have pxy > 0 for some n ≡ r mod d. Let m ≡ r mod d satisfy m > A2 B + n with (m−n) notation as in the previous lemma. Then (m − n)/d > A2 B/d. Hence, pxx > 0 and (m−n) (n) p(m) pxy > 0. xy ≥ pxx

(n)

In particular, if y ∈ I0 (x), then pxy > 0 for all n ∈ dZ, sufficiently large. This implies that (kn) pxy > 0 for n ∈ dZ sufficiently large. So all I0 (x) are all in the same communicating class for P k . Similarly, since Ij (x) = I0 (y) for any y ∈ Ij (x), we see that all of Ij (x) is in the same communicating class for any j. Let g = HCF {k, d}. Proposition 0.6. Ir (x) and Is (x) are in the same communicating class for P k if and only if r ≡ s mod g. Proof. Suppose they are in the same communicating class. Then there are y ∈ Ir (x) and z ∈ Is (x) (mk) such that pyz > 0 for some m. So then z ∈ I[mk] (y), and hence, z ∈ Ir+[mk] (x). This implies that r + [mk] = s. Hence, r0 − s0 = −mk + ad for some a, and hence, r ≡ s mod g. Conversely, suppose r ≡ s mod g and let y ∈ Ir (x), z ∈ Is (x). Then r0 = s0 + ag for some a. Thus, we have y ∈ I[ag] (z). We can write ag = ld + nk. So y ∈ I[nk] (z). Hence, for all m (m)

sufficiently large such that m ≡ nk mod d, we have pzy > 0. In particular, we can choose m of the ((n+hd)k) > 0. We can switch the role of z and y in this form m = nk + hdk for h large. But then, pzy argument, which allows us to conclude that z and y are in the same communicating class for P k . We conclude that there are g communicating classes. Now, I leave it to you to check that the period of P k is d/g.

2