    Next: Multiplicative Reversible Version of Up: Reversibility; Estimates for the Previous: Recursive Construction of the   Contents

### Determining the Rate of Convergence under Reversibility

• Let and be a quasi-positive (i.e. an irreducible and aperiodic) transition matrix.
• In case the eigenvalues of are pairwise distinct we showed by the Perron-Frobenius-Theorem (see Corollary 2.4) that (96)

where is the (uniquely determined) solution of the equation .
• If is also reversible one can show that the basis considered in (96) cannot be improved.
• Let be reversible, where is an irreducible and aperiodic transition matrix.
• In this case the detailed balance condition (85) implies the symmetry of the matrix where .
• As the eigenvalues of coincide with the eigenvalues of we obtain for all ,
• and the right eigenvectors of can be chosen such that all of their components are real,
• that furthermore are also left eigenvectors of and that the rows as well as the lines of the matrix are orthonormal vectors.
• The spectral representation (30) of yields for every  • By plugging in and we obtain for arbitrary   (97)

• If is even or all eigenvalues are nonnegative, then • This shows that is the smallest positive number such that the estimate for the rate of convergence considered in (96) holds uniformly for all initial distributions .

Remarks

• Notice that (97) yields the following more precise specification of the convergence estimate (96). We have as the column vectors and hence also the row vectors where form an orthonormal basis in and thus by the Chauchy-Schwarz inequality • Consequently, (98)

• However, the practical benefit of the estimate (98) can be limited for several reasons:
• The factor in front of in (98) does not depend on the choice of the initial distribution .
• The derivation of the estimate (98) requires the Markov chain to be reversible.
• It can be difficult to determine the eigenvalue if the number of states is large.

• Therefore in Section 2.3.5 we consider an alternative convergence estimate,
• which depends on the initial distribution
• and does not require the reversibility of the Markov chain.
• Furthermore, in Section 2.3.7 we will derive an upper bound for the second largest absolute value among the eigenvalues of a reversible transition matrix.    Next: Multiplicative Reversible Version of Up: Reversibility; Estimates for the Previous: Recursive Construction of the   Contents
Ursa Pantle 2006-07-20