Tail distributions of cover times of once-reinforced random walks

Abstract

We consider the tail distribution of the edge cover time of a specific non-Markov process, $\delta$ 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 $\delta \in (0,\infty )$ 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 ${\alpha }_c^1(\delta )$, which has a variational representation and some interesting analytic properties including ${\alpha }_c^1(0+)$ reflecting the graph structures.