Alternative Estimate for the Rate of Convergence; $\chi ^2$ Contrast

Based on the multiplicative reversible version ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ of the ergodic (but not necessarily reversible) transition matrix ${\mathbf{P}}$ we will now deduce an alternative estimate for the rate of convergence ${\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\to{\boldsymbol{\pi}}^\top$ for $n\to\infty$; see Theorem 2.16.

The following abbreviations and lemmata will turn out to be useful in the proof of Theorem 2.16.

• Let $\mathcal{L}(E)$ denote the family of all functions
  • defined on $E$ and mapping into the real line $\mathbb{R}$
  • and let ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ be an arbitrary positive probability function from $\mathcal{L}(E)$, i.e. $\pi_i>0$ for all $i\in E$ and $\sum_{i=1}^\ell\pi_i=1$.
• For arbitrary vectors ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathcal{L}(E)$ and ${\mathbf{y}}=(y_1,\ldots,y_\ell)^\top\in\mathcal{L}(E)$ we denote by $({\mathbf{x}},{\mathbf{y}})_{\boldsymbol{\pi}}$ the inner product

  $$({\mathbf{x}},{\mathbf{y}})_{\boldsymbol{\pi}}=\sum\limits_{i=1}^\ell x_iy_i\pi_i$$ (103)

  
  
  and by $\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}$ the induced norm, i.e.,
  $$\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}= \sqrt{\sum\limits_{i=1}^\ell x_i^2\pi_i}\;.$$

• The terms ( ${\boldsymbol{\pi}}$-weighted) mean $({\mathbf{x}})_{\boldsymbol{\pi}}$ and variance ${\rm Var\,}_\pi({\mathbf{x}})$ of ${\mathbf{x}}\in\mathcal{L}(E)$ will be used to denote the quantities

  $$({\mathbf{x}})_{\boldsymbol{\pi}}=\sum\limits_{i=1}^\ell x_i\pi_i\qquad\Bigl(=({\mathbf{x}},{{\mathbf{e}}})_{\boldsymbol{\pi}}\Bigr)$$ (104)

  
  
  and

  $${\rm Var\,}_\pi({\mathbf{x}})=\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2-({\mathbf{x}})_{\boldsymbol{\pi}}^2\,,$$ (105)

  
  
  respectively.

Lemma 2.6   $\;$ For all ${\mathbf{x}}\in\mathcal{L}(E)$, it holds that

$${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})={\rm Var\,}_{\boldsy... ...{\mathbf{I}}-{\mathbf{M}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}\,.$$ (106)

Proof

 

• Introducing the notation $\widehat{\mathbf{x}}={\mathbf{x}}-({\mathbf{x}})_{\boldsymbol{\pi}}{{\mathbf{e}}}$ we obtain that $(\widehat{\mathbf{x}})_{\boldsymbol{\pi}}=0$ and
  $$(\widetilde{\mathbf{P}}\widehat{\mathbf{x}})_{\boldsymbol{\pi}}=\... ...\sum\limits_{i,j=1}^\ell \pi_jp_{ji}x_j-({\mathbf{x}})_{\boldsymbol{\pi}}=0\,,$$
  where the last but one equality follows from the definition (99) of the matrix $\widetilde{\mathbf{P}}$.
• This implies

  $$\Vert\widehat{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2={\rm Var\,}_... ...ymbol{\pi}}(\widehat{\mathbf{x}}) ={\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) \qquad \Vert\widetilde{\mathbf{P}}\widehat{\mathbf{x}}\Vert _{\bo... ...hbf{x}})= {\rm Var\,}_{\boldsymbol{\pi}}(\widetilde{\mathbf{P}}{\mathbf{x}})\,.$$ (107)

  
  

