A modern field of study investigates the rates of convergence for the Kolmogorov ergodic theorem. The scope is to help develop and validate Monte Carlo methods for the approximate simulation from laws, which will be described in Section 5.2. One of the objectives of this section is to facilitate the reading of advanced books on the subject, such as Duflo, M. (1996) and Saloff-Coste, L. (1997). The latter book provides many examples of explicit refined bounds of convergence in law.
We are going to describe the functional analysis framework which is at the basis of the simplest aspects of these studies, which is an extension of the concepts in Section 1.3. If is finite, then powerful results can be obtained by classic tools of finite dimensional linear algebra, which they thus illustrate. If is infinite, extensions of these tools will be introduced, such as those described in the book of Rudin, W. (1991).
Let be an irreducible positive recurrent Markov chain on with matrix , and be its invariant law. Consider the functional Hilbert space , in which the scalar product of and is given by
A fundamental probabilistic interpretation is that
The matrix of the time reversal in equilibrium of satisfies
Hence, is the adjoint of in , and is reversible for if and only if is self-adjoint in . The link between adjoints and time reversal can be seen in
The natural duality bracket between measures and functions
allows to identify the dual space with a subspace of . The Cauchy–Schwarz inequality yields that
with equality if is equal to the density of w.r.t. . Thus, is a Hilbert space included in , with scalar product given, for and , by
which is the scalar product in of their densities w.r.t. . The adjoint of on is the operator on , which has norm , and
The following duality formulae should be kept in mind:
These computations become clearer if we use as a reference duality bracket the scalar product of itself, which identifies it with its own dual . For and ,
which identifies to its density and to . Note that the total variation norm can be expressed as the norm of the densities.
We elect to use the natural duality already used in Section 1.3 and use the duality formulae (3.8), even though the notations and are compatible with both duality frameworks.
This duality could be identified with the natural duality between the sequence spaces and , in which case and are identified with the spaces and of square-summable sequences with the corresponding weights, and the space is the pivot space in the Gelfand triple
All this makes for a better understanding of Section 3.3.3.
The notations and can be used if the context is clear. If , then often it is said that “there is a spectral gap.”
This almost tautological result justifies the notions that have been introduced: if , then provides a geometric convergence rate for toward . If is finite, it is so as soon as is irreducible, and this will be generalized to an arbitrary irreducible aperiodic matrix in Exercise 4.10.
If is not irreducible or is not aperiodic, clearly and are not irreducible, and then . Exercise 4.6 will show that or may well not be irreducible, even if is irreducible aperiodic.
An effective method for finding explicit lower bounds for the spectral gap can be to establish Poincaré inequalities using graph techniques. This will be done in Exercises 4.11 and 4.12. This technique is developed on many examples in Duflo, M. (1996) and Saloff-Coste, L. (1997), Chapter 3.
The Markov chain on with matrix for is irreducible if and only if and aperiodic if and only if .
If , then , any law is invariant, and . Else, the only invariant law is and is reversible for , and if and only if . Moreover,
and and imply that, up to sign for ,
Thus, varies continuously, between when and the chain is not irreducible and when and the chain has period .
As and hence and
and the explicit form for given in Section 1.3.3 shows that the exponential bounds in Theorem 4.3.5 cannot be improved.
The spectrum of a bounded operator on a Banach space is the set of all such that is not invertible. The spectral radius is given by .
If is a transition matrix having an invariant law , then is reversible w.r.t. and , and and are both reversible w.r.t. and nonnegative: and . In this way, we can reduce some problems to reversible matrices. These correspond to self-adjoint operators on a Hilbert space, of which the spectral theory is a powerful tool developed, for example, in Rudin, W. (1991), Chapter 12.
If is an irreducible transition matrix on a state space , which is reversible w.r.t. a probability measure , then is self-adjoint in the Hilbert space , and hence, its spectrum is real, see Rudin, W. (1991) Theorem 12.15. Theorem 4.2.15 then yields that the only elements of the spectrum of modulus can be (always a simple eigenvalue) and and that is in the spectrum if and only if has period and then it is a simple eigenvalue.
Let be an irreducible transition matrix, which is reversible w.r.t. a probability measure , on a finite state space .
Classic results of linear algebra and Theorem 4.2.15 yield that the spectrum is constituted of (possibly repeated) real eigenvalues
and that can be diagonalized in an orthonormal basis of constituted of corresponding eigenvectors , , … , . This yields the spectral decomposition
in which
denotes the orthogonal projection in on the eigenspace of . The expression in terms of these projections is unique, even though the orthonormal basis is not.
Setting
for , it holds that
with equality if and only if is in the vector space generated by the eigenvalues with modulus . If has period , then is an eigenvalue and hence , else if is aperiodic, then gives the geometric rate of convergence. The corresponding result for is obtained analogously or by duality.
As an example, we refer to the macroscopic description of the Ehrenfest Urn in Section 1.4.4. Its eigenvalues are of the form
the latter as has period . Moreover, the corresponding eigenvectors were computed.
When is infinite, the spectral decomposition in terms of orthogonal projections (3.9) can be generalized in integral form into a resolution of the identity, using the spectral theorem given, for example, in Rudin, W. (1991) Theorem 12.23. This yields results analogous to (3.10). We state without further explanations the following important result, which we have just proved when is finite and hence, is finite dimensional, and which is still classic in infinite dimensions.
If , then and converge to exponentially as goes to infinity. Moreover, if and only if or are in the closure of , which can happen when is infinite even when is irreducible aperiodic. In this situation, a modern research topic is to establish polynomial rates of convergence bounds.
The advantage of the Dirichlet form techniques is that they can be applied to a transition matrix which is not necessarily reversible w.r.t. its invariant law . Moreover, it is often difficult to estimate a spectrum, and the following result allows the estimation of from the spectral gap , and the latter can often be estimated using, for instance, Poincaré inequalities.
The theory of continuous-time Markov chains is simpler than the theory for discrete-time Markov chains for everything concerning the long-time limits of the instantaneous law and their rates of convergence, for instance in terms of Dirichlet forms, spectral gaps, and spectral theory. Notably, the notion of period disappears.
If the generator (or -matrix) is bounded as an operator on , that is, if
then the transition semigroup with generic term is given by the sum of the exponential series
which is normally convergent for the operator norm , and the Gronwall Lemma yields that it is the unique solution of the Kolmogorov equations
Moreover, for some transition matrix , and the evolution of a continuous-time Markov chain with bounded generator corresponds to jumping at the instants of a Poisson process of intensity according to a discrete-time Markov chain with transition matrix .
Hence, Saloff-Coste, L. (1997, Sections 1.3.1 and 2.1.1) considers the continuous-time Markov chain with generator . The first inequality of the proof of Theorem 4.3.5 is replaced if by
obtained by the Kolmogorov equations and the differentiation of bilinear forms, yielding the inequalities
in which the spectral gap appears directly. If and hence are reversible, formulae such as (3.10) become
in which is again the spectral gap, which explains this denomination.
4.1 The space station, the mouse, and three-card Monte See Exercises 1.1, 1.2, and 1.5.
4.2 Difficult advance, see Exercise 3.9 For , give the long-time limit of the probability that the chain is in . For , give for the long-time limit of the ratio between the time spent in and the time spent in .
4.3 Queue with servers, see Exercise 3.10 When , give the long-time limit of the fraction of time that all servers are operating simultaneously.
4.4 Centered random walk, 1-d On , let be a sequence of i.i.d. integrable r.v., be an independent r.v., and be the corresponding random walk. Let , recall that then is null recurrent, and let and . Let and for .
4.5 Period and adjoint Let be an irreducible transition matrix with period having an invariant measure , and the adjoint of w.r.t. . Prove that has period and describe its decomposition in aperiodic classes. Are the matrices and irreducible?
4.6 Renewal process Let , the renewal process with and , and its matrix .
4.7 Distance to equilibrium Let be an irreducible Markov chain on with matrix having an invariant law .
4.8 Dirichlet form Let be an irreducible transition matrix and an invariant measure. As a generalization of the Dirichlet form, for in , let .
4.9 Spectral gap bounds Let be an irreducible transition matrix on having an invariant law , and .
4.10 Exponential bounds Let be an irreducible transition matrix on having an invariant law .
4.11 Poincaré inequality and graphs Let be an irreducible transition matrix on which is reversible w.r.t. a law , and
Choose a length function , for every a simple path
in which are distinct elements of , and let
Deduce from this that
4.12 Spectral gap of the M/M/1 queue The results of Exercise 4.11 are now going to be applied to the random walk with reflection at on with matrix given by and . Let and for in .
Actually, this bound is the exact value for the spectral gap, which is well known as is the generator of the continuous-time Markov chain of the number of jobs in an queue.
4.13 Entropy Let with . For laws and on , the relative entropy of w.r.t. is defined by
3.147.84.169