Bounds for the Eigenvalues $\lambda _2$ and $\lambda _\ell$

In order to derive bounds for the eigenvalues $\lambda _2$ and $\lambda _\ell$ the following notions and notations are necessary.

• For each pair $i,j\in E$ such that $i\not= j$ and $p_{ij}>0$ we denote
  • by $e=e_{ij}$ the corresponding directed edge of the transition graph
  • by $e^-=i$ and $e^+=j$ the starting and target vertices of $e$, respectively.
  • Let $\mathcal{E}$ be the set of all directed edges $e=e_{ij}$ such that $i\not= j$ and $p_{ij}>0$.

  
  

• Furthermore, for each $i,j\in E$ such that $i\not= j$ we consider exactly one path $\gamma_{ij}$ from $i$ to $j$,
  • which is given by a vector $\gamma_{ij}=(i_0,i_1,\ldots,i_{m-1},i_m)$ of states such that $i=i_0$, $j=i_m$ and
    $$p_{ii_1}p_{i_1i_2}\,\ldots\,p_{i_{m-1}j}>0\,,$$
    such that none of the edges $e_{i_{k-1}i_k}$ is contained more than once (and $m$ is the smallest possible number).
  • Let $\Gamma$ be the set of all these paths and for each path $\gamma_{ij}\in\Gamma$ define

    $$\vert\gamma_{ij}\vert=\sum\limits_{e\in\gamma_{ij}}\frac{1}{Q(e)}... ...{1}{\pi_{i_1}p_{i_1i_2}}\;+\;\ldots \;+\;\frac{1}{\pi_{i_{m-1}}p_{i_{m-1}j}}\;,$$ (119)

    
    
    where $Q(e_{i_{k-1}i_k})=\pi_{i_{k-1}}p_{i_{k-1}i_k}$.
  • The so-called Poincaré-coefficient $\kappa$ of the set of paths $\Gamma$ is then defined as

    $$\kappa=\kappa(\Gamma)=\max\limits_{e\in\mathcal{E}} \sum\limits_{\gamma_{ij}\ni e} \vert\gamma_{ij}\vert\pi_i\pi_j\,.$$ (120)

    
    

• Finally we consider
  • the extended set of edges $\mathcal{E}^\prime\supset\mathcal{E}$ also containing the edges of the type $i\to i$ in case $p_{ii}>0$.
  • for all $i\in E$ exactly one path $\gamma_i$ from $i$ to $i$ which contains an odd number of edges in $\mathcal{E}^\prime$ such that no edge occurs more than once.
  • Let $\Gamma^\prime$ be the set of all these paths and for every path

    $\gamma_i\in\Gamma^\prime$ let

    $$\vert\gamma_i\vert=\sum\limits_{e\in\gamma_i}\frac{1}{Q(e)}\;.$$ (121)

    
    

  • The coefficient $\zeta$ of the path set $\Gamma^\prime$ is then defined as

    $$\zeta=\zeta(\Gamma^\prime)=\max\limits_{e\in\mathcal{E}^\prime} \sum\limits_{\gamma_i\ni e} \vert\gamma_i\vert\pi_i\,.$$ (122)

    
    

Theorem 2.18   $\;$ For the eigenvalues $\lambda _2$ and $\lambda _\ell$ of ${\mathbf{P}}$ the following inequalities hold

$$1-\;\frac{1}{\kappa}\ge\lambda_2\ge\lambda_\ell\ge-1+\;\frac{2}{\zeta}$$ (123)

and hence

$$\max\{\lambda_2,\vert\lambda_\ell\vert\}\le1-\min\, \Bigl\{\,\frac{1}{\kappa}\;,\;\frac{2}{\zeta}\,\Bigr\}\,.$$ (124)

Proof

 

