Estimates for the Rate of Convergence; Perron-Frobenius-Theorem

• Recall:
  • If $\{X_n\}$ is a Markov chain whose 1-step transition matrix ${\mathbf{P}}$ has only strictly positive entries $p_{ij}$,
  • then the geometric bound for the rate of convergence to the limit distribution ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ derived in (40) is given as follows:

    $$\max\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert= O((1-\ell a)^n)\,,$$ (43)

    
    
    where $a=\min_{i,j\in E}p_{ij}> 0$.
• Whenever the minimum $a$ of the entries $p_{ij}$ of the transition matrix ${\mathbf{P}}$ is close to 0 the bound in (43) is not very useful.

• However, in some cases the basis $1-\ell a$ of the convergence estimate (43) can be improved.

Example

$\;$ (Weather Forecast)

• Let $E=\{1,2\}$ and
  $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)\;,$$   $$\mbox{where $0<p,p^\prime<1$.}$$$$$$

• In Section  2.2.1 we showed that
  • the $n$-step transition matrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ is given by
    $${\mathbf{P}}^n=\frac{1}{p+p^\prime} \left(\begin{array}{cc} p^\pr... ...me} \left(\begin{array}{cc} p & -p\\ -p^\prime & p^\prime \end{array}\right)$$

  • and thus
    $$\Bigl({\mathbf{P}}^\infty=\Bigr)\quad \displaystyle \lim_{n... ...rray}{cc} p^\prime & p \\ p^\prime & p \end{array}\right)\;.$$

  • Consequently

    $${\mathbf{P}}^n-{\mathbf{P}}^\infty=\frac{(1-p-p^\prime)^n}{p+p^\p... ...& p^\prime \end{array}\right)\qquad\Bigl(=O(\vert 1-p-p^\prime\vert^n)\Bigr)\,,$$ (44)

    
    
    where $p+p^\prime>2a=2\min_{i,j\in E}p_{ij}$ and hence $\vert 1-p-p^\prime\vert<1-2a$ if $p\not= p^\prime$.
• Remarks
  • The basis $\vert\theta_2\vert=\vert 1-p-p^\prime\vert$ of the rate of convergence in (44) is the absolute value of the second largest eigenvalue $\theta_2$ of the transition matrix ${\mathbf{P}}$,
  • as the characteristic equation
    $$\Bigl(\det({\mathbf{P}}-\theta{\mathbf{I}})=\Bigr)\quad (1-p-\theta)(1-p^\prime-\theta)-pp^\prime=0$$
    of ${\mathbf{P}}$ has the two solutions $\theta_1=1$ and $\theta_2=1-p-p^\prime$.

In general geometric estimates of the form (44) for the rate of convergence can be derived by means of the following so-called Perron-Frobenius theorem for quasi-positive matrices.

Theorem 2.6    

• Let ${\mathbf{A}}$ be a quasi-positive $\ell\times\ell$ matrix with eigenvalues $\theta_1,\ldots,\theta_\ell$ such that $\vert\theta_1\vert\ge\ldots\ge\vert\theta_\ell\vert$.
• Then the following holds:

  (a)

  The eigenvalue $\theta_1$ is real and positive.

  (b)

  $\theta_1>\vert\theta_i\vert$ for all $i=2,\ldots,\ell$,

  (c)

  The right and left eigenvectors ${\boldsymbol{\phi}}_1$ and ${\boldsymbol{\psi}}_1$ of $\theta_1$ are uniquely determined up to a constant factor and can be chosen such that all components of ${\boldsymbol{\phi}}_1$ and ${\boldsymbol{\psi}}_1$ are positive.

A proof of Theorem 2.6 can be found in Chapter 1 of E. Seneta (1981) Non-Negative Matrices and Markov Chains, Springer, New York.

Corollary 2.3   $\;$ Let ${\mathbf{P}}$ be a quasi-positive transition matrix. Then

• $\theta_1=1,{\boldsymbol{\phi}}_1={\mathbf{e}}$ and ${\boldsymbol{\psi}}_1={\boldsymbol{\pi}}$, where ${\mathbf{e}}=(1,\ldots,1)^\top$ and ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$.
• $\vert\theta_i\vert<1$ for all $i=2,\ldots,\ell$.