• On the other hand
  

  $$\Vert\widetilde{\mathbf{P}}\widehat{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2 = \bigl(\widetilde{\mathbf{P}}\widehat{\mathbf{x}}, \widetilde{\mat... ...igl(\sum\limits_{k=1}^\ell \widetilde p_{ik}\widehat{\mathbf{x}}_k\Bigr)^2\pi_i$$

  $$= \sum\limits_{i=1}^\ell \sum\limits_{j,k=1}^\ell \widetilde p_{ij}... ... =\frac{\pi_k p_{ki}}{\pi_i}} \widehat{\mathbf{x}}_j\widehat{\mathbf{x}}_k\pi_i$$

  $$= \sum\limits_{k=1}^\ell\underbrace{\displaystyle\sum\limits_{j=1}^... ...=({\mathbf{P}}\widetilde{\mathbf{P}}{\mathbf{x}})_k}\widehat{\mathbf{x}}_k\pi_k$$

  $$= \bigl({\mathbf{P}}\widetilde{\mathbf{P}}\widehat{\mathbf{x}}, \wi... ...{\mathbf{M}}\widehat{\mathbf{x}}, \widehat{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}$$

  
  
  and thus
  $$\Vert\widehat{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2-\Vert\wideti... ...mathbf{I}}-{\mathbf{M}}){\mathbf{x}}, {\mathbf{x}}\bigr)_{\boldsymbol{\pi}}\,,$$
  as ${\mathbf{M}}$ is a stochastic matrix such that ${\boldsymbol{\pi}}^\top{\mathbf{M}}={\boldsymbol{\pi}}^\top$ and therefore $({\mathbf{I}}-{\mathbf{M}}){{\mathbf{e}}}={\,{\bf0}}$ and
  $$\bigl(({\mathbf{I}}-{\mathbf{M}}){\mathbf{x}},\,{{\mathbf{e}}}\bi... ..._{j=1}^\ell x_j\underbrace{\sum\limits_{i=1}^\ell \pi_i m_{ij}}_{=\pi_j} =0\,.$$

• Taking into account (107) this shows the validity of (106).
  
  $\Box$

We introduce the following notions.

• Let $E=\{1,\ldots,\ell\}$, let ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ and ${\boldsymbol{\beta}}=(\beta_1,\ldots,\beta_\ell)^\top$ be arbitrary probability distributions on $E$, and let

  $$d_{\rm TV}({\boldsymbol{\alpha}},{\boldsymbol{\beta}})=\frac{1}{2}\;\sum\limits_{i\in E}\vert\alpha_i-\beta_i\vert\,,$$ (108)

  
  
  i.e., the distance $d_{\rm TV}({\boldsymbol{\alpha}},{\boldsymbol{\beta}})$ between ${\boldsymbol{\alpha}}$ and ${\boldsymbol{\beta}}$ is expressed via the total variation

  $$\vert{\boldsymbol{\alpha}}-{\boldsymbol{\beta}}\vert= \sum\limits_{i\in E}\vert\alpha_i-\beta_i\vert$$ (109)

  
  
  of the ,,signed measure'' ${\boldsymbol{\alpha}}-{\boldsymbol{\beta}}$.
• If $\beta_i>0$ for all $i\in E$ we also consider the term

  $$\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\beta}})=\sum\limits_{i\in E} \;\frac{(\alpha_i-\beta_i)^2}{\beta_i}$$ (110)

  
  
  which is called the $\chi ^2$-contrast of ${\boldsymbol{\alpha}}$ with respect to ${\boldsymbol{\beta}}$.

The distance $d_{\rm TV}({\boldsymbol{\alpha}},{\boldsymbol{\beta}})$ between ${\boldsymbol{\alpha}}$ and ${\boldsymbol{\beta}}$ can be estimated via the $\chi ^2$-contrast $\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\beta}})$ of ${\boldsymbol{\alpha}}$ with respect to ${\boldsymbol{\beta}}$ as follows.

Lemma 2.7   $\;$ If $\beta_i>0$ for all $i\in E$, then

$$d_{\rm TV}^2({\boldsymbol{\alpha}},{\boldsymbol{\beta}})\le \frac{1}{4}\;\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\beta}})\,.$$ (111)

