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

- Recall:
- If is a Markov chain whose 1-step transition matrix has only strictly positive entries ,
- then the geometric bound for the rate of convergence to the limit
distribution
derived in
(40) is given as follows:

where .

- Whenever the minimum of the entries of the transition matrix is close to 0 the bound in (43) is not very useful.
However, in some cases the basis of the convergence estimate (43) can be improved.

**Example**- (
*Weather Forecast*)- Let and
- In Section 2.2.1 we showed that
- the -step transition matrix
is given by
- and thus
- Consequently

where and hence if .

- the -step transition matrix
is given by
- Remarks
- The basis of the rate of convergence in (44) is the absolute value of the second largest eigenvalue of the transition matrix ,
- as the characteristic equation

- Let and

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.

- Let be a quasi-positive matrix with eigenvalues such that .
- Then the following holds:
- (a)
- The eigenvalue is real and positive.
- (b)
- for all ,
- (c)
- The right and left eigenvectors and of are uniquely determined up to a constant factor and can be chosen such that all components of and 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.

- and , where and .
- for all .

**Proof**-
- As
is a stochastic matrix
- obviously and (41) implies .
- Thus is an eigenvalue of and and are right and left eigenvectors of this eigenvalue, respectively.

- Let now be
- an arbitrary eigenvalue of and let an eigenvector corresponding to .
- By definition (27) of and
- Consequently and therefore is the largest eigenvalue of .

- Theorem 2.6 now implies
for
.

- As
is a stochastic matrix

Corollary 2.3 yields the following geometric convergence estimate.

**Proof**-
- Corollary 2.3 implies

as for all . - Furthermore, Corollary 2.3 implies as well as and being the right and left eigenvectors of , respectively.
- Taking into account the spectral representation (30) of
, i.e.,
- As
(see
Theorem 2.3) this together with (46)
shows (45).

- Corollary 2.3 implies
**Example**- (
*Reaching a Consensus*)

see C. Hesse (2003)*Angewandte Wahrscheinlichkeitstheorie*. Vieweg, Braunschweig, p. 349- A committee consisting of members has the mandate to project
a certain (economical) parameter
, one could think of the
German Council of Economic Experts projecting economic growth for
the next year.
- In a first step each of the experts gives a personal projection for , where the single projection results are denoted by .
- 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 , 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 colleagues and
his personal assessment of their authors expertise.
- For arbitrary
the expert attributes
the ,,trust probability'' to the expert such that
and
- and expert modifies his original projection
replacing it by
- In most cases the modified projections will still be different from each other. Therefore the procedure is repeated until the differences are sufficiently small.

- For arbitrary
the expert attributes
the ,,trust probability'' to the expert such that
- Theorem 2.4 ensures
- The equality (47) can be seen as follows:

- The consensus, i.e. the common projection of the unknown parameter
, reached by the committee is given by

- A committee consisting of members has the mandate to project
a certain (economical) parameter
, one could think of the
German Council of Economic Experts projecting economic growth for
the next year.
**Remarks**-
- For large 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 and

- The entries of this stochastic matrix imply that the third expert has a particularly high reputation among his colleagues.
- The solution
of the corresponding
linear equation system (41) is given by

- Let and
- The eigenvalues of the transition matrix given in
(49) are
,
and
.
- The ,,basis'' in the rate of convergence given by
(43) is