Supplementary Material for Random Cayley Graphs Project

2018/10/11 by Jonathan Hermon, Hermon, Jonathan, Sam Olesker-Taylor +1 · 3 citations
Computer Science · Mathematics · #Cellular Automata and Applications #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1810.05130

openalex publication_date 2018/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This document contains supplementary material for the main articles in our Random Cayley Graphs project. We prove refined results about simple random walks on the integers and on the cycle. We are primarily interested in the entropy of these random walks at certain times and how this entropy changes when the time changes slightly. Additionally, we prove some large deviation and exit time estimates. We prove some results on the size of discrete lattice balls and how this size changes when the radius changes slightly. We do this in a general L_q norm, with q ∈ [1,∞]. We also prove some other technical results deferred from the main papers. We hope that some of the results, particularly the simple random walk estimates, will be useful in their own right for other researchers.

Citations

• Logarithmic Sobolev inequalities for finite Markov chains

Cited by

• Cutoff for Random Walks on Upper Triangular Matrices
• Further Results and Discussions on Random Cayley Graphs
• Cutoff for Almost All Random Walks on Abelian Groups

Related

• Monotonicity for continuous-time random walks
• Further Results and Discussions on Random Cayley Graphs
• Return times of random walk on generalized random graphs
• Long-time Behavior of Random Walks in Random Environment
• Transience of Simple Random Walks With Linear Entropy Growth