Estimate for the Rate of Convergence

• We will now show how the upper bounds for the variational distance $d_{\rm TV}({\boldsymbol{\alpha}}_n,\,{\boldsymbol{\pi}})$ and the second largest absolute value $\vert\theta_2\vert=\max\{\lambda_2,\vert\lambda_\ell\vert\}$ of the eigenvalues $\lambda_1,\ldots,\lambda_\ell$ of the transition matrix ${\mathbf{P}}$ derived in Section 2.3 can be used
  • in order to determine upper bounds for the distance $d_{\rm TV}({\boldsymbol{\alpha}}_n,\,{\boldsymbol{\pi}})$ occurring in the $n$th step of the MCMC simulation via the Metropolis algorithm,
  • if the simulated distribution ${\boldsymbol{\pi}}$ satisfies the following conditions.
• Namely we assume
  • that $\pi_{\mathbf{x}}\not=\pi_{{\mathbf{x}}^\prime}$ for arbitrary ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ such that ${\mathbf{x}}\not={\mathbf{x}}^\prime$,
  • and that the states ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\in E$ are ordered such that $\pi_{{\mathbf{x}}_1}>\ldots>\pi_{{\mathbf{x}}_\ell}$.
• We may thus (w.l.o.g.) return to the notation used in Section 2.3 and identify the states ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\in E$ and the first $\ell$ natural numbers, i.e. $E=\{1,\ldots,\ell\}$.
• The probabilities $\pi_i\;(=\pi_{{\mathbf{x}}_i})$ can thus be written in the following way:

  $$\pi_i=\frac{b^{h(i)}}{z(b)}\;,\qquad\forall\, i=1,\ldots,\ell\,,$$ (56)

  
  
  • where $h:\{1,\ldots,\ell\}\to(1,\infty)$ is a monotonically increasing function,
  • and $b\in(0,1)$ is chosen such that for a certain constant $c\ge 1$

    $$h(i+1)-h(i)\ge c\,,\qquad\forall\, i=1,\ldots,\ell-1$$ (57)

    
    

  • and $z(b)=\sum_{i=1}^\ell b^{h(i)}$ is an (in general unknown) factor.
• Furthermore, the definition of a Metropolis algorithm for the MCMC simulation of ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ requires
  • that the basis $b$ and the differences $h(i+1)-h(i)$ are known for all $i=1,\ldots,\ell-1$,
  • i.e. in particular that the quotients $\pi_{i+1}/\pi_i$ are known for all $i=1,\ldots,\ell-1$.
• Let the matrix ${\mathbf{Q}}=(q_{ij})$ of the ,,potential'' transitions $i\to j$ be given by

  $$q_{ij}=\left\{\begin{array}{ll} \displaystyle\frac{1}{2} &\mbox{i... ...,\ell-1$\ and $j=i-1,\,i+1$,}\\ [3\jot] 0\,, & \mbox{else.} \end{array}\right.$$ (58)

  
  
  • Let the acceptance probability $a_{ij}$ be defined as in (53), i.e.
    $$a_{ij}=\min\Bigl\{1,\;\frac{\pi_j\, q_{ji}}{\pi_i q_{ij}}\Bigr\}=... ...r\}\,,\qquad\forall\,i,j\in \{1,\ldots,\ell\}\;\mbox{where $q_{ij}=q_{ji}>0$.}$$

  • By (56) and (58) the entries $p_{ij}=q_{ij}a_{ij}$ of the transition matrix ${\mathbf{P}}=(p_{ij})$ for the MCMC simulation are thus be given as

    $$p_{11}=1-\;\frac{b^{h(2)-h(1)}}{2}\;,\qquad p_{12}=\frac{b^{h(2)-h(1)}}{2}\;,\qquad p_{\ell,\ell-1}=p_{\ell\ell}=\;\frac{1}{2}$$ (59)

    
    
    and for $i=2,\ldots,\ell-1$

    $$p_{i,i-1}=\frac{1}{2}\;,\qquad p_{i,i+1}=\frac{b^{h(i+1)-h(i)}}{2}\;,\qquad p_{ii}=1-p_{i,i-1}-p_{i,i+1}\,.$$ (60)

    
    

Theorem 3.15   $\;$ The second largest eigenvalue $\lambda _2$ of the transition matrix ${\mathbf{P}}=(p_{ij})$ defined by $(\ref{ein.tra.ein})$- $(\ref{ein.tra.zwe})$ has the following upper bound

$$\lambda_2\le 1-\;\frac{(1-b^{c/2})^2}{2}\;.$$ (61)

Proof

 

