Dirichlet-Forms and Rayleigh-Theorem

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

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 $\lambda_1,\ldots,\lambda_\ell$ such that
  $$1=\lambda_1>\lambda_2\ge\ldots\ge\lambda_\ell>-1\,.$$

• Moreover, for the multiplicative reversible version ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ of the transition matrix ${\mathbf{P}}$ that was introduced in Section 2.3.4 we have
  $$1=\lambda_1>\lambda_2\ge\ldots\ge\lambda_\ell>0\,,$$
  i.e., for the eigenvalues of the matrix ${\mathbf{M}}$ the notations $\theta_1,\ldots,\theta_\ell$ and $\lambda_1,\ldots,\lambda_\ell$ coincide.
• For large $\ell$,
  • the calculation of the second largest absolute value $\vert\theta_2\vert=\max\{\lambda_2,\vert\lambda_\ell\vert\}$ among the eigenvalues can cause difficulties.
  • Therefore, in Section 2.3.7 we will derive bounds for $\lambda _2$ and $\lambda _\ell$, 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 ${\boldsymbol{\alpha}}$; for example it could be started in a predetermined state $i\in E$, i.e. $\alpha_i=1$ and $\alpha_j=0$ for $j\not=i$.

In order to derive an upper bound for $\lambda _2$, we need a representation formula for $\lambda _2$,

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

  $$D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=... ...l(({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}$$ (115)

  
  
  of the reversible pair $({\mathbf{P}},{\boldsymbol{\pi}})$ , where $({\mathbf{y}},{\mathbf{x}})_{\boldsymbol{\pi}}$ denotes the inner product of ${\mathbf{y}}$ and ${\mathbf{x}}$ with respect to ${\boldsymbol{\pi}}$; see (103).

First of all we will show the following lemma.

Lemma 2.8   $\;$ For all ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell$,

$$D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\frac{1}{2}\;\sum_{i,j\in E}\pi_ip_{ij}(x_j-x_i)^2\,.$$ (116)

Proof

$\;$ From the definition (103) of the inner product and the reversibility of the pair $({\mathbf{P}},{\boldsymbol{\pi}})$ we obtain

$$2\bigl(({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}} = 2\sum\limits_{i,j\in E}\pi_ip_{ij}x_i(x_i-x_j)$$

$$\stackrel{i\to j}{=} \sum\limits_{i,j\in E}\pi_ip_{ij}x_i(x_i-x_j) +\sum\limits_{i,j\in E}\pi_jp_{ji}x_j(x_j-x_i)$$

$$\stackrel{(\ref{for.cha.rev})}{=} \sum\limits_{i,j\in E}\pi_ip_{ij}x_i(x_i-x_j) +\sum\limits_{i,j\in E}\pi_ip_{ij}x_j(x_j-x_i)$$

$$= \sum_{i,j\in E}\pi_ip_{ij}(x_j-x_i)^2\,.$$

 
  $\Box$

We will now prove the Rayleigh-theorem that yields a representation formula for the second largest eigenvalue $\lambda _2$ of the reversible pair $({\mathbf{P}},{\boldsymbol{\pi}})$.

Theorem 2.17    

• Let $\mathbb{R}^\ell_{\not=}=\bigl\{{\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell:\;$   $\mbox{$x_i\not=x_j$\ for some pair $i,j\in E$}$$\bigr\}$ denote the set of all vectors in $\mathbb{R}^\ell$ whose components are not all equal.
• For the eigenvalue $\lambda _2$ of the reversible pair $({\mathbf{P}},{\boldsymbol{\pi}})$ the following holds

  $$\lambda_2=1-\inf\limits_{{\mathbf{x}}\in\mathbb{R}^\ell_{\not=}}\... ...)}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})}\;,$$ (117)

  
  
  where ${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})$ denotes the variance of the components of ${\mathbf{x}}$ with respect to ${\boldsymbol{\pi}}$ defined in $(\ref{var.iks.pii})$.

Proof

 

