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 theoremeigensystemmixing timenon-backtracking random walksimple random walk

Mathematics Subject Classification ID

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

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
• New upper bounds for the connective constants of self-avoiding walks
• Non-Backtracking Random Walks and Cogrowth of Graphs
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Poisson approximation for non-backtracking random walks
• Unlacing hypercube percolation: a survey

Cited in

(23)

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

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)