• By Theorem 3.14 the pair $({\mathbf{P}},{\boldsymbol{\pi}})$ is reversible.
• Hence, Rayleigh's theorem (see Theorem 2.17) yields the following representation formula

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

  
  
  • where $\mathbb{R}^\ell_{\not=}=\bigl\{{\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell:\;$   $\mbox{$x_i\not=x_j$\ for somer $i,j\in E$}$$\bigr\}$ denotes the subset of vectors in $\mathbb{R}^\ell$ whose components are not all equal,
  • ${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})=\Vert{\mathbf{x}}\Vert^2_{\boldsymbol{\pi}}-({\mathbf{x}})^2_{\boldsymbol{\pi}}$ is the variance of the components of ${\mathbf{x}}$ with respect to ${\boldsymbol{\pi}}$
  • and $D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\bigl(({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}$ denotes the Dirichlet form of the reversible pair $({\mathbf{P}},{\boldsymbol{\pi}})$.
• Due to (62) it is sufficient to show that

  $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})\le a D_{({\mathbf{P}... ...}})}({\mathbf{x}},{\mathbf{x}})\,,\qquad\forall\,{\mathbf{x}}\in\mathbb{R}^\ell$$ (63)

  
  
  for some constant $a$ such that

  $$0<a\le\frac{2}{(1-b^{c/2})^2}\;.$$ (64)

  
  
  • Similar to the proof of Theorem 2.18 we obtain by copying the notation that for all $\theta\in(0,1)$
    

    $$2\,{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) = \sum\limits_{i,j\in E} (x_i-x_j)^2\pi_i\pi_j$$

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

    $$\le \sum\limits_{i,j\in E}\Biggl( \sum\limits_{e\in\gamma_{ij}}Q(e)^{... ...m\limits_{e\in\gamma_{ij}} \;\frac{1}{Q(e)^{2\theta}}\;\Biggr) \; \pi_i\pi_j\,,$$

    
    
    where the ,,edge probability'' $Q(e)=\pi_{e^-}\,p_{e^-e^+}$ is assigned to the ,,directed'' edge $e=(e^{-},e^{+})$ and $\gamma_{ij}$ denotes the ,,path'' from $i$ to $j$.
  • Using the notation $\vert\gamma_{ij}\vert _\theta=\sum_{e\in\gamma_{ij}} \;Q(e)^{-2\theta}$ we thus obtain
    

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

    $$= \sum\limits_{e\in\mathcal{E}}(x_{e^-}-x_{e^+})^2Q(e)Q(e)^{2\theta-1} \sum\limits_{\gamma_{ij}\ni e}\pi_i\pi_j\vert\gamma_{ij}\vert _\theta\,.$$

    
    

  • This shows (63) for

    $$a=\max\limits_{e\in\mathcal{E}}\Bigl\{Q(e)^{2\theta-1} \sum\limits_{\gamma_{ij}\ni e}\pi_i\pi_j\vert\gamma_{ij}\vert _\theta\Bigr\}\,,$$ (65)

    
    
    as we showed in Lemma 2.8 that
    $$2\,D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\sum\limits_{e\in\mathcal{E}}(x_{e^-}-x_{e^+})^2Q(e)\,.$$

• It is left to show that the constant $a$ considered in (65) satisfies the inequality (64).
  • For this purpose we choose the path $\gamma_{ij}=(i,i+1,\ldots,j-1,j)$ for each pair $i,j\in E$ such that $i<j$.
  • Then (56) and (59)-(60) imply
    $$Q(i,i+1)=\pi_i p_{i,i+1}=\frac{b^{h(i)}}{z(b)}\;\frac{b^{h(i+1)-h(i)}}{2}=\frac{\pi_{i+1}}{2}\;.$$

  • Thus, the reversibility of the pair $({\mathbf{P}},{\boldsymbol{\pi}})$ shown in Theorem  3.14 yields
    $$Q(i+1,i)=Q(i,i+1)=\frac{\pi_{i+1}}{2}\;.$$

  • Because of (56) and (57) we obtain for arbitrary $i,j\in E$ such that $i<j$
    

    $$\vert\gamma_{ij}\vert _\theta = \Biggl(\Bigl(\frac{\pi_{i+1}}{\pi_j}\Bigr)^{-2\theta}+\ldots+ \Bi... ...-i-1)c\theta}+\ldots+b^{2c\theta}+1\Bigr)\Bigl(\frac{\pi_j}{2}\Bigr)^{-2\theta}$$

    $$\le \frac{2^{2\theta}\pi_j^{-2\theta}}{1-b^{2c\theta}}\;.$$

    
    

  • Moreover, all edges $e\in\mathcal{E}$ are of the form $e=(i,i+1)$ or $e=(i,i-1)$, as for the entries $p_{ij}$ of the transition matrix ${\mathbf{P}}=(p_{ij})$ defined by (58)-(60) we have $p_{ij}=0$ if $\vert i-j\vert>1$.
