We study convergence to equilibrium for a class of Markov chains in random environment. The chains are sparse in the sense that in every row of the transition matrix P the mass is essentially concentrated on few entries. Moreover, the entries are exchangeable within each row. This includes various models of random walks on sparse random directed graphs. The models are generally non reversible and the equilibrium distribution is itself unknown. In this general setting we establish the cutoff phenomenon for the total variation distance to equilibrium, with mixing time given by the logarithm of the number of states times the inverse of the average row entropy of P. As an application, we consider the case where the rows of P are i.i.d. random vectors in the domain of attraction of a Poisson–Dirichlet law with index α∈ (0 , 1). Our main results are based on a detailed analysis of the weight of the trajectory followed by the walker. This approach offers an interpretation of cutoff as an instance of the concentration of measure phenomenon.

Bordenave, C., Caputo, P., Salez, J. (2019). Cutoff at the “entropic time” for sparse Markov chains. PROBABILITY THEORY AND RELATED FIELDS, 173(1-2), 261-292 [10.1007/s00440-018-0834-0].

Cutoff at the “entropic time” for sparse Markov chains

Bordenave, Charles;Caputo, Pietro
;
2019-01-01

Abstract

We study convergence to equilibrium for a class of Markov chains in random environment. The chains are sparse in the sense that in every row of the transition matrix P the mass is essentially concentrated on few entries. Moreover, the entries are exchangeable within each row. This includes various models of random walks on sparse random directed graphs. The models are generally non reversible and the equilibrium distribution is itself unknown. In this general setting we establish the cutoff phenomenon for the total variation distance to equilibrium, with mixing time given by the logarithm of the number of states times the inverse of the average row entropy of P. As an application, we consider the case where the rows of P are i.i.d. random vectors in the domain of attraction of a Poisson–Dirichlet law with index α∈ (0 , 1). Our main results are based on a detailed analysis of the weight of the trajectory followed by the walker. This approach offers an interpretation of cutoff as an instance of the concentration of measure phenomenon.
2019
Bordenave, C., Caputo, P., Salez, J. (2019). Cutoff at the “entropic time” for sparse Markov chains. PROBABILITY THEORY AND RELATED FIELDS, 173(1-2), 261-292 [10.1007/s00440-018-0834-0].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/346427
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 12
social impact