Long-term concentration of measure and cut-off (Q2169077)

This article presents new theoretical concentration of measure inequalities for Markov chains in a unified framework, establishing and generalizing results for chains that are contracting in Wasserstein distance. Under suitable assumptions -- either concerning the set of functions on which the concentration inequality operates, or the contraction properties of the underlying path-space -- the concentration bounds are shown to be of the \textit{Gaussian then exponential} type, akin to Bernstein's inequalities: the probability of deviations of at least \(m\) from the mean is of order \(\mathrm{e}^{-cm^2}\) for small \(m\) and \(\mathrm{e}^{-cm}\) for large \(m\). It is worth mentioning that in the case where the assumptions concern the set of functions of interest, the concentration inequality operates without even a metric on the state space, due to the direct effect a coupling has on the function \(f\) of interest (case of \textit{\(f\) contracting chains}). These bounds are then extended to continuous-time Markov chains with general state space and provide a very useful tool to establish the cut-off phenomenon for fairly general chains. An auxiliary result for continuous-time Markov chains is also derived which proves that a chain with a contracting coupling mixes rapidly once it enters a region \(R\) of the state space where the equilibrium distribution is concentrated; namely, it is shown that the mixing time from any `distant' state is dominated by the `travel time' to reach \(R\), providing a useful ingredient for proofs of the cut-off phenomenon. The paper studies three examples. First, a concentration inequality is applied to the Bernoulli-Laplace model of diffusion, yielding a probabilistic proof of the cut-off phenomenon in this case, improving some of the bounds previously obtained by \textit{P. Diaconis} and \textit{M. Shahshahani} [SIAM J. Math. Anal. 18, 208--218 (1987; Zbl 0617.60009)]. Second, the power of the previous concentration inequalities is then illustrated by showing an extended cut-off phenomenon for a continuous-time infection disease model with two hosts (in which transmission only occurs between one host type and the other). Finally, the authors study the classical \textit{supermarket model} where there are \(n\) servers, each with their own queue of customers, and customers arrive according to a Poisson process with rate \(\lambda n\). Each arriving customer inspects the queues for \(d\) of the servers, chosen uniformly at random with replacement, and joins one of the shortest queues among these \(d\); customers cannot subsequently switch to a different queue. At each server, customer service times are iid exponential of mean \(1\). The authors manage to show stronger concentration than already existing results in all cases of parameters \((n,d,\lambda)\), giving another illustration of the power of their concentration inequalities.