Tail distributions of cover times of once-reinforced random walks

2025/05/08 by Xiang‐Yu Huang, Yong Liu, Huang, Xiangyu +3
Mathematics · Biochemistry, Genetics and Molecular Biology · #Stochastic processes and statistical mechanics #Diffusion and Search Dynamics #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.2505.05284

Abstract

We consider the tail distribution of the edge cover time of a specific non-Markov process, δ once-reinforced random walk, on finite connected graphs, whose transition probability is proportional to weights of edges. Here the weights are 1 on edges not traversed and δ∈(0,∞) otherwise. In detail, we show that its tail distribution decays exponentially, and obtain a phase transition of the exponential integrability of the edge cover time with critical exponent α_c¹(δ), which has a variational representation and some interesting analytic properties including α_c¹(0+) reflecting the graph structures.

Citations

• Cover times for random walk on dynamical percolation
• Limit law for the cover time of a random walk on a binary tree
• Cover time for branching random walks on regular trees
• Once reinforced random walk on ℤ× Γ
• The branching-ruin number and the critical parameter of once-reinforced random walk on trees
• Exponential concentration of cover times
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• Linear Cover Time is Exponentially Unlikely
• Cover times, blanket times, and majorizing measures

Related

• Once reinforced random walk on ℤ× Γ
• Almost sure behavior of linearly edge-reinforced random walks on the half-line
• Cover Time in Edge-Uniform Stochastically-Evolving Graphs
• Variations on Reinforced Random Walks
• The Cover Time of Random Walks on Graphs