• First we will show that $\lambda_2\le 1-\kappa^{-1}$.
  • Because of Theorem 2.17 it suffices to show that

    $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})\le\kappa\; D_{({\mat... ...({\mathbf{x}},{\mathbf{x}})\,,\qquad\forall\, {\mathbf{x}}\in\mathbb{R}^\ell\,.$$ (125)

    
    

  • Using the notation introduced in (119) we obtain
    

    $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) = \frac{1}{2}\;\Bigl(2\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2-2({\mathbf{x}})_{\boldsymbol{\pi}}^2\Bigr)$$

    $$= \frac{1}{2}\;\Bigl(\sum\limits_{i\in E} x_i^2\pi_i+\sum\limits_{j\in E} x_j^2\pi_j -2\sum\limits_{i,j\in E} x_i x_j\pi_i\pi_j\Bigr)$$

    $$= \frac{1}{2}\;\sum\limits_{i,j\in E}(x_i-x_j)^2\pi_i\pi_j$$

    $$= \frac{1}{2}\;\sum\limits_{i,j\in E}\Bigl(\sum\limits_{e\in\gamma_{ij}}\;\frac{1}{\sqrt{Q(e)}}\;\sqrt{Q(e)} (x_{e^-}-x_{e^+})\Bigr)^2\pi_i\pi_j\,.$$

    
    

  • An application of the Cauchy-Schwarz inequality yields
    

    $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) \le \frac{1}{2}\;\sum\limits_{i,j\in E}\Bigl(\vert\gamma_{ij}\vert\sum\limits_{e\in\gamma_{ij}}\;{Q(e)} (x_{e^-}-x_{e^+})^2\Bigr)\pi_i\pi_j$$

    $$= \frac{1}{2}\; \sum\limits_{e\in\mathcal{E}}\Biggl({Q(e)} (x_{e^-}... ...um\limits_{\gamma_{ij}\ni\, e} \vert\gamma_{ij}\vert\; \pi_i\pi_j \Bigr)\Biggr)$$

    $$\le \kappa\;D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})\,,$$

    
    
    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 $\lambda_\ell\ge-1+2\zeta^{-1}$.
  • For this purpose we exploit the following equation: For all ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell$

    $$\frac{1}{2}\;\sum\limits_{i,j\in E}(x_i+x_j)^2\pi_i p_{ij}= ({\ma... ...thbf{x}},{\mathbf{x}})_{\boldsymbol{\pi}}+\Vert x\Vert _{\boldsymbol{\pi}}^2\,,$$ (126)

    
    
    as the reversibility of $({\mathbf{P}},{\boldsymbol{\pi}})$ implies
    

    $$\frac{1}{2}\;\sum\limits_{i,j\in E}(x_i+x_j)^2\pi_i p_{ij} = \frac{1}{2}\;\underbrace{\sum\limits... ...tackrel{(\ref{for.cha.rev})}{=}\pi_j p_{ji}}}_{=\sum\limits_{j\in E}x_j^2\pi_j}$$

    $$= \Vert x\Vert _{\boldsymbol{\pi}}^2+({\mathbf{P}}{\mathbf{x}},{\mathbf{x}})_{\boldsymbol{\pi}}\,.$$

    
    

  • Let now $\gamma_i=(i_0,i_1,\ldots,i_{2m},i_{2m+1})$ where $i=i_0=i_{2m+1}$ is a path from $i$ to $i$, containing an odd number of edges such that every edge does not occur more than once.
  • Then
    

    $$x_i = \frac{1}{2}\;\Bigl((x_i+x_{i_1})-(x_{i_1}+x_{i_2})+\ldots+(x_{i_{2m}}+x_i)\Bigr)$$

    $$= \frac{1}{2}\;\sum\limits_{e\in\gamma_i}(-1)^{n(e)} (x_{e^+}+x_{e^-})\,,$$

    
    
    where $n(e)=k$ if $e=(i_k,i_{k+1})\in\gamma_i$.
  • Similarly to the first part of the proof, the Cauchy-Schwarz inequality implies that for all ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell$
    

    $$\Vert{\mathbf{x}}\Vert^2_{\boldsymbol{\pi}} = \sum\limits_{i\in E}\;\frac{\pi_i}{4}\;\Bigl(\sum\limits_{e\in\gamma_i}\; \frac{1}{\sqrt{Q(e)}}\;\sqrt{Q(e)}(-1)^{n(e)} (x_{e^+}+x_{e^-})\Bigr)^2$$

    $$\le \sum\limits_{i\in E}\;\Bigl(\frac{\pi_i}{4}\; \vert\gamma_i\vert \sum\limits_{e\in\gamma_i}\;(x_{e^+}+x_{e^-})^2Q(e)\Bigr)$$

    $$= \frac{1}{4}\;\sum\limits_{e\in\mathcal{E}^\prime}\Bigl((x_{e^+}+x_{e^-})^2 Q(e)\sum\limits_{\gamma_i\ni\, e} \vert\gamma_i\vert\pi_i\Bigr)$$

    $$\le \frac{\zeta}{4}\;\sum\limits_{e\in\mathcal{E}^\prime}(x_{e^+}+x_{e^-})^2Q(e)\,.$$

    
    

  • From (126) we can now conclude that
    $$\Vert{\mathbf{x}}\Vert^2_{\boldsymbol{\pi}}\le\;\frac{\zeta}{2}\;... ...{x}})_{\boldsymbol{\pi}}+\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2\Bigr)\,.$$

  • For ${\mathbf{x}}={\boldsymbol{\phi}}_\ell$ we obtain in particular that
    $$1\le\frac{\zeta}{2}\;(\lambda_\ell+1)$$   and$$\qquad \lambda_\ell\ge -1+\frac{2}{\zeta}\;.$$
    
     
      $\Box$
    
    
    

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 $G=(V,K)$ be a connected graph with vertices $V=\{v_1,\ldots,v_\ell\}$ and edges $K$ where each edge connects two vertices,
  • such that for each pair $v_i,v_j\in V$ of vertices there is a ,,path'' of edges in $K$ connecting $v_i$ and $v_j$.