Proof

 

• As ${\mathbf{P}}$ is a stochastic matrix
  • obviously ${\mathbf{P}}{\mathbf{e}}={\mathbf{e}}$ and (41) implies ${\boldsymbol{\pi}}^\top{\mathbf{P}}={\boldsymbol{\pi}}^\top$.
  • Thus $1$ is an eigenvalue of ${\mathbf{P}}$ and ${\mathbf{e}}$ and ${\boldsymbol{\pi}}$ are right and left eigenvectors of this eigenvalue, respectively.
• Let now be
  • $\theta$ an arbitrary eigenvalue of ${\mathbf{P}}$ and let ${\boldsymbol{\phi}}=(\phi_1,\ldots,\phi_\ell)^\top$ an eigenvector corresponding to $\theta$.
  • By definition (27) of $\theta$ and ${\boldsymbol{\phi}}$
    $$\vert\theta\vert\, \vert\phi_i\vert\le\sum_{j=1}^\ell p_{ij}\vert\phi_j\vert\le\max_{j\in E} \vert\phi_j\vert\,, \qquad\forall\, i\in E\,.$$

  • Consequently $\vert\theta\vert\le 1$ and therefore $\theta_1=1$ is the largest eigenvalue of ${\mathbf{P}}$.
• Theorem 2.6 now implies $\vert\theta_i\vert<1$ for $i=2,\ldots,\ell$.
  
  $\Box$

Corollary 2.3 yields the following geometric convergence estimate.

Corollary 2.4   $\;$ Let ${\mathbf{P}}$ be a quasi-positive transition matrix such that all eigenvalues $\theta_1,\ldots,\theta_\ell$ of ${\mathbf{P}}$ are pairwise distinct. Then

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

Proof

 

