Convergence time to equilibrium
for multi-particle Markov chains

A. D. Manita

(September 1997)

Multi-particle Markov chains ${\cal L}(N)$ are stochastic systems consisting of $M(N)$ noninteracting particles moving according to the law of some "one-particle" finite Markov chain ${\cal K}(N)$. Our goal is to find the convergence time to equilibrium $T(N)$ for the sequence of Markov chains ${\cal L}(N)$ in the situation when the number of particles $M(N)$ tends to infinity and the "size" of the one-particle chain ${\cal K}(N)$ grows. We consider wide classes of models and find $T(N)$ for them as a function of $M(N)$ and $T_{\cal K}(N)$, where $T_{\cal K}(N)$ is the convergence time to equilibrium for the sequence of one-particle chains ${\cal K}(N)$. We apply these results to a discrete analogue of some queueing system and to a random walk on circle.

Key words: convergence time to equilibrium, multi-particle Markov chains, Monte Carlo Markov chains, Lyapunov functions, geometric ergodicity, queueing system M|M|1|N, random walk on circle

Preprint of French-Russian Institute, No.3. Moscow University, 1997.

English version:

• mp-eng.ps.gz (GZip compression, 160K)
• mp-eng.zip (Zip compression, 160K)
• mp-eng.ps (plain PostScript, 480K)

Russian version:

• manita1.ps.gz (GZip compression)
• manita1.zip (Zip compression)
• manita1.ps (plain PostScript)

Hardcopy of the preprint may be requested from the author.