NON-BACKTRACKING RANDOM WALKS MIX FASTER

DOI10.1142/S0219199707002551zbMath1140.60301arXivmath/0610550OpenAlexW3100428187MaRDI QIDQ3502774

Sasha Sodin, Noga Alon, Itai Benjamini, Eyal Lubetzky

Publication date: 20 May 2008

Published in: Communications in Contemporary Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0610550

zbMATH Keywords

Chebyshev polynomials mixing rate balls and bins high-girth regular expander

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Related Items

Markov chains on finite fields with deterministic jumps, Analytical results for the distribution of cover times of random walks on random regular graphs, Ramanujan graphings and correlation decay in local algorithms, Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time, A new method for quantifying network cyclic structure to improve community detection, Cutoff on all Ramanujan graphs, The cover time of a biased random walk on a random cubic graph, Mean-field conditions for percolation on finite graphs, Poisson approximation for non-backtracking random walks, Functional limit theorems for random regular graphs, On the exponential generating function for non-backtracking walks, Séta: Supersingular Encryption from Torsion Attacks, A new weighted Ihara zeta function for a graph, CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS, Random walks and diffusion on networks, Supersingular curves you can trust, Matrix functions in network analysis, Kemeny's constant for nonbacktracking random walks, On the almost eigenvectors of random regular graphs, Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, The limit theorem with respect to the matrices on non-backtracking paths of a graph, Combinatorial statistics and the sciences, The spectral edge of some random band matrices, Non-backtracking random walk, New constructions of collapsing hashes, Spectral redemption in clustering sparse networks, Spectral theory of the non-backtracking Laplacian for graphs, Correlation Bounds for Distant Parts of Factor of IID Processes, Simple versus nonsimple loops on random regular graphs, Spectral measures of factor of i.i.d. processes on vertex-transitive graphs, The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis, Unnamed Item, An estimate for the average spectral measure of random band matrices, On the spectral analysis of second-order Markov chains, Expander graphs -- both local and global, The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, On the Number of Perfect Matchings in Random Lifts, Beyond non-backtracking: non-cycling network centrality measures, Analysis of node2vec random walks on networks, Greedy Random Walk, Hypercube percolation, Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk, Unnamed Item, Some spectral properties of the non-backtracking matrix of a graph, Cutoff phenomena for random walks on random regular graphs, Characterizing limits and opportunities in speeding up Markov chain mixing, Approximate Moore graphs are good expanders, Cycle density in infinite Ramanujan graphs, Reversibility of the non-backtracking random walk, Recent results of quantum ergodicity on graphs and further investigation, A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs, Some observations on the smallest adjacency eigenvalue of a graph, Deterministic walks with choice, Spectra of random regular hypergraphs, Identification protocols and signature schemes based on supersingular isogeny problems, Balanced Allocation on Graphs: A Random Walk Approach, Non-Backtracking Alternating Walks, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Comparing mixing times on sparse random graphs, Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization, Mixing time of fractional random walk on finite fields, The non-backtracking spectrum of the universal cover of a graph, Non-backtracking PageRank, Discrete Graphs – A Paradigm Model for Quantum Chaos, The distribution of first hitting times of non-backtracking random walks on Erdős–Rényi networks, Analytical results for the distribution of first hitting times of random walks on random regular graphs

Cites Work