Determining the Rate of Convergence under Reversibility

• Let $E=\{1,\ldots,\ell\}$ and ${\mathbf{P}}$ be a quasi-positive (i.e. an irreducible and aperiodic) transition matrix.
  • In case the eigenvalues $\theta_1,\ldots,\theta_\ell$ of ${\mathbf{P}}$ are pairwise distinct we showed by the Perron-Frobenius-Theorem (see Corollary 2.4) that

    $$\max\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert= O(\vert\theta_2\vert^n)\,,$$ (96)

    
    
    where ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ is the (uniquely determined) solution of the equation ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$.
  • If $({\mathbf{P}},{\boldsymbol{\pi}})$ is also reversible one can show that the basis $\vert\theta_2\vert$ considered in (96) cannot be improved.
• Let $({\mathbf{P}},{\boldsymbol{\pi}})$ be reversible, where ${\mathbf{P}}$ is an irreducible and aperiodic transition matrix.
  • In this case the detailed balance condition (85) implies the symmetry of the matrix ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ where ${\mathbf{D}}={\,{\rm diag}}(\sqrt{\pi_i})$.
  • As the eigenvalues $\theta_1,\ldots,\theta_\ell$ of ${\mathbf{P}}$ coincide with the eigenvalues of ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ we obtain $\theta_i\in\mathbb{R}$ for all $i\in E$,
  • and the right eigenvectors ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ of ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ can be chosen such that all of their components are real,
  • that furthermore ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ are also left eigenvectors of ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ and that the rows as well as the lines of the $\ell\times\ell$ matrix $({\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*)$ are orthonormal vectors.
• The spectral representation (30) of ${\mathbf{A}}={\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ yields for every $n\ge 1$
  $${\mathbf{P}}^n=\bigl({\mathbf{D}}^{-1}{\mathbf{A}}{\mathbf{D}}\bi... ...f{D}}^{-1}{\boldsymbol{\phi}}_k^*({\boldsymbol{\phi}}_k^*)^\top{\mathbf{D}}\,.$$
  • By plugging in $\theta_1=1$ and ${\boldsymbol{\phi}}_1^*=(\sqrt{\pi_1},\ldots,\sqrt{\pi_\ell})^\top$ we obtain for arbitrary $i,j\in E$

    $$p_{ij}^{(n)}=\pi_j+\sqrt{\frac{\pi_j}{\pi_i}}\;\sum\limits_{k=2}^\ell\theta_k^n \phi_{ki}^*\phi_{kj}^*\,, \mbox{where ${\boldsymbol{\phi}}_k^*=(\phi_{k1}^*,\ldots,\phi_{k\ell}^*)^\top$.}$$ (97)

    
    

  • If $n$ is even or all eigenvalues $\theta_2,\ldots,\theta_\ell$ are nonnegative, then
    $$\sup\limits_{{\boldsymbol{\alpha}}_0}\max\limits_{j\in E}\vert\al... ...(\phi_{kj}^*)^2\Bigr\vert \ge \theta_2^n\max\limits_{j\in E}(\phi_{2j}^*)^2\,.$$

• This shows that $\vert\theta_2\vert$ is the smallest positive number such that the estimate for the rate of convergence considered in (96) holds uniformly for all initial distributions ${\boldsymbol{\alpha}}_0$.

Remarks

 

• Notice that (97) yields the following more precise specification of the convergence estimate (96). We have
  $$\bigl\vert p_{ij}^{(n)}-\pi_j\bigr\vert \le \frac{1}{\sqrt{\min\l... ...rt^n \le \frac{1}{\sqrt{\min\limits_{i\in E} \pi_i}}\; \vert\theta_2\vert^n\,,$$
  as the column vectors ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ and hence also the row vectors $(\phi_{1,j},\ldots,\phi_{\ell,j})$ where $j=1,\ldots,\ell$ form an orthonormal basis in $\mathbb{R}^\ell$ and thus by the Chauchy-Schwarz inequality
  $$\sum\limits_{k=2}^\ell \vert\phi_{ki}^*\vert \vert\phi_{kj}^*\ver... ...^*)^2\Bigr)^{1/2}\Bigl(\sum\limits_{k=1}^\ell (\phi_{kj}^*)^2\Bigr)^{1/2}=1\,.$$

• Consequently,

  $$\max\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert\le \frac{1}{\sqrt{\min\limits_{i\in E} \pi_i}}\; \vert\theta_2\vert^n \;.$$ (98)

  
  

  
  

• However, the practical benefit of the estimate (98) can be limited for several reasons:
  • The factor in front of $\vert\theta_2\vert^n$ in (98) does not depend on the choice of the initial distribution ${\boldsymbol{\alpha}}_0$.
  • The derivation of the estimate (98) requires the Markov chain to be reversible.
  • It can be difficult to determine the eigenvalue $\theta_2$ 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 $\vert\theta_2\vert$ among the eigenvalues of a reversible transition matrix.