Convergence of Finite Markov Chains

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

P_y(t)(x)-p(x)

£ Ca^t, " x,y Î S,

where P_y(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

d_tv(P,Q)=

sup

AÌ S

{

P(A)-Q(A)

}

iÎ S

P({i})-Q({i})

or, more precisely

d(t)=

sup

xÎ S

d_tv(P_x(t),p).

One particularly interesting property is the existence of a cutoff (see Diaconis [2]):

Definition 1 There is a cutoff if there exist a_n,b_n®¥, b_n/a_n®0, such that

lim

n®¥

d(a_n+tb_n)=H(t),

with lim_t®-¥H(t)=1 and lim_t®+¥H(t)=0.

Two main methods can be used to evaluate d(t):

Geometric (see Diaconis and Stroock [3]): when X is a reversible Markov chain, then

d_tv(P_x(t),p)£

1

2
(

1-p(x)

p(x)
)^1/2 [ max{b₁,|b_m-1|} ]

t

,
where -1<b_m-1£b_m-2£...£b₁<b₀=1 are the eigenvalues of P. The values of b₁ and b_m-1 can be obtained from the Rayleigh-Ritz principle.
Coupling (see Aldous [1]): 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:
d_tv(P_x(t),p)£ Pr(T>t).
Moreover, there exists a coupling T^* such that, for all xÎ S, d_tv(P_x(t),p)= Pr(T^*>t).

2 Application to Erlang's Model

As an example of these techniques, let X_N(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:

and its equilibrium distribution is

p(x)= C_N

(l N)^x

, x£ N.

This process has three different regimes:

l>1. The queue becomes full after a finite time and N-X_N(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 (X_N(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-X_N(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 [4] is the existence of a cutoff in the possible regimes of Erlang's model:

Proposition 1 In the case l>1,

lim

N®¥

d_N(t) =

ì
í
î

1	if t<logl/l-1,
0	if t>logl/l-1.

In the case l³ 1 the behaviour of d_N is such that, for any sequence f(N) and for any aÎ R^*,

lim

N®¥

d_N

é
ê
ê
ë

log N

+ 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 Y_N(t) with input rate l N, which is the unbounded version of X_N(t). A central tool in the proof is the process

(

E_c(t)

)

t³0

æ
è

(1+ce^t)

Y_N(t)

-l Nce^t

ö
ø

t³0

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 L^AT_EX by H^EV^EA.