Proof

 

• Taking into account that $\sum_{i\in E}\beta_i=1$, an application of the Cauchy-Schwarz inequality yields
  $$\Bigl(\sum\limits_{i\in E}\vert\alpha_i-\beta_i\vert\Bigr)^2 = \B... ..._i}\Bigr)^2 \le \sum\limits_{i\in E}\frac{1}{\beta_i}\;(\alpha_i-\beta_i)^2\,.$$

• This implies the assertion of the lemma.
  
  $\Box$

The rate of convergence ${\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\to{\boldsymbol{\pi}}^\top$ for $n\to\infty$ can now be estimated based on

• the second largest eigenvalue $\theta_{{\mathbf{M}},2}$ of the multiplicative reversible version ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ of the (ergodic) transition matrix ${\mathbf{P}}$
• and the $\chi ^2$ contrast $\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\pi}})$ of the initial distribution ${\boldsymbol{\alpha}}$ with respect to the stationary limit distribution ${\boldsymbol{\pi}}$.

Theorem 2.16   $\;$ For any initial distribution ${\boldsymbol{\alpha}}$ and for all $n\in\mathbb{N}$,

$$d^2_{\rm TV} \bigl(\bigl({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n... ...({\boldsymbol{\alpha}};{\boldsymbol{\pi}})}{4}\; \;\theta^n_{{\mathbf{M}},2}\,.$$ (112)

Proof

 

• Let ${\boldsymbol{\rho}}_n=(\rho_{n1},\ldots,\rho_{n\ell})^\top$ where $\rho_{ni}=({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n)_i/\pi_i$.
  • Then for all $i\in E$
    $$\sum\limits_{k=1}^\ell\frac{\pi_k p_{ki}}{\pi_i}\;\frac{({\boldsy... ..._k}{\pi_k}\;=\; \frac{({\boldsymbol{\alpha}}^\top{\mathbf{P}}^{n+1})_i}{\pi_i}$$
    and thus
    $$\widetilde{\mathbf{P}}{\boldsymbol{\rho}}_n={\boldsymbol{\rho}}_{n+1}\,.$$

  • Moreover, by definition (110) of the $\chi ^2$ contrast $\chi_n^2=\chi^2\bigl(\bigl({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\bigr)^\top;{\boldsymbol{\pi}}\bigr)$ of $\bigl({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\bigr)^\top$ with respect to ${\boldsymbol{\pi}}$ we obtain
    

    $$\chi^2_n = \sum\limits_{i=1}^\ell\;\frac{\bigl(({\boldsymbol{\alpha}}^\top{\... ...Bigl(\frac{({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n)_i} {\pi_i}-1\Bigr)^2\pi_i$$

    $$= \sum\limits_{i=1}^\ell \bigl(\rho_{ni}-({\boldsymbol{\rho}}_n)_{\... ...l{\pi}}\bigr)^2\pi_i = {\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)\,,$$

    
    
    i.e.,

    $$\chi^2_n={\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)\,.$$ (113)

    
    

  • Now the identity (106) derived in Lemma 2.6 yields

    $$\chi^2_n=\chi^2_{n+1}+\bigl(({\mathbf{I}}-{\mathbf{M}}){\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n\Bigr)_{\boldsymbol{\pi}}\,.$$ (114)

    
    

• On the other hand the spectral representation (101) of ${\mathbf{M}}$ derived in Theorem 2.15 implies
  

  $$\bigl(({\mathbf{I}}-{\mathbf{M}}){\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n\Bigr)_{\boldsymbol{\pi}} = ({\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}-({\mathbf{M}}{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}$$

  $$= ({\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}... ...{\psi}}_i^\top{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}$$

  $$= ({\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}... ...si}}_i^\top{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}\,,$$

  
  
  as $\theta_{{\mathbf{M}},1}=1$, ${\boldsymbol{\phi}}_1={{\mathbf{e}}}$ and ${\boldsymbol{\psi}}_1^\top={\boldsymbol{\pi}}^\top$ and therefore
  $$\bigl({\boldsymbol{\phi}}_1{\boldsymbol{\psi}}_1^\top{\boldsymbol... ...bol{\pi}}=1 \qquad\Bigl(=({\boldsymbol{\rho}}_n)^2_{\boldsymbol{\pi}}\Bigr)\,.$$
  • As the eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ von ${\mathbf{M}}$ defined in (100) are a basis of $\mathbb{R}^\ell$ there is a (uniquely determined) vector $\bigl(\rho_{n1}^{\rm (r)},\ldots,\rho_{n\ell}^{\rm (r)}\bigr)^\top\in\mathbb{R}^\ell$, such that ${\boldsymbol{\rho}}_n=\sum_{i=1}^\ell \rho_{ni}^{\rm (r)}{\boldsymbol{\phi}}_i$.
  • Moreover, in (102) we have shown that ${\boldsymbol{\psi}}_i^\top{\boldsymbol{\rho}}_n=\rho_{ni}^{\rm (r)}$. As ${\boldsymbol{\psi}}_1^\top={\boldsymbol{\pi}}^\top$ we can conclude ${\boldsymbol{\psi}}_1^\top{\boldsymbol{\rho}}_n=1$.
  • Furthermore, as ${\boldsymbol{\phi}}_i={\mathbf{D}}^{-1}{\boldsymbol{\phi}}_i^*$ and ${\boldsymbol{\psi}}_i={\mathbf{D}}{\boldsymbol{\phi}}_i^*$ for all $i\in E$ we obtain
    

    $$\sum\limits_{i=2}^\ell \theta_{{\mathbf{M}},i}({\boldsymbol{\phi}... ...{\psi}}_i^\top{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}} = \sum\limits_{i=2}^\ell\sum\limits_{j=1}^\ell \theta_{{\mathbf{M}}... ...j}^{\rm (r)} ({\boldsymbol{\phi}}_i,\,{\boldsymbol{\phi}}_j)_{\boldsymbol{\pi}}$$

    $$= \sum\limits_{i=2}^\ell\sum\limits_{j=1}^\ell \theta_{{\mathbf{M}}... ...athbf{D}}^{-1}{\boldsymbol{\phi}}^*_j \bigr)_{\boldsymbol{\pi}}}_{=\delta_i(j)}$$

    $$= \sum\limits_{i=2}^\ell \theta_{{\mathbf{M}},i}\bigl(\rho_{ni}^{\rm (r)}\bigr)^2$$

    $$\le \theta_{{\mathbf{M}},2}\sum\limits_{i=2}^\ell \bigl(\rho_{ni}^{\r... ...^{\rm (r)}}_{ ={\boldsymbol{\psi}}_1^\top{\boldsymbol{\rho}}_n=1}\bigr)^2\Bigr)$$

    $$= \theta_{{\mathbf{M}},2}\Biggl(\sum\limits_{i=1}^\ell\sum\limits_{... ...mbol{\pi}}-1\Bigr)}_{={\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)}\,.$$

    
    

• Summarizing our results we have seen that
  $$\bigl(({\mathbf{I}}-{\mathbf{M}}){\boldsymbol{\rho}}_n,\,{\boldsy... ...{\mathbf{M}},2}\bigr) {\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)\,.$$
  • Because of (113) and (114) this implies
    $$\chi^2_n\ge\chi^2_{n+1}+\bigl(1-\theta_{{\mathbf{M}},2}\bigr)\chi^2_n$$   and$$\qquad \chi^2_{n+1}\le\theta_{{\mathbf{M}},2}\;\chi^2_n\,.$$

  • Thus, we have shown that $\chi^2_n\le\theta^n_{{\mathbf{M}},2}\;\chi^2_0$ for all $n\ge 1$ and, consequently, the assertion follows from Lemma 2.7.
    
    $\Box$