Non-backtracking random walk

DOI10.1007/S10955-012-0684-6MaRDI QIDQ1942293zbMATH OpenOpenAlexFDO

Authors Robert Fitzner, Remco van der Hofstad

Publication date 18 March 2013

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

central limit theoremmixing timesimple random walknon-backtracking random walkeigensystem

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Brownian motion (60J65) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We consider non-backtracking random walk (NBW) in the nearest-neighbor setting on the Zd-lattice and on tori. We evaluate the eigensystem of the m X m-dimensional transition matrix of NBW where m denote the degree of the graph. We use its eigensystem to show a functional central limit theorem for NBW on Zd and to obtain estimates on the convergence towards the stationary distribution for NBW on the torus.

Recommendations

• Reversibility of the non-backtracking random walk
• Remarks on the recurrence and transience of non-backtracking random walks
• Random matrices, nonbacktracking walks, and orthogonal polynomials
• A non-backtracking Pólya's theorem
• Non-Backtracking Random Walks and Cogrowth of Graphs

Cites work

• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• Improved upper bounds for self-avoiding walks in Z^d
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Minimization algorithms and random walk on the d-cube
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• New upper bounds for the connective constants of self-avoiding walks
• Non-Backtracking Random Walks and Cogrowth of Graphs
• Poisson approximation for non-backtracking random walks
• Unlacing hypercube percolation: a survey

Cited in

(19)

• Loop expansion around the Bethe approximation through the \(M\)-layer construction
• A new weighted Ihara zeta function for a graph
• Hypercube percolation
• A non-backtracking Pólya's theorem
• Random walks and diffusion on networks
• Generalized approach to the non-backtracking lace expansion
• Remarks on the recurrence and transience of non-backtracking random walks
• Unlacing hypercube percolation: a survey
• A new method for quantifying network cyclic structure to improve community detection
• Characterizing limits and opportunities in speeding up Markov chain mixing
• The first order correction to the exit distribution for some random walks
• Analysis of node2vec random walks on networks
• Deterministic walks with choice
• Hitting times for second-order random walks
• NoBLE for lattice trees and lattice animals
• Reversibility of the non-backtracking random walk
• Expansion of Percolation Critical Points for Hamming Graphs
• Non-backtracking loop soups and statistical mechanics on spin networks
• Random walks with “back buttons” (extended abstract)

This page was built for publication: Non-backtracking random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1942293)