Next: Bounds for the Eigenvalues Up: Reversibility; Estimates for the Previous: Alternative Estimate for the   Contents

Dirichlet-Forms and Rayleigh-Theorem

• Let be an arbitrary finite set and let be an -dimensional transition matrix, which is irreducible and aperiodic (i.e. quasi-positive) as well as reversible.
• Recall that
• all eigenvalues of are real (see Section 2.3.3), and
• by the Perron-Frobenius theorem (see Theorem 2.6 and Corollary 2.3) the eigenvalues of are in the interval , where
• the largest eigenvalue is and the absolute values of the other eigenvalues are (strictly) less than .

Remarks

• Instead of ordering the eigenvalues according to their absolute values (like above) we will now order them with respect to their own size and denote them by such that

• Moreover, for the multiplicative reversible version of the transition matrix that was introduced in Section 2.3.4 we have

i.e., for the eigenvalues of the matrix the notations and coincide.
• For large ,
• the calculation of the second largest absolute value among the eigenvalues can cause difficulties.
• Therefore, in Section 2.3.7 we will derive bounds for and , whose calculation is very simple.
• These bounds are particularly useful if
• the stationary (limit) distribution is at least in principle known,
• but in spite of this the corresponding Markov chain is started with an instationary initial distribution ; for example it could be started in a predetermined state , i.e. and for .

In order to derive an upper bound for , we need a representation formula for ,

• that is usually called the Rayleigh-theorem in literature
• and that is expressed based on the so-called Dirichlet-form

 (115)

of the reversible pair , where denotes the inner product of and with respect to ; see (103).

First of all we will show the following lemma.

Lemma 2.8   For all ,

 (116)

Proof
From the definition (103) of the inner product and the reversibility of the pair we obtain

We will now prove the Rayleigh-theorem that yields a representation formula for the second largest eigenvalue of the reversible pair .

Theorem 2.17
• Let     denote the set of all vectors in whose components are not all equal.
• For the eigenvalue of the reversible pair the following holds

 (117)

where denotes the variance of the components of with respect to defined in .

Proof

• Lemma 2.8 implies for arbitrary and

• Thus, the assertion (117) is equivalent to

 (118)

where .
• Let now the left eigenvectors of be chosen such that they are an orthonormal basis of with respect to the inner product , i.e. if and if where .
• First of all, the eigenvectors of the symmetric vectors are chosen such that they are orthonormal with respect to the ordinary euclidian inner product. Then we can define for all (see also Section 2.3.3).
• For every there is now a uniquely determined vector such that

• As we obtain

and hence

• On the other hand as and the eigenvectors are orthonormal with respect to the inner product we can conclude that

and   if

• Thus for every

• This shows that (118) holds as the last expression for the quotient implies

for where as and are linearly independent.

Next: Bounds for the Eigenvalues Up: Reversibility; Estimates for the Previous: Alternative Estimate for the   Contents
Ursa Pantle 2006-07-20