Authors | ||

Book | arXiv.org. | |

Year of edition | 2016 |

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 $d\ge 3$. 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$, $d\ge 3$. 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 |
---|

Bibliography | |
---|---|

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. |