Recurrence and transience of random walks on monotonically changing environments

Rupert Li; Jiyun Park

In the authors' words

Let $(c_{t})_{t \geq 0}$ be a deterministic family of edge conductances on a countable vertex set, monotone in $t$ , and let $(X_{t})$ be the random walk that takes its $t$ -th step using the conductances $c_{t}$ . We prove that if $c_{t} ↑ c_{\infty}$ and $c_{\infty}$ is recurrent (respectively, $c_{0}$ is transient), then $(X_{t})$ is almost surely recurrent (respectively, transient), i.e., visits every vertex infinitely (respectively, finitely) often. We also establish the analogous results in continuous time. This proves conjectures of Amir, Benjamini, Gurel-Gurevich, and Kozma, and the special case of ${0, 1}$ -valued conductances corresponds to simple random walk on a growing graph, and in this special case our results prove a conjecture of Dembo, Huang, and Sidoravicius. In addition, we provide counterexamples to the corresponding conjectures when $(c_{t})$ is monotone non-increasing: if $c_{t} ↓ c_{\infty}$ and $c_{\infty}$ is transient, $(X_{t})$ need not be transient, and similarly if $c_{0}$ is recurrent, $(X_{t})$ need not be recurrent, even if $c_{\infty} \geq α c_{0}$ for some $α > 0$ .

Main resultLimitation the authors admit

Recurrence and transience of random walks on monotonically changing environments

In the authors' words

More on Probability that day

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

Stopping models closed under pgf composition, and the stability of randomly stopped model extensions

On Fast-Slow Mean-Field Forward-Backward Stochastic Systems

Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation

Quantitative QSD convergence in 1-Wasserstein distance via the F\"ollmer drift