Cutoff for samples of Markov chains

LMC/IMAG, BP. 53, 38041 Grenoble Cedex 9, France; Bernard.Ycart@imag.fr.

Received: 2 February 1998
Revised: 23 September 1998

Abstract

We study the convergence to equilibrium of n-samples of independent Markov chains in discrete and continuous time. They are defined as Markov chains on the n-fold Cartesian product of the initial state space by itself, and they converge to the direct product of n copies of the initial stationary distribution. Sharp estimates for the convergence speed are given in terms of the spectrum of the initial chain. A cutoff phenomenon occurs in the sense that as n tends to infinity, the total variation distance between the distribution of the chain and the asymptotic distribution tends to 1 or 0 at all times. As an application, an algorithm is proposed for producing an n-sample of the asymptotic distribution of the initial chain, with an explicit stopping test.

Résumé

Nous étudions la convergence vers l'équilibre d'échantillons de taille n de chaînes de Markov en temps discret et continu. Ces échantillons sont des chaînes de Markov sur le produit cartésien de n copies de l'espace initial par lui-même, et ils convergent vers le produit de n copies de la mesure stationnaire de la chaîne initiale. Des estimations précises de la vitesse de convergence sont données en termes du spectre de la chaîne initiale. Un phénomène de transition rapide se produit, au sens où la distance en variation totale entre la loi de la chaîne et la mesure d'équilibre converge vers 1 ou 0 quand n tend vers l'infini. Comme application, nous proposons un algorithme, muni d'un test d'arrêt explicite, pour produire un échantillon de taille n de la mesure d'équilibre de la chaîne initiale.