Next: Monte-Carlo Simulation Up: Reversibility; Estimates for the Previous: Dirichlet-Forms and Rayleigh-Theorem   Contents

### Bounds for the Eigenvalues and

In order to derive bounds for the eigenvalues and the following notions and notations are necessary.

• For each pair such that and we denote
• by the corresponding directed edge of the transition graph
• by and the starting and target vertices of , respectively.
• Let be the set of all directed edges such that and .

• Furthermore, for each such that we consider exactly one path from to ,
• which is given by a vector of states such that , and

such that none of the edges is contained more than once (and is the smallest possible number).
• Let be the set of all these paths and for each path define

 (119)

where .
• The so-called Poincaré-coefficient of the set of paths is then defined as

 (120)

• Finally we consider
• the extended set of edges also containing the edges of the type in case .
• for all exactly one path from to which contains an odd number of edges in such that no edge occurs more than once.
• Let be the set of all these paths and for every path

let

 (121)

• The coefficient of the path set is then defined as

 (122)

Theorem 2.18   For the eigenvalues and of the following inequalities hold

 (123)

and hence

 (124)

Proof

• First we will show that .
• Because of Theorem 2.17 it suffices to show that

 (125)

• Using the notation introduced in (119) we obtain

• An application of the Cauchy-Schwarz inequality yields

where the last inequality follows from Lemma 2.8 and by definition of the Poincaré-coefficient; see (120). This shows (125).
• In order to finish the proof it is left to show that .
• For this purpose we exploit the following equation: For all

 (126)

as the reversibility of implies

• Let now where is a path from to , containing an odd number of edges such that every edge does not occur more than once.
• Then

where if .
• Similarly to the first part of the proof, the Cauchy-Schwarz inequality implies that for all

• From (126) we can now conclude that

• For we obtain in particular that

and

Example
Random Walk on a Graph
• We return to the example of a random walk on a graph that has been already discussed in Section 2.3.1.
• Let be a connected graph with vertices and edges where each edge connects two vertices,
• such that for each pair of vertices there is a ,,path'' of edges in connecting and .
• A random walk on the graph is a Markov chain
• with state space and transition matrix where

 (127)

• Recall that two vertices and are called neighbors if they are endpoints of the same edge where, for each vertex , denotes its number of neighbors.
• the transition matrix given in (127) is always irreducible (where we now additionally assume to be aperiodic),
• the uniquely determined initial distribution is given by

 (128)

• the pair given by (127)-(128) is reversible.
• For the Poincaré-coefficient introduced in (120) we obtain

where

and denotes the number of edges (i.e. the length) of the path .
• Taking into account (127)-(128), this implies

 (129)

where denotes the total number of edges,
• is the maximum number of edges originating at a vertex,
• denotes the maximal path length and
• is the so-called Bottleneck-coefficient, i.e. the maximal number of paths containing a single edge.
• From (123) and (129) we obtain the following estimate

 (130)

for the second largest eigenvalue of .
• In a similar way one obtains the upper bound

where

and hence

 (131)

• Remarks.
• For the numerical example from Section 2.3.1

the following holds:

und

• The inequalities (130) and (131) thus imply

and hence

Next: Monte-Carlo Simulation Up: Reversibility; Estimates for the Previous: Dirichlet-Forms and Rayleigh-Theorem   Contents
Ursa Pantle 2006-07-20