Res. Lett. Inf. Math. Sci. (2007) 11, 1-22 Available online at http://iims.massey.ac.nz/research/letters/ Coupling and Mixing Times in a Markov Chains Jeffrey J. Hunter I.I.M.S. Massey University, Auckland, New Zealand j.hunter@massey.ac.nz Abstract The derivation of the expected time to coupling in a Markov chain and its relation to the expected time to mixing (as introduced by the author in ?Mixing times with applications to perturbed Markov chains? Linear Algebra Appl. (417, 108-123 (2006)) are explored. The two-state cases and three-state cases are examined in detail. 1. Introduction Let P = [p ij ] be the transition matrix of a finite irreducible, discrete time Markov chain {X n }, (n ? 0), with state space S = {1, 2,?, m}. It is well known that such Markov chains have a unique stationary distribution {? j }, (1 ? j ? m), that, in the case of a regular (finite, irreducible and aperiodic) chain, is also the limiting distribution of the Markov chain ([4, Theorem 7.1.2]) . Let ?T = (? 1 , ? 2 , ... ,? m ) be the stationary probability vector of the Markov chain. Various measures have been proposed regarding the ?time to stationary? for a Markov chain, i.e. the number of trials, or steps, that the Markov chain makes until it can be regarded as operating under ?stationary conditions?. (See e.g. [1], [9]). The author considered ([3]) the concept of ?time to mixing? as a possible approach, along the following lines. Let Y be a random variable whose probability distribution is the stationary distribution {? j }. We shall say that the Markov chain {X n }, ?achieves ?mixing?, at time T = k, when X k = Y for the smallest such k ? 1. Thus, we first sample from the stationary distribution {? j } to determine a value of the random variable Y, say Y = j. We then observe the Markov chain, starting at a given state i and achieve ?mixing? at time T = n when X n = j for the first such n ? 1. i.e., conditional upon Y = j, T = min{n ?1 such that X n = j given that X 0 = i} = T ij , the first passage time from state i to state j, (or return to state j when i = j). In [3] we assumed that mixing cannot occur at the initial trial although we could have assumed a mixing time of T = 0 when X 0 = Y. We consider such a case later when we summarise the key results regarding the expected ?time to mixing? in Section 2. The main thrust of this paper is to explore the concept of ?coupling? of Markov chains as a procedure to provide a measure of the time to stationarity. We start a Markov chain {Y n }, with the same transition matrix P as for {X n }, operating under stationary conditions, so that the initial probability distribution for Y 0 is the stationary distribution {? j }. We start the Markov chain {X n } in an initial state i and allow each Markov chain 2 R.L.I.M.S. Vol. 11, April 2007 to evolve, independently, until time T = n when both chains {X n } and {Y n } reach the same state at this n-th trial. We call this the ?coupling time? since after time T each chain is coupled and evolves identically as the {Y n } Markov, with each chain having the same stationary distribution {? j }. In Section 3 we explore the derivation of the expected ?time to coupling?. In section 4 we compare the two concepts of ?time to stationarity? through a variety of special two-state and three-state cases. We show, in particular, that it is difficult to get general inequalities between the expected times to mixing starting in state i, ? i ,M , and the expected time to coupling starting in state i, ? i ,C . Further periodic Markov chains that give minimal expected times to mixing in general never achieve coupling. Since the expected times to mixing are in general easier to calculate than the expected times to coupling we recommend that as a first approximation such expected values be used as an indication as to how long a general Markov chain can take to achieve stationarity. We conclude the paper with some observations pertaining to the expected times to mixing and coupling in general finite Markov chains focussing, in particular, on the case of independent trials. 2. Mixing Times The irreducibility of the Markov chain ensures that the T ij are all proper random variables ([4, Theorem 5.3.6]), ensuring the finiteness of the ?mixing time? (a.s.). Further, under the finite state space restriction, all the moments of T ij are finite, ([5, Theorem 7.3.1]). Let m ij be the mean first passage time from state i to state j, i.e. m ij = E[T ij | X 0 = i] for all i, j ? S. (It is possible, in the presence of null states in the case of an infinite state space for m ii = + ?.) In [3] we showed that if ? i is the expected time to mixing starting at state i, then ? i = m ij ? j j=1 m ? . (2.1) We further showed that ? i = ?, a constant independent of i, the starting state and obtained various alternative expressions for ? using generalized inverses of I ? P, (where I is the identity matrix). In particular, if ?T = (? 1 ,? 2 ,...,? m ) and e T = (1,1,...,1) , we have the following general results initially derived in [3]. (For the properties of g- inverses of I ? P see [4], [5] and [6]). If G = [g ij ] is any g-inverse of I ? P, and ? = e? T, ? = [1? tr(G?) + tr(G)]e = ?e. (2.2) Further, if g j i = g jk k =1 m ? , then ? = 1+ (g jj j=1 m ? ? g ji ? j ). (2.3) Further, if for some g, Ge = ge, ? = 1 ? g + tr(G). (2.4) J.J. Hunter Coupling and Mixing Times in Markov Chains 3 In particular, ? = tr(Z) = 1 + tr(T). (2.5) where Z is Kemeny and Snell?s fundamental matrix Z = [I ? P ? ?] ?1 given initially in [8, Theorem 4.4.7] and [7]; and T is Meyer?s group inverse of I ? P, Z ? ? as given in [10, Theorem 3.3]. If we assume that mixing can occur initially when X 0 = Y, so that we consider ?hitting times? rather than ?return times? to any state, then the expected time to mixing, starting in state i, is ? M ,i = ? i ? 1 = ? ?1= ? M (= m ij ? j j?i m ? , since m ii = 1 ? i .) Thus from equations (2.2), (2.3), (2.4) and (2.5), using the same notation, ? M = (g jj j=1 m ? ? g ji ? j ) = tr(G) ? g = tr(Z ) ?1= tr(T ). (2.6) 3. Coupling Times Under the assumption that {X n } and {Y n } both have a finite state space S = {1,2, ?m}, Z n = (X n ,Y n ), (n ? 0), is a (two-dimensional) Markov chain with state space S ? S = {(i, j), 1 ? i ? m, 1 ? j ? m}. The chain is an absorbing chain with absorbing (coupling) states C = {(i, i), 1 ? i ? m} and transient states T = {(i, j), i ? j, 1 ? i ? m, 1 ? j ? m}. The transition probabilities, prior to coupling, are given by P{Z n+1 = (k, l) | Z n = (i, j) } = P{X n+1 = k, Y n +1 = l | X n = i, Y n = j} = P{X n+1 = k | X n = i}.P{Y n+1 = l | Y n = j} = p ik p jl . Once coupling occurs at time T = n, X n+k = Y n+k for all k ? 0. If Z 0 ?C, coupling of the two Markov chains is instantaneous and the coupling time T = 0. We define T ij,kl to be the first passage time from state ( i, j) to state (k, l). Observe that the time to coupling in state k, starting in state (i, j), (i ? j), is the first passage time T ij,kk to the absorbing state (k, k). Let T ij,C, be the first passage time from (i ,j), (i ? j) to the absorbing (coupling) states C. We define T ii,C = 0, (1 ? i ? m), consistent with the coupling occurring instantaneously if X 0 = Y 0 (in state i). Under the assumption that the embedded Markov chains, X n and Y n , are irreducible and aperiodic (i.e. regular) the transition matrix for the two dimensional Markov chain can be represented in the canonical form for an absorbing Markov chain, as P = I 0 R Q ? ? ? ? ? ? (3.1) where I is an m?m identity matrix, Q is an m(m-1)?m(m-1) matrix governing the transition probabilities within the transient states T, and R is an m(m-1)?m matrix 4 R.L.I.M.S. Vol. 11, April 2007 governing the transition probabilities from the transient states T to the absorbing (coupling) states C. Note that if the Markov chains, X n and Y n are periodic (period m) then mixing either occurs initially or never occurs! (If (X n ,Y n ) = (i, j) (i ? j) then it is impossible for (X n ,Y n ) = (k, k) for any k due to the identical cyclicity of each embedded chain. If the period of the chains is however less than m coupling may be possible. We restrict attention to embedded regular chains. Let the n-step first passage time matrix be F (n ) ? f ij ,kl (n ) ? ? ? ? , where f ij,kl (n ) ? P{T ij ,kl = n}. It is well known that for absorbing chains ([5], Theorem 6.2.1) that with the equivalent partitioning as given by (3.1), F (n ) = F 1 (n ) F 2 (n) F 3 (n ) F 4 (n) ? ? ? ? ? ? , then F 1 (1) = I,F 1 (n ) = 0, (n ? 2); F 2 (n ) = 0, (n ? 1); F 3 (n ) = Q n?1 R, (n ? 1); F 4 (n ) = Q[F 4 (n?1) ? F 4d (n?1) ]; F 4 (1) = Q , using the notation that if A = [a ij ] then A d = [? ij a ij ]. In particular, the probability that the first passage (coupling) from the starting state, (i, j), (i ? j) to the coupling states C occurs on the n-th trial (n ? 1), is given by f ij,C (n ) = P{T ij,C = n} = f ij ,kk (n) k=1 m ? so that f (n ) = ( fij ,C(n ) )(i, j )?T = F3(n)e = Qn?1Re, (3.2) where e is an m?1 column vector of 1?s, and f (n ) is an m(m-1)?1 column vector. Let the ?reaching probability? matrix be F ? f ij ,kl ? ? ? ? , where f ij,kl ? P{T ij ,kl < ?}. For a general absorbing Markov chain, (see [5], Theorem 6.3.1), with the equivalent partitioning as given by (3.1), F = F 1 F 2 F 3 F 4 ? ? ? ? ? ? = I 0 NR (N ? I )N d ?1 ? ? ? ? ? ? , where N = (I ? Q) -1 . Thus if f ij,kk is the probability that the coupling state ( k, k ) is ever reached from the initial state (i, j), (i ? j), then f ij,kk ? f ij ,kk (n) n=1 ? ? = P{T ij ,kk < ?} and F 3 ? f ij ,kk ? ? ? ? = NR. Now f ij,C ? f ij ,kk (n ) n=1 ? ? k=1 ? ? = P{T ij ,C < ?} is the probability of the coupling occurring in finite time, starting in state (i, j) (i ? j), so that f = ( fij ,C )(i, j )?T = F3e = NRe . Now, since P is a stochastic matrix, Pe = e, from Eqn. (3.1), (with appropriate dimensions), we deduce that Re + Qe = e, implying that Re = (I ? Q) e. Consequently f = NRe = (I ?Q) ?1 (I ?Q)e = e . (3.3) i.e. f ij,C = 1, implying that starting from any state (i, j), coupling will occur with probability one. J.J. Hunter Coupling and Mixing Times in Markov Chains 5 Let ? ij (C ) = E[T ij ,C ] be the expected time to coupling starting in state X 0 = i, Y 0 = j. By definition ? ij (C ) = nP[T ij ,C n=1 ? ? = n] = nf ij ,C (n) n=1 ? ? = nf ij,kk (n ) n=1 ? ? k=1 m ? . (3.4) Define ? ij ,kk = nf ij ,kk (n ) n=1 ? ? and K = (? ij,kk ) = ( nf ij,kk (n ) n=1 ? ? ) then K = nF 3 (n) n=1 ? ? . Using the expression F 3 (n ) , and noting that (I ?Q) ?1 exists (and hence has all eigenvalues less than 1 in modulus), from Exercise 4.5.1 of [4] we deduce that K = nQ n?1 n=1 ? ? R = (I ?Q) ?2 R = N 2 R . (3.5) Let ? ? (? ij (C ) ) , a column vector (of dimension m(m-1)?1) of the expected times to coupling. Since ? ij (C ) = ? ij ,kk k=1 m ? , we deduce from (3.5), and simplifying using (3.3), that ? = Ke = NNRe = Ne. (3.6) Since the states of the Markov chain {Y n } have at each trial the stationary distribution, and since, coupling occurs initially if i = j with T ii,C = 0, the expected time to coupling starting in state i, (1 ? i ? m) is? C ,i = ? j j=1 m ? E[T ij,C ] = ? j j?i ? ? ij (C ) . (3.7) To evaluate (3.7), we restrict attention to those entries in ? that start in state i. Let? 1 T = (? 12 (C ) ,...,? 1 j (C ) ,...,? 1m (C ) ),?,? i T = (? i1 (C ) ,...,? i ,i?1 (C ) ,? i ,i+1 (C ) ,...? im (C ) ), ?,? m T = (? m1 (C ) ,...,? m,m?1 (C ) ), and hence re-express ? as ? T = (? 1 T ,..., ? i T ,..., ? m ? ) . If we define ? i T = ? T [e 1 ,e 2 ,...,e i?1 ,e i+1 ,...,e m ] = (? 1 ,...,? i?1 ,? i+1 ,...? m ), i.e. a modification of ? T to yield a vector of dimension 1? (m -1) (with ? i removed at the i-th position from ? T) then, for 1 ? i ? m,? C ,i = ? i T? i . (3.8) There are some key observations, related to the structure of the Q matrix, that lead to simplification of the calculation of these expected values. First note that from Eqn. (3.6), ? = Ne = (I ?Q)?1e ? (I ?Q)? = e so that ? can be obtained by solving the set of linear equations (I ?Q)? = e. (3.9) In deriving the properties of the coupling process Z n = (X n ,Y n ) the original state space S consisting of m states was expanded to S ? S, a state space consisting of m 2 states. The Q-matrix is of dimension m(m-1)?m(m-1) and governs the transitions within the m(m-1) transient states. However, if we look carefully at this matrix we observe some symmetry. In particular, suppose we look at the sub-matrix of one-step transition probabilities governing transitions between the states (i, j) and (j, i) (i ? j). Observe the symmetry as follows 6 R.L.I.M.S. Vol. 11, April 2007 (i, j) ( j,i) (i, j) ( j,i) p ii p jj p ij p ji p ji p ij p jj p ii ? ? ? ? ? ? . Note also that the transition probabilities from (i, j) to the other transient states have some symmetrical reciprocity, i.e. for i ? j and r ? s, P[(X n+1 ,Y n+1 ) = (r, s) | (X n ,Y n ) = (i, j)] = p ir p js = P[(X n+1 ,Y n+1 ) = (s, r) | (X n ,Y n ) = (j, i)]. Further, the one step transition to any coupling state (k, k) has the same probability from either (i, j) or (j, i) i.e. P[(X n+1 ,Y n+1 ) = (k, k) | (X n ,Y n ) = (i, j)] = p ik p jk = P[(X n+1 ,Y n+1 ) = (k, k) | (X n ,Y n ) = (j, i)]. What this implies is that by appropriately labelling the states in successive symmetrical pairs, each even numbered row of Q has the same probabilities, but interchanged in pairs, as the previous odd numbered row. Furthermore these pairs of rows have identical probabilities in the same place in the R matrix. The nett effect of this observation is that instead of inverting the m(m-1) dimensional matrix N, or solving the linear equations (3.9), we need only solve the equivalent of m(m-1)/2 equations. We illustrate this further in the m = 3 case. 4. Special cases Example 4.1a. Two-state Markov chains (Mixing) Let P = p 11 p 12 p 21 p 22 ? ? ? ? ? ? ? ? = 1? a a b 1? b ? ? ? ? ? ? , (0 < a ? 1, 0 < b ? 1), be the transition matrix of a two-state Markov chain with state space S = {1, 2}. Let d = 1 ? a ? b so that 1 ? d = a + b. If ? 1? d < 1, the Markov chain is irreducible with a unique stationary distribution given by ? 1 = b a + b , ? 2 = a a + b . If ? 1< d < 1, the Markov chain is regular and this stationary distribution is in fact the limiting distribution. If d = ? 1 the Markov chain is irreducible periodic, period 2. The expected time to mixing, ? M = 1 1? d = 1 a + b . From [3], for all two-state irreducible Markov chains, ? M ? 0.5 with the minimum value of ? M = 0.5 occurring when d = ? 1, (a = 1, b = 1) in which case the Markov chain is periodic, period 2. Arbitrarily large values of ? M occur as d? 1, (when both a ? 0 and J.J. Hunter Coupling and Mixing Times in Markov Chains 7 b? 0), when the chain is approaching the situation when the chain is close to being reducible with both states absorbing. Example 4.1b. Two-state Markov chains (Coupling) With the same transition matrix as given in Example 4.1a, and the notation of Section 3, observe that (1,2) (2,1) Q = (1,2) (2,1) p 11 p 22 p 12 p 21 p 21 p 12 p 22 p 11 ? ? ? ? ? ? = (1? a)(1? b) ab ab (1? a)(1? b) ? ? ? ? ? ? . Now Eqn. (3.9) (I ?Q)? = e can be written as 1? (1? a)(1? b) ?ab ?ab 1? (1? a)(1? b) ? ? ? ? ? ? ? 12 (C )? 21 (C ) ? ? ? ? ? ? = 1 1 ? ? ? ? ? ? . This can either be solved by taking the inverse of (I ? Q), N, or solving the linear equations to give N = 1 (a + b)(a + b ? 2ab) 1? (1? a)(1? b) ab ab 1? (1? a)(1? b) ? ? ? ? ? ? ? ? 12 (C )? 21 (C ) ? ? ? ? ? ? = 1 (a + b ? 2ab) 1 1 ? ? ? ? ? ? . Now ? C ,1 = ? 2 ? 21 (C ) = a (a + b)(a + b ? 2ab) , and ? C ,2 = ? 1 ? 12 (C ) = b (a + b)(a + b ? 2ab) . Thus the expected times to coupling are state dependent with? C ,1 < ? C ,2 ? a < b , ? C ,1 = ? C ,2 ? a = b , ? C ,1 > ? C ,2 ? a > b ;? C ,1 < ? M ? a < 1 2 , ? C ,1 = ? M ? a = 1 2 , ? C ,1 > ? M ? a > 1 2 ;? C ,2 < ? M ? b < 1 2 , ? C ,2 = ? M ? b = 1 2 , ? C ,2 > ? M ? b > 1 2 . Figure 1 gives regions where different inequalities exist between the three different expected values. As can be seen every possible inequality arrangement can be achieved somewhere in the region (0,1]?(0,1], with selected equalities occurring on the boundaries where a = 1/2, b = 1/2 and a = b. This leads to the observation that we cannot determine any universal inequalities for all a and b. 8 R.L.I.M.S. Vol. 11, April 2007 Figure 1: Two state MC - Inequalities between expected mixing and coupling times Example 4.2a. Three-state Markov chains (Mixing) Let P = p 11 p 12 p 13 p 21 p 22 p 23 p 31 p 32 p 33 ? ? ? ? ? ? ? ? ? ? = 1? b ? c b c d 1? d ? f f g h 1? g ? h ? ? ? ? ? ? ? ? ? ? be the transition matrix of a Markov chain with state space S = {1, 2, 3}. Note that 0 < b + c ? 1, 0 < d + f ? 1 and 0 < g + h ? 1. Let ? 1 ? p 23 p 31 + p 21 p 32 + p 21 p 31 = fg + dh + dg, ? 2 ? p 31 p 12 + p 32 p 13 + p 32 p 12 = gb + hc + hb, ? 3 ? p 12 p 23 + p 13 p 21 + p 13 p 23 = bf + cd + cf,? ? ? 1 + ? 2 + ? 3 = fg + dh + dg + gb + hc + hb + bf + cd + cf. The Markov chain, with the above transition matrix, is irreducible (and hence a stationary distribution exists) if and only if ? 1 > 0, ? 2 > 0, ? 3 > 0. It is easily shown that the stationary probability vector is (? 1 ,? 2 , ? 3 ) = 1 ? (? 1 ,? 2 ,? 3 ) , Define ? ? p 12 + p 13 + p 21 + p 23 + p 31 + p 32 = b + c + d + f + g + h. It can verified, from [3] using the results for ?, that for all three-state MC?s,? M = ? ? . (4.1) The following special cases were explored in detail in [3]. b 1 1/2 0 0 1/2 1 a ? C ,1 < ? M < ? C ,2 ? C,2 < ? M < ? C ,1 ? M < ? C ,1 < ? C ,2? C ,2 < ? C ,1 < ? M ? C ,1 < ? C ,2 < ? M ? M < ? C ,2 < ? C ,1 J.J. Hunter Coupling and Mixing Times in Markov Chains 9 Case 1: ?Minimal period 3? If p 12 = p 23 = p 31 =1 i.e. b = f = g= 1, the Markov chain is periodic, period 3, with transitions cycling from 1 ? 2 ? 3 ? 1 ... and transition matrix P = 0 1 0 0 0 1 1 0 0 ? ? ? ? ? ? ? ? ? ? . Note that? 1 = ? 2 = ? 3 = 1, ? = 3, implying ?T = (1/3, 1/3. 1/3). Further ? = 3, implying from (4.1) that ? M = 1, the smallest possible amongst all 3-state Markov chains. Case 2: ?Period 2? If p 12 = p 32 = 1 and p 22 = 0, i.e. b = 1, d + f = 1, h = 1, the Markov chain is periodic, period 2 (with transitions alternating between the states {1, 3} and {2}), and transition matrix P = 0 1 0 d 0 f 0 1 0 ? ? ? ? ? ? ? ? ? ? . Then ? 1 = d, ? 2 = 1, ? 3 = f, ? = 2, implying ? T = (d 2,1 2, f 2). Further ? = 3, and hence from (4.1), ? M = 1.5. Case 3: ?Constant movement? If p 11 = p 22 = p 33 = 0, i.e. b + c = 1, d + f = 1, g + h = 1, then at each step the chain does not remain at the state but moves to one of the other states. The Markov chain is irreducible, and regular if 0 < b < 1, 0 < f < 1, 0 < g < 1. The transition matrix is P = 0 b 1? b 1? f 0 f g 1? g 0 ? ? ? ? ? ? ? ? ? ? . Now ? 1 = 1 ? f(1 ? g), ? 2 = 1 ? g(1 ? b), ? 3 = 1 ? b(1 ? f), implying that? = 3 ? f(1 ? g) ? g(1 ? b) ? b(1 ? f). Further ? = 3, and hence, from (4.1),? M = 3 3? b(1? f ) ? f (1? g) ? g(1? b) = 3 3? p 12 p 21 ? p 23 p 32 ? p 31 p 13 . In [3] we showed 1 ? ? M ? 1.5. The minimal value of 1 occurs when b = f = g = 1, and this case reduces to the ?period 3? Case 1 above. Further when b = f = g = 0 this case again reduces to a periodic, ?period 3? chain but with transitions 1 ? 3 ? 2 ? 1 .... . The maximal value of 1.5 occurs when any pair of (b, f, g) take the values 0 and 1, say b = 1, g = 0, when this case reduces to the ?period 2? Case 2 above. For the regular case 1 < ? M < 1.5. 10 R.L.I.M.S. Vol. 11, April 2007 Case 4: ?Independent? Suppose p ij = p j for all i, j implying that the Markov chain is equivalent to independent trials on the state space S = {1, 2, 3}. Now ? 1 = p 1 , ? 2 = p 2 , ? 3 = p 3 , so that ? = 1. Also? = 2, implying ? M = 2. Case 5: ?Cyclic drift? Let p 13 = p 21 = p 32 = 0, i.e. c = d = h = 0, with 0 < b < 1, 0 < f < 1, 0 < g < 1, implying that the Markov chain is regular with transition matrix P = 1? b b 0 0 1? f f g 0 1? g ? ? ? ? ? ? ? ? ? ? . At each transition the chain either remains in the same state i or moves to state i + 1 (or 1, if i = 3). Now ? 1 = fg, ? 2 = gb, ? 3 = bf so that ? = bf + fg + gb. Also ? = b + f + g. Note that 0 < ? < 3 and 0 < ? < 3 implying ? M = b + f + g bf + fg + gb = p 12 + p 23 + p 21 p 12 p 23 + p 23 p 21 + p 21 p 12 . When b + f + g ? 3 then bf + fg + gb ? 3 and ? M ? 1 (as in Case 1). When b + f + g ? 0 then bf + fg + gb ? 0, but the behaviour of ? M depends upon the rates of convergence and can be large. In this situation the Markov chain resides for a large number of transitions in each state so that there is little movement implying that the mixing time can become excessively large. Case 6: ?Constant probability state selection? Let P = 1 ? a a 2 a 2 b 2 1 ? b b 2 c 2 c 2 1 ? c ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? , where 0 < a < 1, 0 < b < 1, 0 < c < 1. The chain is regular with ? 1 = 3bc/4, ? 2 = 3ac/4, ? 3 = 3ab/4 so that? = 3(bc + ca + ab)/4. Also ? = a + b + c, leading, from (4.1), to ? M = 4(a + b + c) 3(bc + ca + ab) . With a = b = c = e, ? M = 4 3? so that 4 3 < ? M < ?. The lower bound is approached as e ? 1 (with the Markov chain approaching the special case of b = f = g = 1/2 as in Case 3). In [3] we showed that for all 3-state irreducible Markov chains ? M ? 1, consistent with our observations above. J.J. Hunter Coupling and Mixing Times in Markov Chains 11 Example 4.2b. Three-state Markov chains (Coupling) The key to achieving some symmetry in the Q matrix is to take the transient states in a string of ordered pairs. For example if T = {(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)} then Q can be displayed as Q = p 11 p 22 p 12 p 21 p 11 p 23 p 13 p 21 p 12 p 23 p 13 p 22 p 12 p 21 p 11 p 22 p 13 p 21 p 11 p 23 p 13 p 22 p 12 p 23 p 11 p 32 p 12 p 31 p 11 p 33 p 13 p 31 p 12 p 33 p 13 p 32 p 12 p 31 p 11 p 32 p 13 p 31 p 11 p 33 p 13 p 32 p 12 p 33 p 21 p 32 p 22 p 31 p 21 p 33 p 23 p 31 p 22 p 33 p 23 p 32 p 22 p 31 p 21 p 32 p 23 p 31 p 21 p 33 p 23 p 32 p 22 p 33 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? . Let ?? = (? 12 (C ) ,? 21 (C ) ,? 13 (C ) ,? 31 (C ) ,? 23 (C ) ,? 32 (C ) ) then the linear equations (3.9) can be expressed as 1? p 11 p 22 ?p 12 p 21 ? p 11 p 23 ? p 13 p 21 ? p 12 p 23 ? p 13 p 22 ? p 12 p 21 1? p 11 p 22 ? p 13 p 21 ? p 11 p 23 ? p 13 p 22 ? p 12 p 23 ? p 11 p 32 ? p 12 p 31 1? p 11 p 33 ? p 13 p 31 ? p 12 p 33 ? p 13 p 32 ? p 12 p 31 ? p 11 p 32 ? p 13 p 31 1? p 11 p 33 ? p 13 p 32 ? p 12 p 33 ? p 21 p 32 ? p 22 p 31 ? p 21 p 33 ? p 23 p 31 1? p 22 p 33 ?p 23 p 32 ? p 22 p 31 ? p 21 p 32 ? p 23 p 31 ? p 21 p 33 ? p 23 p 32 1? p 22 p 33 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 21 (C )? 13 (C )? 31 (C )? 23 (C )? 32 (C ) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1 1 1 1 1 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? . (4.1) This matrix equation (4.1) gives rise to 6 linear equations in 6 unknowns. Rather than attempt to invert the 6 ? 6 matrix (I ? Q) to obtain N, there is an easier way to solve for the unknowns. The symmetry of I ? Q suggests producing another set of three equations by adding each successive pair of equations and a further set of three equations by subtracting the 2 nd from the 1 st , the 4 th from the 3 rd and the 6 th from the 5 th equation. Let? 12 (C ) +? 21 (C ) = ? 1 , ? 13 (C ) +? 31 (C ) = ? 2 , ? 23 (C ) +? 32 (C ) = ? 3 and? 12 (C ) ?? 21 (C ) = ? 1 , ? 13 (C ) ?? 31 (C ) = ? 2 , ? 23 (C ) ?? 32 (C ) = ? 3 . With these definitions the six linear equations (4.1) are replaced by two sets of Equations (4.2) and (4.3) below: 1? p 11 p 22 ? p 12 p 21 ? p 11 p 23 ? p 13 p 21 ? p 12 p 23 ? p 13 p 22 ? p 11 p 32 ? p 12 p 31 1? p 11 p 33 ? p 13 p 31 ? p 12 p 33 ? p 13 p 32 ?p 21 p 32 ? p 22 p 31 ?p 21 p 33 ? p 23 p 31 1? p 22 p 33 ? p 23 p 32 ? ? ? ? ? ? ? ? ? ? ? 1? 2? 3 ? ? ? ? ? ? ? ? ? ? = 2 2 2 ? ? ? ? ? ? ? ? ? ? , (4.2) 12 R.L.I.M.S. Vol. 11, April 2007 1? p 11 p 22 + p 12 p 21 ? p 11 p 23 + p 13 p 21 ? p 12 p 23 + p 13 p 22 ? p 11 p 32 + p 12 p 31 1? p 11 p 33 + p 13 p 31 ? p 12 p 33 + p 13 p 32 ?p 21 p 32 + p 22 p 31 ?p 21 p 33 + p 23 p 31 1? p 22 p 33 + p 23 p 32 ? ? ? ? ? ? ? ? ? ? ? 1? 2? 3 ? ? ? ? ? ? ? ? ? ? = 0 0 0 ? ? ? ? ? ? ? ? ? ? . (4.3) These equations can be expressed in matrix form as A? = 2e, and B? = 0. Using Maple (with the p ij elements replaced by the simplified notation of the second expression for P as displayed in Example 4.2a) it can be shown that det(B ) = ?(? ? ?). Note that, by the irreducibility of the initial Markov chain, ? > 0, and since coupling does not occur for a periodic Markov chain, we know that ? M > 1 (cf. Case1 of Example 4.2a) implying that ? > ? and hence det(B) ? 0. Thus B is non-singular and B -1 exists. From (4.3), we conclude that ? = 0. This implies that ? 12 (C ) =? 21 (C ) , ? 13 (C ) =? 31 (C ) , ? 23 (C ) =? 32 (C ) , and consequently 2? 12 (C ) = ? 1 , 2? 13 (C ) = ? 2 , 2? 23 (C ) = ? 3 . If we define ? (C )T = (? 12 (C ) ,? 13 (C ) ,? 23 (C ) ) then, from (4.2), 1? p 11 p 22 ? p 12 p 21 ? p 11 p 23 ? p 13 p 21 ? p 12 p 23 ? p 13 p 22 ? p 11 p 32 ? p 12 p 31 1? p 11 p 33 ? p 13 p 31 ? p 12 p 33 ? p 13 p 32 ?p 21 p 32 ? p 22 p 31 ?p 21 p 33 ? p 23 p 31 1? p 22 p 33 ? p 23 p 32 ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = A? (C) = e . (4.4) The solution of the set of equations (4.4) can be effected but, even with Maple, we have been unable to find compact expressions for all possible parameter values. We can use MatLab to calculate values for the expected times. Note however that the elements of ? (C) are subsidiary results in that we are interested in expressions for the elements of ? (C)T = (? C ,1 ,? C ,2 ,? C ,3 ) . Note from (3.8) that ? C ,i = ? i T? i implying? C ,1 = ? 2 ? 12 (C ) + ? 3 ? 13 (C ) , ? C ,2 = ? 1 ? 21 (C ) + ? 3 ? 23 (C ) , ? C ,3 = ? 1 ? 31 (C ) + ? 2 ? 32 (C ) . (4.5) Thus ? (C) = D? (C ) where D = ? 2 ? 3 0? 1 0 ? 3 0 ? 1 ? 2 ? ? ? ? ? ? ? ? ? ? , or that ? (C ) = D?1?(C) implying AD ?1? (C) = e where D ?1 = 1 2? 1 ? 2 ? 3 ? 1 ? 3 ? 2 ? 3 ?? 3 2? 1 ? 2 ?? 2 2 ? 2 ? 3 ?? 1 2 ? 1 ? 2 ? 1 ? 3 ? ? ? ? ? ? ? ? ? ? = 1 2 1 ? 2 1 ? 1 ?? 3 ? 1 ? 2 1 ? 3 ?? 2 ? 1 ? 3 1 ? 1 ?? 1 ? 2 ? 3 1 ? 3 1 ? 2 ? ? ? ? ? ? ? ? ? ? . J.J. Hunter Coupling and Mixing Times in Markov Chains 13 In this situation, ? i = ? i /?, so that substituting in D and D -1 , yields? (C) = DA-1e = 1 ? ? 2 ? 3 0 ? 1 0 ? 3 0 ? 1 ? 2 ? ? ? ? ? ? ? ? ? ? A -1 e = 1 ? ? 2 ? 3 0 ? 1 0 ? 3 0 ? 1 ? 2 ? ? ? ? ? ? ? ? ? ? 1? p 11 p 22 ? p 12 p 21 ?p 11 p 23 ? p 13 p 21 ? p 12 p 23 ? p 13 p 22 ? p 11 p 32 ? p 12 p 31 1? p 11 p 33 ? p 13 p 31 ?p 12 p 33 ? p 13 p 32 ? p 21 p 32 ? p 22 p 31 ? p 21 p 33 ? p 23 p 31 1? p 22 p 33 ? p 23 p 32 ? ? ? ? ? ? ? ? ? ? ?1 1 1 1 ? ? ? ? ? ? ? ? ? ? . Alternatively, try to solve for ? (C) directly from the linear equations AD?1? (C) = e : 1 ? p 11 p 22 ? p 12 p 21 ? p 11 p 23 ? p 13 p 21 ? p 12 p 23 ? p 13 p 22 ? p 11 p 32 ? p 12 p 31 1 ? p 11 p 33 ? p 13 p 31 ? p 12 p 33 ? p 13 p 32 ? p 21 p 32 ? p 22 p 31 ? p 21 p 33 ? p 23 p 31 1 ? p 22 p 33 ? p 23 p 32 ? ? ? ? ? ? ? ? ? ? ? 1 ? 3 ? 2 ? 3 ? ? 3 2 ? 1 ? 2 ? ? 2 2 ? 2 ? 3 ? ? 1 2 ? 1 ? 2 ? 1 ? 3 ? ? ? ? ? ? ? ? ? ? ? C,1? C,2? C,3 ? ? ? ? ? ? ? ? ? ? = 2 ? 1 ? 2 ? 3 ? e. Case 1: ?Minimal period 3? with P = 0 1 0 0 0 1 1 0 0 ? ? ? ? ? ? ? ? ? ? . Formal substitution in Eqn. (4.4) leads to 1 0 ?1 ?1 1 0 0 ?1 1 ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = e . This is an inconsistent set of equations with no solution. This is however consistent with the observation that coupling of periodic chains either occurs initially or never occurs. Case 2: ?Period 2? with P = 0 1 0 d 0 f 0 1 0 ? ? ? ? ? ? ? ? ? ? , (d + f = 1). Eqn. (4.4) yield 1? d 0 ?(1? d) 0 1 0 ?d 0 d ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = e , implying ? 13 (C ) = 1 and ? 12 (C ) =? 23 (C ) (= ?). There are no finite solutions, consistent with the observation that the periodicity implies that coupling either occurs initially or never occurs. A key observation is that we will not see any minimal expected time to coupling in the presence of periodicities, as was the case for mixing times. 14 R.L.I.M.S. Vol. 11, April 2007 Case 3: ?Constant movement? with p 11 = p 22 = p 33 = 0. The transition matrix P = 0 p 12 p 13 p 21 0 p 23 p 31 p 32 0 ? ? ? ? ? ? ? ? ? ? = 0 b 1? b 1? f 0 f g 1? g 0 ? ? ? ? ? ? ? ? ? ? . Eqn. (4.4) yields A? (C) = 1 ? p12 p21 ? p13p21 ? p12 p23? p 12 p 31 1 ? p 13 p 31 ? p 13 p 32 ? p 21 p 32 ? p 23 p 31 1 ? p 23 p 32 ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = e . If we define ? 2 = p 12 p 21 + p 23 p 32 + p 31 p 13 , ? 3 = p 12 p 23 p 31 ? p 13 p 21 p 32 , then A ?1 = 1 1?? 2 ?? 3 2 1? p 23 p 32 ? p 31 p 13 p 13 p 21 + p 23 ? 3 p 12 p 23 ? p 13 ? 3 p 12 p 31 ? p 32 ? 3 1? p 12 p 21 ? p 23 p 32 p 13 p 32 + p 12 ? 3 p 21 p 32 + p 31 ? 3 p 23 p 31 ? p 21 ? 3 1? p 13 p 31 ? p 21 p 12 ? ? ? ? ? ? ? ? ? ? . This leads to? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = 1 1?? 2 ?? 3 2 1+ p 13 (p 21 ? p 31 ) + p 23 (p 12 ? p 32 ) + (p 23 ? p 13 )? 3 1+ p 12 (p 31 ? p 21 ) + p 32 (p 13 ? p 23 ) + (p 12 ? p 32 )? 3 1+ p 21 (p 32 ? p 12 ) + p 31 (p 23 ? p 13 ) + (p 31 ? p 21 )? 3 ? ? ? ? ? ? ? ? ? ? . Finally, using Eqn. (4.5) and noting that ? 1 = 1? p 23 p 32 ,? 2 = 1? p 31 p 13 ,? 3 = 1? p 12 p 21 and ? = 3?? 2 to obtain expressions for ? C,i .? C ,1? C ,2? C ,3 ? ? ? ? ? ? ? ? ? ? = 1 (3?? 2 )(1?? 2 ?? 3 2 ) ? 2 + ? 3 + (? 2 p 13 ? ? 3 p 12 )(p 21 ? p 31 ) + (? 2 p 23 + ? 3 ? 3 )(p 12 ? p 32 ) + (? 3 p 32 ? ? 2 ? 3 )(p 13 ? p 23 ) ? 1 + ? 3 + (? 1 p 13 ? ? 3 ? 3 )(p 21 ? p 31 ) + (? 1 p 23 ? ? 3 p 21 )(p 12 ? p 32 ) + (? 1 ? 3 + ? 3 p 31 )(p 23 ? p 13 ) ? 1 + ? 2 + (? 1 p 12 + ? 2 ? 3 )(p 31 ? p 21 ) + (? 1 p 32 ? ? 2 p 31 )(p 13 ? p 23 ) + (? 2 p 21 ? ? 1 ? 3 )(p 32 ? p 12 ) ? ? ? ? ? ? ? ? ? ? Computation of ? C,i , for all values of the parameters, shows that 1 ? ? M ? 1.5 < 2.6667 ? min 1? i?3 ? C ,i < ? . Thus, in all situations for this case, the expected time to mixing is less than the expected time to coupling from any state. Simple regions, in terms of the parameters (transition probabilities, when inequalities between the ? C,i and ? C,j (i ? j) are difficult to determine. We can show, for example, that? C ,1 < ? C ,2 ? 0 < (? 1 ? ? 2 ){p 12 (p 31 + p 23 ) + p 21 (p 13 + p 32 ) +? 3 (p 23 ? p 13 )} + ? 3 {p 12 p 32 + p 21 p 31 +? 3 (p 23 ? p 12 )}. Note that p 12 (p 31 + p 23 ) + p 21 (p 13 + p 32 ) +? 3 (p 23 ? p 13 ) > 0 and ? 3 > 0. Sufficient conditions for ? C ,1 < ? C ,2 can be derived from the above, in terms of ? 1 ? ? 2 , ? 3 and p 23 ? p 12 . There is no simple region in terms of the independent parameters p 12 , p 23 , p 31 . Similar conditions can be deduced for other inequalities between the ? C,i . J.J. Hunter Coupling and Mixing Times in Markov Chains 15 Case 4: ?Independent trials? with P = p 1 p 2 p 3 p 1 p 2 p 3 p 1 p 2 p 3 ? ? ? ? ? ? ? ? ? ? . In this situation Eqns. (4.4) become 1? 2p 1 p 2 ?2p 1 p 3 ?2p 2 p 3 ?2p 1 p 2 1? 2p 1 p 3 ?2p 2 p 3 ?2p 1 p 2 ?2p 1 p 3 1? 2p 2 p 3 ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = e . These equations yield ? 12 (C ) =? 13 (C ) =? 23 (C ) = 1 (1? 2p 1 p 2 ? 2p 1 p 3 ? 2p 2 p 3 ) . Further ? 1 = p 1 , ? 2 = p 2 , ? 3 = p 3 , implying ? = 1 and p 1 = p 1 , p 2 = p 2 , p 3 = p 3 . Thus, from Eqn. (4.5),? C ,1 = p 2 + p 3 1? 2p 1 p 2 ? 2p 1 p 3 ? 2p 2 p 3 , ? C ,2 = p 1 + p 3 1? 2p 1 p 2 ? 2p 1 p 3 ? 2p 2 p 3 ,? C ,3 = p 1 + p 2 1? 2p 1 p 2 ? 2p 1 p 3 ? 2p 2 p 3 . Note that ? C ,i < ? C , j if and only if p j < p i for all i ? j. When p 1 = p 2 = p 3 = 1 3 it is easily seen that for all i = 1, 2, 3, ? C ,i = 2 = ? M . It can be shown that for all possible parameter values 0 < p 1 , p 2 , p 3 , < 1 with p 1 + p 2 + p 3 = 1, that 0 < ? C ,i < 2.22474 with the maximal value of ? C ,i occurring at p 1 = 0.18350 , p 2 = p 3 = 0.40825 (and similarly for the other ? C ,i . ) Of interest is, when does ? C ,i exceed 2, the value of ? M ? For each i, the region where? C ,i = 2 is an ellipse. Let q 1 = p 1 + p 2 , q 2 = p 1 ? p 2 . Consider the values in the ( p 1 , p 2 )- plane (which lie in the interior of the region bounded by p 1 = 0, p 2 = 0 and p 1 + p 2 = 1. For i = 1, the ellipse is q 1 + 1 4 ? ? ? ? ? ? 2 + 3 q 2 ? 7 12 ? ? ? ? ? ? 2 = 1 2 3 ? ? ? ? ? ? 2 , i.e centred on p 1 = 1 6 = 0.1667, p 2 = 5 12 = 0.4167. For i = 2, the ellipse is q 1 ? 1 4 ? ? ? ? ? ? 2 + 3 q 2 ? 7 12 ? ? ? ? ? ? 2 = 1 2 3 ? ? ? ? ? ? 2 , i.e. centred on p 1 = 5 12 = 0.4167, p 2 = 1 6 = 0.1667. For i = 3, the ellipse is q 1 2 + 3 q 2 ? 5 6 ? ? ? ? ? ? 2 = 1 2 3 ? ? ? ? ? ? 2 , i.e centred on p 1 = 5 12 = 0.4167, p 2 = 5 12 = 0.4167. 16 R.L.I.M.S. Vol. 11, April 2007 Figure 2:Regions where expected coupling times exceed expected mixing times, Case 4 Case 5: Cyclic drift p 13 = p 21 = p 32 = 0 with P = p 11 p 12 0 0 p 22 p 23 p 31 0 p 33 ? ? ? ? ? ? ? ? ? ? = 1? b b 0 0 1? f f g 0 1? g ? ? ? ? ? ? ? ? ? ? . Eqn. (4.4) yields 1? p 11 p 22 ? p 11 p 23 ? p 12 p 23 ? p 12 p 31 1? p 11 p 33 ? p 12 p 33 ? p 22 p 31 ?p 23 p 31 1? p 22 p 33 ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = e . Define ? 1 = p 11 + p 22 + p 33 , ? 2 = p 11 p 22 + p 22 p 33 + p 33 p 11 , ? 3 = p 11 p 22 p 33 ? p 12 p 23 p 31 , then 0 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17 0.18 0.19 0.2 0.21 0.22 0.23 0.24 0.25 0.26 0.27 0.28 0.29 0.3 0.31 0.32 0.33 0.34 0.35 0.36 0.37 0.38 0.39 0.4 0.41 0.42 0.43 0.44 0.45 0.46 0.47 0.48 0.49 0.5 0.51 0.52 0.53 0.54 0.55 0.56 0.57 0.58 0.59 0.6 0.61 0.62 0.63 0.64 0.65 0.66 0.67 0.68 0.69 0.7 0.71 0.72 0.73 0.74 0.75 0.76 0.77 0.78 0.79 0.8 0.81 0.82 0.83 0.84 0.85 0.86 0.87 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.02 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.03 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.04 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.06 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.07 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.08 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.09 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1+3 1+3 1+3 1+3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1+2 1 1 1 1 1 1 1 1 1 1 1 1 1 1+3 1+3 1+3 1+3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1+2 1+2 1 1 1 1 1 1 1 1 1 1+3 1+3 1+3 1+3 1+3 1+3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1+2 1+2 1+2 1 1 1 1 1 1 1+3 1+3 1+3 1+3 1+3 1+3 1+3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1+2 1+2 1 1 1 1 1 1+3 1+3 1+3 1+3 1+3 1+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0.31 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1+2 1+2 1 1 1+3 1+3 1+3 1+3 1+3 1+3 1+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0.32 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1+2 1+2 1+2 1+2 1+2 1 1+3 1+3 1+3 1+3 1+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0.33 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1+2 1+2 1+2 1+3 1+3 1+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0.34 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0.35 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0.36 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0.37 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0.38 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0.39 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0.4 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0.41 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0.42 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0.43 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0.44 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0.45 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.46 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.47 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.48 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2+3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.49 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.5 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.51 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.52 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.53 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.54 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0.55 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0.56 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0.57 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0.58 0 0 0 0 0 0 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 0 0.59 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.61 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.62 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.66 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.71 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.72 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.74 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.76 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.77 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.78 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.79 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.82 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.83 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.84 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.85 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.86 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.87 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.88 0 0 0 0 0 0 0 0 0 0 0 0 0 0.89 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0 0 0 0 0 0 0 0 0 0 0 0.91 0 0 0 0 0 0 0 0 0 0 0.92 0 0 0 0 0 0 0 0 0 0.93 0 0 0 0 0 0 0 0 0.94 0 0 0 0 0 0 0 0.95 0 0 0 0 0 0 0.96 0 0 0 0 0 0.97 0 0 0 0 0.98 0 0 0 0.99 0 0 1 0 Colour code Region of inequalites ? C1 < 2 ? C2 < 2 ? C3 < 2 ? C1 > 2 ? C2 < 2 ? C3 < 2 ? C1 < 2 ? C2 > 2 ? C3 < 2 ? C1 < 2 ? C2 < 2 ? C3 > 2 ? C1 > 2 ? C2 > 2 ? C3 < 2 ? C1 > 2 ? C2 < 2 ? C3 > 2 ? C1 < 2 ? C2 > 2 ? C3 > 2 p 1 p 2 0 0.1667 0.3333 0 1 1 0.1667 0.4167 0.3333 0.4167 0.5000 p 1 + p 2 = 7/12 = 0.6333 p 1 + p 2 = 5/6 = 0.8333 0.5000 J.J. Hunter Coupling and Mixing Times in Markov Chains 17 A ?1 = 1 1? ? 2 ? ? 3 (? 1 ? ? 3 ) 1? p 33 (? 1 ? ? 3 ? p 33 ) p 23 (p 11 ? ? 3 ) p 12 p 23 p 12 p 31 1? p 22 (? 1 ? ? 3 ? p 22 ) p 12 (p 33 ? ? 3 ) p 31 (p 22 ? ? 3 ) p 23 p 31 1? p 11 (? 1 ? ? 3 ? p 11 ) ? ? ? ? ? ? ? ? ? ? . This leads to? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = 1 1? ? 2 ? ? 3 (? 1 ? ? 3 ) 2 ? ? 2 ? p 12 p 22 + ? 3 (p 33 ? p 23 ) 2 ? ? 2 ? p 31 p 11 + ? 3 (p 22 ? p 12 ) 2 ? ? 2 ? p 23 p 33 + ? 3 (p 11 ? p 31 ) ? ? ? ? ? ? ? ? ? ? . Finally, using Eqn. (4.5) and noting that ? 1 = p 23 p 31 , ? 2 = p 31 p 12 , ? 3 = p 12 p 23 , and ? = p 23 p 31 + p 31 p 12 + p 12 p 23 = 3? 2? 1 + ? 2 we can obtain expressions for ? C,i. :? C ,1? C ,2? C ,3 ? ? ? ? ? ? ? ? ? ? = 1 ?(1? ? 2 ? ? 3 (? 1 ? ? 3 ) (p 31 + p 23 )(2 ? ? 2 ) ? p 31 (p 12 p 22 + p 23 p 11 ) + {p 31 p 33 + p 23 (? 1 ? 2)}? 3 (p 12 + p 31 )(2 ? ? 2 ) ? p 12 (p 31 p 22 + p 23 p 33 ) + {p 12 p 11 + p 31 (? 1 ? 2)}? 3 (p 12 + p 23 )(2 ? ? 2 ) ? p 23 (p 31 p 11 + p 12 p 33 ) + {p 23 p 22 + p 12 (? 1 ? 2)}? 3 ? ? ? ? ? ? ? ? ? ? . Figure 3: Regions where expected coupling times exceed expected mixing times, Case 5 b=0.1 b=0.2 g= 0.1 g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 g= 0.1g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 f=0.1 M M M M M M M M M M f=0.1 M M M M C3 M M M M M f=0.2 M M M M M M M M M M f=0.2 M M M M M M M M M M f=0.3 M M C2 C2 C2 C2 M M M M f=0.3 M M M C2 M M M M M M f=0.4 M C2 C2 C2 C2 C2 C2 C2 C2 C2 f=0.4 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.5 M C2 C2 C2 C2 C2 C2 C2 C2 C2 f=0.5 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.6 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.6 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.7 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.7 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.8 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.8 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.9 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.9 M M C2 C2 C2 C2 C2 C2 C2 C2 f=1 M M C2 C2 C2 C2 C2 C2 C2 C2 f=1 M M C2 C2 C2 C2 C2 C2 C2 C2 b=0.3 b=0.4 g= 0.1 g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 g= 0.1g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 f=0.1 M M C3 C3 C3 C3 C3 C3 C3 C3 f=0.1 M M C3 C3 C3 C3 C3 C3 C3 C3 f=0.2 M M M C3 C3 C3 C3 C3 C3 C3 f=0.2 M M C3 C3 C3 C3 C3 C3 C3 C3 f=0.3 C1 M M C3 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C3 C3 C3 C3 C3 C3 C3 f=0.4 C1 C1 C2 C2 C2 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C3 C3 C3 C3 C3 C3 C3 f=0.5 C1 M C2 C2 C2 C2 C2 C2 C2 C2 f=0.5 C1 C1 C1 C2 C2 C2 C3 C3 C3 C3 f=0.6 C1 M C2 C2 C2 C2 C2 C2 C2 C2 f=0.6 C1 C1 C2 C2 C2 C2 C2 C2 C2 C2 f=0.7 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.7 C1 C1 C2 C2 C2 C2 C2 C2 C2 C2 f=0.8 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.8 C1 C1 C2 C2 C2 C2 C2 C2 C2 C2 f=0.9 M M C2 C2 C2 C2 C2 C2 C2 C2 f=0.9 C1 C1 C2 C2 C2 C2 C2 C2 C2 C2 f=1 M M C2 C2 C2 C2 C2 C2 C2 C2 f=1 C1 C1 C2 C2 C2 C2 C2 C2 C2 C2 b=0.5 b=0.6 g= 0.1 g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 g= 0.1g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 f=0.1 M M C3 C3 C3 C3 C3 C3 C3 C3 f=0.1 M M C3 C3 C3 C3 C3 C3 C3 C3 f=0.2 C1 M M C3 C3 C3 C3 C3 C3 C3 f=0.2 M M M C3 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C3 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C1 C3 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C1 C3 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C1 C3 C3 C3 C3 C3 C3 f=0.5 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.5 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.6 C1 C1 C1 C1 C2 C2 C2 C3 C3 C3 f=0.6 C1 C1 C1 C1 C1 C1 C3 C3 C3 C3 f=0.7 C1 C1 C1 C2 C2 C2 C2 C2 C2 C2 f=0.7 C1 C1 C1 C1 C1 C2 C2 C2 C3 C3 f=0.8 C1 C1 C1 C2 C2 C2 C2 C2 C2 C2 f=0.8 C1 C1 C1 C1 C2 C2 C2 C2 C2 C2 f=0.9 C1 C1 C1 C2 C2 C2 C2 C2 C2 C2 f=0.9 C1 C1 C1 C1 C2 C2 C2 C2 C2 C2 f=1 C1 C1 C1 C2 C2 C2 C2 C2 C2 C2 f=1 C1 C1 C1 C1 C2 C2 C2 C2 C2 C2 b=0.7 b=0.8 g= 0.1 g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 g= 0.1g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 f=0.1 M M M C3 C3 C3 C3 C3 C3 C3 f=0.1 M M M C3 C3 C3 C3 C3 C3 C3 f=0.2 M M M C3 C3 C3 C3 C3 C3 C3 f=0.2 M M M C3 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C1 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C1 C3 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.5 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.5 C1 C1 C1 C1 C1 C1 C3 C3 C3 C3 f=0.6 C1 C1 C1 C1 C1 C1 C3 C3 C3 C3 f=0.6 C1 C1 C1 C1 C1 C1 C3 C3 C3 C3 f=0.7 C1 C1 C1 C1 C1 C1 C1 C3 C3 C3 f=0.7 C1 C1 C1 C1 C1 C1 C1 C3 C3 C3 f=0.8 C1 C1 C1 C1 C1 C1 C2 C2 C2 C3 f=0.8 C1 C1 C1 C1 C1 C1 C1 C1 C3 C3 f=0.9 C1 C1 C1 C1 C1 C2 C2 C2 C2 C2 f=0.9 C1 C1 C1 C1 C1 C1 C1 C2 C2 C2 f=1 C1 C1 C1 C1 C1 C2 C2 C2 C2 C2 f=1 C1 C1 C1 C1 C1 C1 C2 C2 C2 C2 b=0.9 b=1.0 g= 0.1 g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 g= 0.1g=0.2 g=0.3 g=0.4 g=0.5 g=0.6 g=0.7 g=0.8 g=0.9 g=1 f=0.1 M M M C3 C3 C3 C3 C3 C3 C3 f=0.1 M M M C3 C3 C3 C3 C3 C3 C3 f=0.2 M M M C3 C3 C3 C3 C3 C3 C3 f=0.2 M M M C3 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C1 C3 C3 C3 C3 C3 C3 f=0.3 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.4 C1 C1 C1 C1 C1 C3 C3 C3 C3 C3 f=0.5 C1 C1 C1 C1 C1 C1 C3 C3 C3 C3 f=0.5 C1 C1 C1 C1 C1 C1 C3 C3 C3 C3 f=0.6 C1 C1 C1 C1 C1 C1 C1 C3 C3 C3 f=0.6 C1 C1 C1 C1 C1 C1 C1 C3 C3 C3 f=0.7 C1 C1 C1 C1 C1 C1 C1 C3 C3 C3 f=0.7 C1 C1 C1 C1 C1 C1 C1 C1 C3 C3 f=0.8 C1 C1 C1 C1 C1 C1 C1 C1 C3 C3 f=0.8 C1 C1 C1 C1 C1 C1 C1 C1 C3 C3 f=0.9 C1 C1 C1 C1 C1 C1 C1 C1 C1 C3 f=0.9 C1 C1 C1 C1 C1 C1 C1 C1 C1 C3 f=1 C1 C1 C1 C1 C1 C1 C1 C1 C2 C2 f=1 C1 C1 C1 C1 C1 C1 C1 C1 C1 C3 18 R.L.I.M.S. Vol. 11, April 2007 Case 6: ?Constant probability state selection? In this case, withP = 1 ? a a 2 a 2 b 2 1 ? b b 2 c 2 c 2 1 ? c ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? , Eqn. (4.4) yields a + b ? 5ab 4 ? b 2 + ab 4 ? a 2 + ab 4 ? c 2 + ac 4 c + a ? 5ac 4 ? a 2 + ac 4 ? c 2 + bc 4 ? b 2 + bc 4 b + c ? 5bc 4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = A? (C) = e In this case explicit expressions for the ? C,i are complicated but, as for Case 5 we can display figures that give regions of the parameter values a, b, c where the expected times, either for mixing or coupling from state i are minimised. Figure 4: Regions where expected coupling times exceed expected mixing times, Case 6 a=0.1 a=0.2 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 b=0.1 M M M M M M M M M M b=0.1 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.3 M M M M M M M M M M b=0.3 M M M M M M M M M M b=0.4 M M M M M M M M M M b=0.4 M M M M M M M M M M b=0.5 M M M M M M M M M M b=0.5 M M M M M M M M M M b=0.6 M M M M M M M M M M b=0.6 M M M M M M M M M M b=0.7 M M M M M M M M M M b=0.7 M M M M M M M M M M b=0.8 M M M M M M M M M M b=0.8 M M M M M M M M M M b=0.9 M M M M M M M M M M b=0.9 M M M M M M M M M M b=1 M M M M M M M M M M b=1 M M M M M M M M M M a=0.3 a=0.4 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 b=0.1 M M M M M M M M M M b=0.1 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.3 M M M M M M M M M M b=0.3 M M M M M M M M M M b=0.4 M M M M M M M M M M b=0.4 M M M M M M M M M M b=0.5 M M M M M M M M M M b=0.5 M M M M M M M M M M b=0.6 M M M M M M M M M M b=0.6 M M M M M M M M 3 3 b=0.7 M M M M M M M M M M b=0.7 M M M M M M M 3 3 3 b=0.8 M M M M M M M M M M b=0.8 M M M M M M 2 2,3 3 3 b=0.9 M M M M M M M M M M b=0.9 M M M M M 2 2 2 2,3 3 b=1 M M M M M M M M M M b=1 M M M M M 2 2 2 2 2,3 a=0.5 a=0.6 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 b=0.1 M M M M M M M M M M b=0.1 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.3 M M M M M M M M M M b=0.3 M M M M M M M M M M b=0.4 M M M M M M M M M M b=0.4 M M M M M M M M 3 3 b=0.5 M M M M M M M M 3 3 b=0.5 M M M M M M M 3 3 3 b=0.6 M M M M M M M 3 3 3 b=0.6 M M M M M M M 3 3 3 b=0.7 M M M M M M M 3 3 3 b=0.7 M M M M M M 2,3 3 3 3 b=0.8 M M M M M 2 2 2,3 3 3 b=0.8 M M M M 2 2 2 2,3 3 3 b=0.9 M M M M 2 2 2 2 2,3 3 b=0.9 M M M 2 2 2 2 2 2,3 3 b=1 M M M M 2 2 2 2 2 2,3 b=1 M M M 2 2 2 2 2 2 2,3 a=0.7 a=0.8 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 b=0.1 M M M M M M M M M M b=0.1 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.3 M M M M M M M M M 3 b=0.3 M M M M M M M M 3 3 b=0.4 M M M M M M M 3 3 3 b=0.4 M M M M M M 1 1,3 3 3 b=0.5 M M M M M M M 3 3 3 b=0.5 M M M M M 1 1 1,3 3 3 b=0.6 M M M M M M 1,3 3 3 3 b=0.6 M M M M 1 1 1 1,3 3 3 b=0.7 M M M M M 1,2 1,2,3 3 3 3 b=0.7 M M M 1 1 1 1 1,3 3 3 b=0.8 M M M 2 2 2 2 2,3 3 3 b=0.8 M M M 1,2 1,2 1,2 1,2 1,2,3 3 3 b=0.9 M M M 2 2 2 2 2 2,3 3 b=0.9 M M 2 2 2 2 2 2 2,3 3 b=1 M M 2 2 2 2 2 2 2 2,3 b=1 M M 2 2 2 2 2 2 2 2,3 a=0.9 a=1 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 c=0.1 c=0.2 c=0.3 c=0.4 c=0.5 c=0.6 c=0.7 c=0.8 c=0.9 c=1 b=0.1 M M M M M M M M M M b=0.1 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.2 M M M M M M M M M M b=0.3 M M M M M M M 1 1,3 3 b=0.3 M M M M M M 1 1 1 1,3 b=0.4 M M M M M 1 1 1 1,3 3 b=0.4 M M M M M M 1 1 1 1,3 b=0.5 M M M M 1 1 1 1 1,3 3 b=0.5 M M M M 1 1 1 1 1 1,3 b=0.6 M M M 1 1 1 1 1 1,3 3 b=0.6 M M M 1 1 1 1 1 1 1,3 b=0.7 M M M 1 1 1 1 1 1,3 3 b=0.7 M M 1 1 1 1 1 1 1 1,3 b=0.8 M M 1 1 1 1 1 1 1,3 3 b=0.8 M M 1 1 1 1 1 1 1 1,3 b=0.9 M M 1,2 1,2 1,2 1,2 1,2 1,2 1,2,3 3 b=0.9 M M 1 1 1 1 1 1 1 1,3 b=1 M M 2 2 2 2 2 2 2 2,3 b=1 M M 1,2 1,2 1,2 1,2 1,2 1,2 1,2 1,2 J.J. Hunter Coupling and Mixing Times in Markov Chains 19 In attempting to obtain explicit parametric expressions for the ? C ,i let? 1 = a + b + c,? 2 = ab + bc + ca,? 3 = abc. Then a 2 + b 2 + c 2 = ? 1 2 ? 2? 2 , and a 2 b 2 + b 2 c 2 + c 2 a 2 = ? 2 2 ? 2? 1 ? 3 . With these parameters det(A) = 3 4 ? 1 ? 2 ? 1 2 ? 3 ? 15 16 ? 2 2 ? 5 4 ? 1 ? 3 + 21 8 ? 2 ? 3 ? 27 16 ? 3 2 . While it is still difficult to find compact expressions for the ? C ,i we can show that? 12 (C )? 13 (C )? 23 (C ) ? ? ? ? ? ? ? ? ? ? = 1 det(A) a + c ? 5 4 ac + b 2 (1? a 2 ) ? ? ? ? ? ? b + c ? 5 4 bc + a 2 (1? b 2 ) ? ? ? ? ? ? ? ab 16 (a ? c)(b ? c) c + b ? 5 4 cb + a 2 (1? c 2 ) ? ? ? ? ? ? a + b ? 5 4 ab + c 2 (1? a 2 ) ? ? ? ? ? ? ? ca 16 (c ? b)(a ? b) b + a ? 5 4 ba + c 2 (1? b 2 ) ? ? ? ? ? ? c + a ? 5 4 ca + b 2 (1? c 2 ) ? ? ? ? ? ? ? bc 16 (b ? a)(c ? a) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? . It can be shown that the following parameter regions give simple incomplete bounds.? 3 ? 0.20 ?? C ,i < ? M for all i, while ? 3 > 0.252 ?? M < ? C ,i for some i;? 2 ? 1.12 ?? C ,i < ? M for all i, while ? 2 > 1.40 ?? M < ? C ,i for some i;? 1 < 1.9 ?? C ,i < ? M for all i, while ? 1 > 2.2 ?? M < ? C ,i for some i;? M ? 2.243 then ? C ,i < ? M for all i, while ? M ? 2.090 then ? M < ? C ,i for some i. 5. General results From Theorem 4.2 of [3] it is easy to see that for any irreducible m-state Markov chain,? M ? (m ?1) 2 . This is a generalisation of the results for 2-state and 3-state Markov chains as given earlier in this paper. The simplicity of this result, in contrast to the difficulty in obtaining simple expressions for the expected times to coupling, is certainly preferable as a measure of time to stationarity when one can be certain that the expected times to coupling are comparable. In [3], it was established (Theorem 4.3) that for the special case of independent trials with m possible outcomes, ? M = m ?1. The three-state, case 4 model, can be generalized in this special situation. Observe that in this m-state independent trials case with states 1, 2, ?, m and p i , the probability of outcome i, the elements of the Q matrix, given by (3.1), governing the transitions between state (i, j) to (r,s) are p r p s. . Thus the elements of each row of Q are the same. By ordering the states of the coupled process (X n , Y n ) in matched pairs as (1, 20 R.L.I.M.S. Vol. 11, April 2007 2), (2, 1), (1, 3), (3, 1), (4, 1), (1, 4),?,(i, j), (j, i), ?,(m-1, m), (m, m-1), it is easy to express the equation (I ?Q)? = e, (Eqn. (3.9)) in element form to show that for the row corresponding to transitions from state (i, j): (1? p i p j )? ij (C ) ? p i p j ? ji (C ) ? p r r? s,(r ,s)? (i , j ),( j ,i ) ? p s ? rs (C ) = 1. (5.1) Similarly from state (j, i): ?p i p j ? ij (C ) + (1? p i p j )? ji (C ) ? p r r? s ,(r ,s)?(i, j ),( j ,i ) ? p s ? rs (C ) = 1. (5.2) Subtract Eqn.(5.2) from Eqn. (5.1), to observe that for all i ? j, ? ij (C ) ?? ji (C ) = 0, so that? ij (C ) =? ji (C ) . (5.3) Further now adding Eqns. (5.1) and (5.2): (1? 2p i p j )? ij (C ) ? 2p i p j ? ji (C ) ? 2 p r r? s,(r ,s )?(i , j ),( j ,i ) ? p s ? rs (C ) = 2. Utilising Eqn. (5.3) and taking, for simplicity, i < j, (1? 2p i p j )? ij (C ) ? 2 p r r