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 ):
Definition 1   There is a cutoff if there exist an,bn®¥, bn/an®0, 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):
• Geometric (see Diaconis and Stroock ): when X is a reversible Markov chain, then
dtv(Px(t),p)£
1
2
(
1-p(x)
p(x)
)1/2 [ max{b1,|bm-1|} ]  t
,
where -1<bm-1£bm-2£...£b1<b0=1 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:
dtv(Px(t),p)£ Pr(T>t).
Moreover, there exists a coupling T* such that, for all xÎ S, dtv(Px(t),p)= Pr(T*>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:
• 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.

• 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+.
The main result obtained in Fricker, Robert and Tibi  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 tlogl/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) )
 t³0
= æ
è
(1+cet)
 YN(t)
e
 -l Ncet
ö
ø
 t³0
,
which turns out to be a martingale for any c³ 0.

## References


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