@article{EJP3060,
author = {Yinon Spinka and Ron Peled},
title = {Random walk with long-range constraints},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {19},
year = {2014},
keywords = {Random walk, random graph homomorphism, phase transition, Lipschitz function},
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.},
pages = {no. 52, 1-54},
issn = {1083-6489},
doi = {10.1214/EJP.v19-3060},
url = {http://ejp.ejpecp.org/article/view/3060}}