Convergence of Finite Markov Chains

Philippe Robert

INRIA-Rocquencourt

Algorithms Seminar

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

1   Framework

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
| Py(t)(x)-p(x) | Cat,   " x,y S,
where Py(t) is the law of X(t) when X(0)=y.

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
dtv(P,Q)=
 
sup
A S
{ | P(A)-Q(A) | } =
1
2
 
i S
| P({i})-Q({i}) | ,
or, more precisely
d(t)=
 
sup
x S
dtv(Px(t),p).
One particularly interesting property is the existence of a cutoff (see Diaconis [2]):
Definition 1   There is a cutoff if there exist an,bn, bn/an0, such that
 
lim
n
d(an+tbn)=H(t),
with limt-H(t)=1 and limt+H(t)=0.
Two main methods can be used to evaluate d(t):

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
x x+1:
   l N1
 
{x N}
x x-1:    x
and its equilibrium distribution is
p(x)= CN
(l N)x
x!
,   x N.

This process has three different regimes: The main result obtained in Fricker, Robert and Tibi [4] is the existence of a cutoff in the possible regimes of Erlang's model:
Proposition 1   In the case l>1,
 
lim
N
dN(t) =


1    if t<logl/l-1,
0    if t>logl/l-1.
In the case l 1 the behaviour of dN is such that, for any sequence f(N) and for any a R*,
 
lim
N
dN


log N
2
+ af(N)


=


1    if a<0,
0    if a>0.

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
( Ec(t) )
 
 
t0
=
(1+cet)
YN(t)
 
e
-l Ncet
 

 

t0
,
which turns out to be a martingale for any c 0.

References

[1]
Aldous (David). -- Random walks on finite groups and rapidly mixing Markov chains. In Seminar on probability, XVII, pp. 243--297. -- Springer, Berlin, 1983.

[2]
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.

[3]
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.

[4]
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 HEVEA.