Next: Irreducible and Aperiodic Markov Up: Ergodicity and Stationarity Previous: Basic Definitions and Quasi-positive   Contents

### 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:

 (43)

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

 (44)

where and hence if .
• 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

of has the two solutions 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.

Theorem 2.6
• 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.

Corollary 2.3   Let be a quasi-positive transition matrix. Then
• 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 .

Corollary 2.3 yields the following geometric convergence estimate.

Corollary 2.4   Let be a quasi-positive transition matrix such that all eigenvalues of are pairwise distinct. Then

 (45)

Proof

• Corollary 2.3 implies

 (46)

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.,

it is easy to see that

• As (see Theorem 2.3) this together with (46) shows (45).

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.
• 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

 (47)

exist and do not depend on ,
• where the vector of the limits is the (uniquely determined) solution of the linear equation system (41), i.e. with .
• 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

 (48)

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

 (49)

• 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

i.e. the projection of the third expert with the outstanding reputation is most influential.
• The eigenvalues of the transition matrix given in (49) are , and .

• The ,,basis'' in the rate of convergence given by (43) is

whereas Corollary 2.4 yields the following substantially improved geometric rate of convergence

where denotes the second largest eigenvalue of the stochastic matrix given by (49).

Next: Irreducible and Aperiodic Markov Up: Ergodicity and Stationarity Previous: Basic Definitions and Quasi-positive   Contents
Ursa Pantle 2006-07-20