• Corollary 2.3 implies

  $$\lim_{n\to\infty}\sum_{i=2}^\ell\theta_i^n{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top={\bf0}\,,$$ (46)

  
  
  as $\vert\theta_i\vert<1$ for all $i=2,\ldots,\ell$.
• Furthermore, Corollary 2.3 implies $\theta_1=1$ as well as ${\boldsymbol{\phi}}_1=(1,\ldots,1)^\top$ and ${\boldsymbol{\psi}}_1={\boldsymbol{\pi}}$ being the right and left eigenvectors of $\theta_1$, respectively.
• Taking into account the spectral representation (30) of ${\mathbf{P}}^n$, i.e.,
  $${\mathbf{P}}^n= \sum_{i=1}^\ell\theta^n_i{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top\,,$$
  it is easy to see that
  $${\mathbf{P}}^n-\left(\begin{array}{c} {\boldsymbol{\pi}}^\top\\ ... ... = \sum_{i=2}^\ell\theta^n_i{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top\,.$$

• As ${\boldsymbol{\alpha}}_n^\top={\boldsymbol{\alpha}}^\top {\mathbf{P}}^n$ (see Theorem 2.3) this together with (46) shows (45).
  
  $\Box$

Example

$\;$ (Reaching a Consensus)
see C. Hesse (2003) Angewandte Wahrscheinlichkeitstheorie. Vieweg, Braunschweig, p. 349

• A committee consisting of $\ell$ members has the mandate to project a certain (economical) parameter $\mu\in\mathbb{R}$, one could think of the German Council of Economic Experts projecting economic growth for the next year.
  • In a first step each of the $\ell$ experts gives a personal projection for $\mu$, where the single projection results are denoted by $\widehat\mu^{(0)}_1,\ldots,\widehat\mu^{(0)}_\ell$.
  • What could be a method for the experts to settle on a common projection, i.e. reach a consensus?
  • A simple approach would be to calculate the arithmetic mean $(\widehat\mu^{(0)}_1+\ldots+\widehat\mu^{(0)}_\ell)/\ell$, thus ignoring the different levels of expertise within the group.
• Alternatively, every committee member could modify his own projection based on the projections by his $\ell-1$ colleagues and his personal assessment of their authors expertise.
  • For arbitrary $i,j\in\{1,\ldots,\ell\}$ the expert $i$ attributes the ,,trust probability'' $p_{ij}$ to the expert $j$ such that
    $$p_{ij}>0$$   and$$\qquad\sum\limits_{j=1}^\ell p_{ij}=1\,,\qquad\forall\, i,j\in\{1,\ldots,\ell\}\,$$

  • and expert $i$ modifies his original projection $\widehat\mu_i^{(0)}$ replacing it by
    $$\widehat\mu_i^{(1)}=\sum\limits_{j=1}^\ell p_{ij}\widehat\mu_j^{(0)}\,.$$

  • In most cases the modified projections $\widehat\mu^{(1)}_1,\ldots,\widehat\mu^{(1)}_\ell$ will still be different from each other. Therefore the procedure is repeated until the differences are sufficiently small.
• Theorem 2.4 ensures
  • that this can be achieved if the modification procedure is repeated often enough,
  • as according to Theorem 2.4 the limits

    $$\lim\limits_{n\to\infty}\widehat\mu^{(n)}_i=\sum\limits_{j=1}^\ell \pi_j\widehat\mu_j^{(0)}$$ (47)

    
    
    exist and do not depend on $i$,
  • where the vector ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ of the limits $\pi_j=\lim_{n\to\infty} p^{(n)}_{ij}$ is the (uniquely determined) solution of the linear equation system (41), i.e. ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ with ${\mathbf{P}}=(p_{ij})$.
• The equality (47) can be seen as follows:
  

  $$\lim\limits_{n\to\infty}\widehat\mu^{(n)}_i = \lim\limits_{n\to\infty} \sum\limits_{j=1}^\ell p_{ij}\;\widehat\... ...lim\limits_{n\to\infty}\sum\limits_{j=1}^\ell p^{(n)}_{ij}\;\widehat\mu_j^{(0)}$$

  $$= \sum\limits_{j=1}^\ell\lim\limits_{n\to\infty} p^{(n)}_{ij}\;\widehat\mu_j^{(0)} = \sum\limits_{j=1}^\ell \pi_j\;\widehat\mu_j^{(0)}\,.$$

  
  

• The consensus, i.e. the common projection of the unknown parameter $\mu$, reached by the committee is given by

  $$\widehat\mu=\sum\limits_{j=1}^\ell \pi_j\widehat\mu_j^{(0)}\,.$$ (48)

  
  

Remarks

 

• For large $\ell$ the algebraic solution of the linear equation system (41) can be difficult.
• In this case the estimates for the rate of convergence in (47) become relevant for the practical implementation of the method to reach a consensus described in (47).
• We consider the following numerical example.
  • Let $\ell=3$ and

    $${\mathbf{P}}=\left(\begin{array}{ccc}\displaystyle \frac{2}{6} & ... ...{8} & \displaystyle\frac{1}{8} & \displaystyle\frac{5}{8} \end{array}\right)\;.$$ (49)

    
    

  • The entries of this stochastic matrix imply that the third expert has a particularly high reputation among his colleagues.
  • The solution ${\boldsymbol{\pi}}=(\pi_1,\pi_2,\pi_3)^\top$ of the corresponding linear equation system (41) is given by
    $$\pi_1=\frac{21}{77}\;,\qquad\pi_2=\frac{12}{77}\;,\qquad \pi_3=\frac{44}{77}\;,$$
    i.e. the projection $\widehat\mu_3^{(0)}$ of the third expert with the outstanding reputation is most influential.
• The eigenvalues of the transition matrix given in (49) are $\theta_1=1$, $\theta_2=1/8$ and $\theta_3=1/12$.

• The ,,basis'' in the rate of convergence given by (43) is
  $$1-3a=1-3\min\limits_{i,j=1,2,3} p_{ij}= 1-\frac{3}{8}=\frac{5}{8}\;,$$
  whereas Corollary 2.4 yields the following substantially improved geometric rate of convergence
  $$\max\limits_{i\in\{1,\ldots,\ell\}}\bigl\vert\;\widehat\mu-\widehat\mu^{(n)}_i\bigr\vert = O(\vert\theta_2\vert^n)$$
  where $\theta_2=1/8$ denotes the second largest eigenvalue of the stochastic matrix ${\mathbf{P}}$ given by (49).