Convergence of Finite Markov Chains
February 2, 1998
[summary by Jean-Marc Lasgouttes]
A properly typeset version of this document is available in postscript
and in pdf
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Let X(t) be an aperiodic and irreducible Markov chain on a finite
set S, with transition probabilities P=(p(x,y))x,yÎ S and
equilibrium distribution (p(x))xÎ S. It is often desirable to
know how far Pr(X(t)=x) is from p(x), in particular when
p(x) has a nice closed form, but the transient distribution is
difficult to express. It is known (Doeblin) that there exists
aÎ]0,1[, such that
where Py(t) is the law of X(t) when X(0)=y.
||£ Cat, " x,y Î S,
This talk is concerned with methods allowing to get more accurate
estimates on this difference. The distance that will be used in the
following is the total variation distance between two
probability distributions P and Q on S, defined by
or, more precisely
One particularly interesting property is the existence of a
cutoff (see Diaconis ):
There is a cutoff if there exist an,bn®¥, bn/an®0,
with limt®-¥H(t)=1 and limt®+¥H(t)=0.
Two main methods can be used to evaluate d(t):
Geometric (see Diaconis and
Stroock ): when X is a reversible Markov chain,
are the eigenvalues of P. The values of b1 and bm-1
can be obtained from the Rayleigh-Ritz principle.
- Coupling (see Aldous ): let X and X~
be 2 versions of the Markov chain with transition matrix P, such
that X(0)=x and X~(0)~p. A coupling time is a finite
random variable T such that X(t)=X~(t), for all t³
T. The following inequality holds for such T:
Moreover, there exists a coupling T* such that, for all xÎ S,
2 Application to Erlang's Model
As an example of these techniques, let XN(t), tÎ R+ be the
Markov process associated with a M/M/N/N queue with arrival rate
l N and service rate 1. This process, known as an Erlang
loss system with N slots, has the transition rates
and its equilibrium distribution is
This process has three different regimes:
The main result obtained in Fricker, Robert and
Tibi  is the existence of a cutoff in the
possible regimes of Erlang's model:
l>1. The queue becomes full after a finite
time and N-XN(t/N) is a Markov process whose generator tends as
N® ¥ to the generator of a birth and death process.
- l<1. The queue is never full and the
process (XN(t)-l N)/(N)1/2 has a generator which tends to
the generator of an Ornstein-Ülenbeck process with parameter
- l=1. The queue becomes full at infinity and
the process (N-XN(t))/(N)1/2 has a generator which tends to the
generator of the reflected Ornstein-Ülenbeck process on R+.
Proposition 1 In the case l>1,
In the case l³ 1 the behaviour of dN is such that, for
any sequence f(N) and for any aÎ R*,
These results are obtained by coupling techniques and use as an
auxiliary process the M/M/¥ queue YN(t) with input rate
l N, which is the unbounded version of XN(t). A central
tool in the proof is the process
which turns out to be a martingale for any c³ 0.
Aldous (David). --
Random walks on finite groups and rapidly mixing Markov chains. In
Seminar on probability, XVII, pp. 243--297. --
Springer, Berlin, 1983.
Diaconis (Persi). --
The cutoff phenomenon in finite Markov chains. Proceedings of
the National Academy of Sciences of the United States of America, vol. 93,
n°4, 1996, pp. 1659--1664.
Diaconis (Persi) and Stroock (Daniel). --
Geometric bounds for eigenvalues of Markov chains. The Annals
of Applied Probability, vol. 1, n°1, 1991, pp. 36--61.
Fricker (Christine), Robert (Philippe), and Tibi (Danielle). --
On the rates of convergence of Erlang's model. --
Research Report n°3368, Institut National de Recherche en
Informatique et en Automatique, February 1998.
This document was translated from LATEX by