Transience of Simple Random Walks With Linear Entropy Growth

2023/02/15 by Ben Morris, Morris, Ben, Hamilton Samraj Santhakumar +1
Mathematics · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2302.07496

Abstract

Using the technique of evolving sets, we explore the connection between entropy growth and transience for simple random walks on connected infinite graphs with bounded degree. In particular we show that for a simple random walk starting at a vertex x₀, if the entropy after n steps, E_n is at least Cn where the C is independent of x₀, then the random walk is transient. We also give an example which demonstrates that the condition of C being independent of x₀ is necessary.

Related

• Lamplighter Random Walks and Entropy-Sensitivity of Languages
• On random walk on growing graphs
• An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes
• Graph properties, graph limits and entropy
• Graph properties, graph limits, and entropy