Random walk with long-range constraints. (English) Zbl 1294.82019

Summary: We consider a model of a random height function with long-range constraints on a discrete segment. This model was suggested by I. Benjamini et al. [Electron. J. Probab. 12, 926–950 (2007; Zbl 1127.60007)] 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,\dots, 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 et al. [loc. cit.] 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.


82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics
60C05 Combinatorial probability
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
82B26 Phase transitions (general) in equilibrium statistical mechanics
60D05 Geometric probability and stochastic geometry
05A16 Asymptotic enumeration
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B27 Critical phenomena in equilibrium statistical mechanics


Zbl 1127.60007
Full Text: DOI arXiv