Mixing Rates of Random Walks with Little Backtracking

2015/06/03 by Sebastian M. Cioabă, Peng Xu, Cioabă, Sebastian M. +1
Computer Science · Mathematics · #05C81 #05E30 #15A18 #60B10 #60C05 #60G99 #60J10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1506.01419

openalex publication_date 2015/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Many regular graphs admit a natural partition of their edge set into cliques of the same order such that each vertex is contained in the same number of cliques. In this paper, we study the mixing rate of certain random walks on such graphs and we generalize previous results of Alon, Benjamini, Lubetzky and Sodin regarding the mixing rates of non-backtracking random walks on regular graphs.

Related

• Non-backtracking random walks and a weighted Ihara's theorem
• Some relations between the spectra of simple and non-backtracking random walks
• Comparing mixing times on sparse random graphs
• Cutoff for random walks on graphs with bottlenecks
• Random walks on the random graph