A non-backtracking Polya's theorem.

Year of edition2016

 P\'olya's random walk theorem states that a random walk on a d-dimensional grid is recurrent for d=1,2 and transient for d3. We prove a version of P\'olya's random walk theorem for non-backtracking random walks. Namely, we prove that a non-backtracking random walk on a d-dimensional grid is recurrent for d=2 and transient for d=1, d3. Along the way, we prove several useful general facts about non-backtracking random walks on graphs. In addition, our proof includes an exact enumeration of the number of closed non-backtracking random walks on an infinite 2-dimensional grid. This enumeration suggests an interesting combinatorial link between non-backtracking random walks on grids, and trinomial coefficients.

Reference on publication
Kempton M.   A non-backtracking Polya's theorem. - : , 2016. // arXiv.org, 2016.
1.N. Alon, I. Benjamini, E. Lubetzky, and S. Sodin, Non-backtracking random walks mix faster, Communications in Contemporary Mathematics, 9 (2007) 585603.
2.N. Alon and E. Lubetzky. Poisson approximation for non-backtracking random walk, Israel J. Math., 174 (2009), 227-252.
3.O. Angel, J. Friedman, and S. Hoory, The non-backtracking spectrum of the universal cover of a graph, Transactions of the American Mathematical Society, 32 (2015), no. 6, 4287-4318.
4.S. Cioaba and P. Xu, Mixing rates of random walks with little backtracking, SCHOLAR--a scientific celebration highlighting open lines of arithmetic research, 27-58, Contemp. Math., 655, Amer. Math. Soc., Providence, RI, 2015.
5.P.G. Doyle, Applications of Rayleigh's short-cut method to P?olya's recurrence problem, PhDthesis, Dartmouth College, 1982. Online at http://www.math.dartmouth.edu/ doyle/docs/thesis/thesis.pdf.
6.P.G. Doyle and J.L. Snell, Random Walks and Electric Networks, The Mathematical Association of America, 1984.
7.R. Durrett, Probability: Theory and Examples, Cambridge University Press, 2013.
8.R. Fitzner and R. van der Hofstad, Non-backtracking random walk, J. Stat. Phys., 150 (2013), no. 2, 264-284.
9.M. Kempton, Non-backtracking random walks on graphs and a weighted Ihara's theorem, Open Journal of Discrete Mathematics, 6 (2016), no. 4, 207226.
10.F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborova, and P. Zhang, Spectral redemption in clustering sparse networks, Proceedings of the National Academy of Sciences, 110 (2013), no. 52, 20935-20940.
11.L. Lov?asz, Random walks on graphs: a survey, Combinatorics, Paul Erd"os is Eighty (Volume 2), Keszthely (Hungary) (1993) 1-46.
12.C. Moore, Random walks, Ramanujan Mathematical Society Mathematics Newsletter, 17 (2007), no. 3, 78-84.
13.J. Novak, P?olya's random walk theorem, Amer. Math. Monthly, 121 (2014), no. 8, 711-716.
14.G. P?olya, ?Uber eine aufgabe betreffend die irrfahrt im strassennetz, Math. Ann., 84 (1921), 149-160.
15.C. Sabot and P. Tarres, Edge-reinforced random walk, vertex-reinforced jump process and the supersymmetric hyperbolic sigma model, J. Eur. Math. Soc., 17 (2015), no. 9, 2353-2378.
16.J. Spencer and L. Florescu, Asymptopia, Student Mathematical Library, Volume 71, AMS Publications, 2014.
17.Z.-W. Sun, Congruences involving generalized central trinomial coefficients, Sci. China Math., 57 (2014), no. 7, 1375-1400.
18.P. Tetali, Random walks and effective resistance of networks, Journal of Theoretical Probability, 4 (1991), 101-109.
19.S. Wagner, Asymptotics of generalized trinomial coefficients, 2012, Available online at http://arxiv.org/abs/1205.5402v3.

This publication on other resources

Webportal arXiv.org