CUTOFF FOR NONBACKTRACKING RANDOM WALKS ON SPARSE RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Ben-Hamou, Anna; Salez, Justin
• 署名单位: Universite Paris Cite; Universite Paris Cite
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/16-AOP1100
• 发表日期: 2017
• 页码: 1752-1770
• 关键词: markov-chains; glauber dynamics; finite-groups; inequalities; times; MODEL

摘要

A finite ergodic Markov chain exhibits cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Discovered in the context of card shuffling (Aldous-Diaconis, 1986), this phenomenon is now believed to be rather typical among fast mixing Markov chains. Yet, establishing it rigorously often requires a challengingly detailed understanding of the underlying chain. Here, we consider nonbacktracking random walks on random graphs with a given degree sequence. Under a general sparsity condition, we establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a remarkably simple, universal shape.