• Thus, for $\theta<1/2$,
  

  $$a = \max\limits_{e\in\mathcal{E}}\Bigl\{Q(e)^{2\theta-1} \sum\limits_{\gamma_{ij}\ni e}\pi_i\pi_j\vert\gamma_{ij}\vert _\theta\Bigr\}$$

  $$\le \max\limits_{k=1,\ldots,\ell-1}\;\Biggl\{Q(k,k+1)^{2\theta-1} \su... ... j\le\ell}\;2^{2\theta}\; \frac{\pi_i\pi_j^{1-2\theta}}{1-b^{2c\theta}}\Biggr\}$$

  $$\le \frac{2}{({1-b^{2c\theta}})(1-b^{c(1-2\theta)})}\;,$$

  
  
  as $Q(k,k+1)^{2\theta-1}=\bigl(\pi_{k+1}/2\bigr)^{2\theta-1}$ and $\sum_{1\le i\le k}\pi_i\le 1$ and hence
  $$\sum\limits_{k+1\le j\le\ell}\pi_j^{1-2\theta} =\Biggl(\Bigl( \fr... ...pi_{k+1}^{1-2\theta} \le \;\frac{\pi_{k+1}^{1-2\theta}}{1-b^{c(1-2\theta)}}\;.$$

• For $\theta=1/4$ we obtain the estimate (64).
  
  $\Box$

The following lemma will turn out to be useful in order to derive a lower bound for the smallest eigenvalue $\lambda _\ell$ of the transition matrix ${\mathbf{P}}=(p_{ij})$ defined by $(\ref{ein.tra.ein})$- $(\ref{ein.tra.zwe})$.

Lemma 3.1    

• Let ${\mathbf{A}}=(a_{ij})$ be an arbitrary $\ell\times\ell$-matrix and for all $i=1,\ldots,\ell$ let $r_i=\sum_{j:\,1\le j\le\ell,\,j\not= i}\vert a_{ij}\vert$.
• Let $\lambda$ be an arbitrary eigenvalue of ${\mathbf{A}}$, let ${\boldsymbol{\phi}}=(\phi_1,\ldots,\phi_\ell)^\top\not={\mathbf{o}}$ be a left eigenvector corresponding to $\lambda$ and let $k$ be the number of the component $\phi_k$ where
  $$\vert\phi_k\vert=\max\limits_{i=1,\ldots,\ell} \vert\phi_i\vert>0\,.$$

• Then,

  $$\vert\lambda-a_{kk}\vert\le r_k\,.$$ (66)

  
  

Proof

 

• By definition of $\lambda$ and ${\boldsymbol{\phi}}$ we have ${\mathbf{A}}{\boldsymbol{\phi}}=\lambda{\boldsymbol{\phi}}$. In particular
  $$\sum\limits_{j=1}^\ell a_{kj}\phi_j=\lambda\,\phi_k$$   and$$\qquad (\lambda-a_{kk})\phi_k=\sum\limits_{j:\,1\le j\le\ell,\,j\not= k} a_{kj}\phi_j\,.$$

• This implies
  $$\vert\lambda-a_{kk}\vert \vert\phi_k\vert\le\sum\limits_{j:\,1\le... ...e r_k\vert\phi_k\vert\qquad\mbox{and}\qquad \vert\lambda-a_{kk}\vert\le r_k\,.$$
  
   
    $\Box$
  
  
  

Theorem 3.16   $\;$ The smallest eigenvalue $\lambda _\ell$ of the transition matrix ${\mathbf{P}}=(p_{ij})$ defined by $(\ref{ein.tra.ein})$- $(\ref{ein.tra.zwe})$ has the following lower bound

$$\lambda_\ell\ge -b^c\,.$$ (67)

Proof

 

• By Lemma 3.1 applied to ${\mathbf{A}}={\mathbf{P}}$ (and to the index $k$ determined for $\lambda _\ell$)
  $$\vert\lambda_\ell-p_{kk}\vert\le \sum\limits_{j:\,1\le j\le\ell,\... ...}p_{kj}=1-p_{kk}\qquad\mbox{$\Rightarrow$}\qquad \lambda_\ell\ge -1+2p_{kk}\,.$$

• Thus, taking into account (59)-(60) we derive
  $$\lambda_\ell\ge -1+2\min\limits_{i=1,\ldots,\ell}p_{ii}\ge -1+2\Bigl(1-\frac{1}{2}-\frac{b^c}{2}\Bigr)=-b^c\,.$$
  
   
    $\Box$
  
  
  

Remark

$\;$ Summarizing the results of Theorems 3.15 and 3.16 we have shown that

$$\vert\theta_2\vert=\max\{\lambda_2,\vert\lambda_\ell\vert\}\le \m... ...{ 1-\;\frac{(1-b^{c/2})^2}{2}\;,\,b^c\Bigr\} =1-\;\frac{(1-b^{c/2})^2}{2}\; \,.$$ (68)