• A random walk on the graph $G=(V,K)$ is a Markov chain $X_0,X_1,\ldots:\Omega\to E$
  • with state space $E=\{1,\ldots,\ell\}$ and transition matrix ${\mathbf{P}}=(p_{ij})$ where

    $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{1}{d_i} &\mbo... ...$v_i$\ and $v_j$\ are neighbors,}\\ [3\jot] 0 &\mbox{else.} \end{array}\right.$$ (127)

    
    

  • Recall that two vertices $v_i$ and $v_j$ are called neighbors if they are endpoints of the same edge where, for each vertex $v_i$, $d_i$ denotes its number of neighbors.
• We already showed that
  • the transition matrix ${\mathbf{P}}$ given in (127) is always irreducible (where we now additionally assume ${\mathbf{P}}$ to be aperiodic),
  • the uniquely determined initial distribution ${\boldsymbol{\pi}}$ is given by

    $${\boldsymbol{\pi}}=\Bigl(\frac{d_1}{d}\;,\ldots,\;\frac{d_\ell}{d}\Bigr)^\top\,, \mbox{where $\;d=\sum\limits_{i=1}^\ell d_i$,}$$ (128)

    
    

  • the pair $({\mathbf{P}},{\boldsymbol{\pi}})$ given by (127)-(128) is reversible.
• For the Poincaré-coefficient $\kappa$ introduced in (120) we obtain
  $$\kappa=\kappa(\Gamma)=\max\limits_{e\in\mathcal{E}} \sum\limits_{\gamma_{ij}\ni e} \vert\gamma_{ij}\vert\pi_i\pi_j\,,$$
  where
  $$\vert\gamma_{ij}\vert=\sum\limits_{e\in\gamma_{ij}}\frac{1}{Q(e)}=d\,\Delta(\gamma_{ij})$$
  and $\Delta(\gamma_{ij})=\char93 \{e:\,e\in \gamma_{ij}\}$ denotes the number of edges (i.e. the length) of the path $\gamma_{ij}$.
• Taking into account (127)-(128), this implies

  $$\kappa(\Gamma)\;\le\; \frac{\delta^2\Delta\beta}{d}\;,$$ (129)

  
  
  where $d/2$ denotes the total number of edges,
  • $\delta=\max_{i\in E}d_i$ is the maximum number of edges originating at a vertex,
  • $\Delta=\max_{\gamma\in\Gamma}\Delta(\gamma)$ denotes the maximal path length and
  • $\beta=\max_{e\in\mathcal{E}}\char93 \{\gamma\in \Gamma:\,\gamma\ni e\}$ 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

  $$\lambda_2\;\le 1-\;\frac{1}{\kappa}\;\le\; 1-\;\frac{d}{\delta^2\Delta\beta}$$ (130)

  
  
  for the second largest eigenvalue $\lambda _2$ of ${\mathbf{P}}$.
• In a similar way one obtains the upper bound
  $$\zeta=\zeta(\Gamma^\prime)=\max\limits_{e\in\mathcal{E}^\prime} \... ...mma_i\ni e} \vert\gamma_i\vert\pi_i\le \delta \,\Delta^\prime\,\beta^\prime\,,$$
  where
  $$\vert\gamma_i\vert=\sum\limits_{e\in\gamma_i}\frac{1}{Q(e)}=d\,\D... ...\max_{e\in\mathcal{E}^\prime}\char93 \{\gamma\in \Gamma^\prime:\,\gamma\ni e\}$$
  and hence

  $$\lambda_\ell\;\ge\; -1 +\;\frac{2}{\zeta}\;\ge\;-1+\;\frac{2}{\delta \,\Delta^\prime\,\beta^\prime}\;.$$ (131)

  
  

• Remarks. 
  • For the numerical example from Section 2.3.1
    
    
    
    

    the following holds:

    $$d=24,\, \delta=5,\,\Delta=3,\,\beta=7$$   und$$\qquad \Delta^\prime=3,\,\beta^\prime=3.$$

  • The inequalities (130) and (131) thus imply
    $$\lambda_2\;\le\; 1-\;\frac{24}{25\cdot 3\cdot 7}\;<\;\frac{24}{25... ...nd}\qquad \lambda_8\;>\;-1+\;\frac{2}{5\cdot 3\cdot 3}\;=\;-\;\frac{43}{45}\;.$$
    and hence
    $$\max\{\lambda_2,\vert\lambda_8\vert\}\;<\;\frac{24}{25}\;.$$