Random walk with long-range constraints

Abstract

We consider a model of a random height function with long-range constraints on a discrete segment. This model was suggested by Benjamini, Yadin and Yehudayoff and is a generalization of simple random walk. The random function is uniformly sampled from all graph homomorphisms from the graph $P_{n,d}$ to the integers $\mathbb{Z}$, where the graph $P_{n,d}$ is the discrete segment $\{0,1,\ldots, n\}$ with edges between vertices of different parity whose distance is at most $2d+1$. Such a graph homomorphism can be viewed as a height function whose values change by exactly one along edges of the graph $P_{n,d}$. We also consider a similarly defined model on the discrete torus.

Benjamini, Yadin and Yehudayoff conjectured that this model undergoes a phase transition from a delocalized to a localized phase when $d$ grows beyond a threshold $c\log n$. We establish this conjecture with the precise threshold $\log_2 n$. Our results provide information on the typical range and variance of the height function for every given pair of $n$ and $d$, including the critical case when $d-\log_2 n$ tends to a constant.

In addition, we identify the local limit of the model, when $d$ is constant and $n$ tends to infinity, as an explicitly defined Markov chain.