• Lemma 2.8 implies for arbitrary $c\in\mathbb{R}$ and ${\mathbf{x}}\in\mathbb{R}^\ell$
  $$D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=... ...ldsymbol{\pi}})}({\mathbf{x}}-c\,{\mathbf{e}},{\mathbf{x}}-c\,{\mathbf{e}})\,.$$
  • Thus, the assertion (117) is equivalent to

    $$1-\lambda_2=\inf\limits_{{\mathbf{x}}\in\mathbb{R}^\ell_0}\; \fra... ...)}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})}\;,$$ (118)

    
    
    where $\mathbb{R}^\ell_0=\bigl\{{\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell:\; ({\mathbf{x}})_{\boldsymbol{\pi}}=0,\,{\mathbf{x}}\not={\,{\bf0}}\bigr\}$.
  • Let now the left eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ of ${\mathbf{P}}$ be chosen such that they are an orthonormal basis of $\mathbb{R}^\ell$ with respect to the inner product $(\cdot\,,\,\cdot)_{\boldsymbol{\pi}}$, i.e. $({\boldsymbol{\phi}}_i,{\boldsymbol{\phi}}_j)_{\boldsymbol{\pi}}=1$ if $i=j$ and $({\boldsymbol{\phi}}_i,{\boldsymbol{\phi}}_j)_{\boldsymbol{\pi}}=0$ if $i\not= j$ where ${\boldsymbol{\phi}}_1={{\mathbf{e}}}$.
  • First of all, the eigenvectors ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ of the symmetric vectors ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ are chosen such that they are orthonormal with respect to the ordinary euclidian inner product. Then we can define ${\boldsymbol{\phi}}_i={\mathbf{D}}^{-1}{\boldsymbol{\phi}}_i^*$ for all $i\in E$ (see also Section 2.3.3).
  • For every ${\mathbf{x}}\in\mathbb{R}^\ell$ there is now a uniquely determined vector $\bigl(x_1^{\rm (r)},\ldots,x_\ell^{\rm (r)}\bigr)^\top\in\mathbb{R}^\ell$ such that
    $${\mathbf{x}}=\sum\limits_{i=1}^\ell x_i^{\rm (r)}{\boldsymbol{\phi}}_i\,.$$

  • As $\lambda_1=1$ we obtain
    $$({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}}=\sum\limits_{i=2}^\ell (1-\lambda_i)x_i^{\rm (r)}{\boldsymbol{\phi}}_i$$   and hence$$\qquad D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\sum\limits_{i=2}^\ell (1-\lambda_i)\bigl(x_i^{\rm (r)}\bigr)^2\,.$$

• On the other hand as ${\boldsymbol{\phi}}_1={{\mathbf{e}}}$ and the eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ are orthonormal with respect to the inner product $(\cdot\,,\,\cdot)_{\boldsymbol{\pi}}$ we can conclude that
  $$({\mathbf{x}})_{\boldsymbol{\pi}}=({\mathbf{x}},\,{{\mathbf{e}}})_{\boldsymbol{\pi}}=x_1^{\rm (r)}$$   and$$\qquad {\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})= \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2\,,$$   if$$\; ({\mathbf{x}})_{\boldsymbol{\pi}}=0\,.$$
  • Thus for every ${\mathbf{x}}\in\mathbb{R}^\ell_0$
    

    $$\frac{D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})} = \frac{\sum\limits_{i=2}^\ell (1-\lambda_i)\bigl(x_i^{\rm (r)}\bigr)^2}{ \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2}$$

    $$= (1-\lambda_2)+\; \frac{\sum\limits_{i=2}^\ell (1-\lambda_i)\bigl(... ...bigl(x_i^{\rm (r)}\bigr)^2}{ \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2}$$

    $$= (1-\lambda_2)+\; \frac{\sum\limits_{i=3}^\ell (\lambda_2-\lambda_... ...2}{ \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2} \;\;\ge\; 1-\lambda_2\,.$$

    
    

  • This shows that (118) holds as the last expression for the quotient $D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})/{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})$ implies
    $$\frac{D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})}=1-\lambda_2\,,$$
    for ${\mathbf{x}}={\boldsymbol{\phi}}_2$ where ${\boldsymbol{\phi}}_2\in\mathbb{R}^\ell_0$ as ${\boldsymbol{\phi}}_1={\mathbf{e}}$ and ${\boldsymbol{\phi}}_2$ are linearly independent.
    
    $\Box$