Random walk with long-range constraints

Yinon Spinka (Tel-Aviv University)
Ron Peled (Tel Aviv Unviersity)

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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-54

Publication Date: June 23, 2014

DOI: 10.1214/EJP.v19-3060

References

  • Benjamini, Itai; Häggström, Olle; Mossel, Elchanan. On random graph homomorphisms into ${\bf Z}$. J. Combin. Theory Ser. B 78 (2000), no. 1, 86--114. MR1737627
  • Benjamini, Itai; Peres, Yuval. Markov chains indexed by trees. Ann. Probab. 22 (1994), no. 1, 219--243. MR1258875
  • Benjamini, Itai; Peres, Yuval. Tree-indexed random walks on groups and first passage percolation. Probab. Theory Related Fields 98 (1994), no. 1, 91--112. MR1254826
  • Benjamini, Itai; Yadin, Ariel; Yehudayoff, Amir. Random graph-homomorphisms and logarithmic degree. Electron. J. Probab. 12 (2007), no. 32, 926--950. MR2324796
  • Brascamp, Herm Jan; Lieb, Elliot H.; Lebowitz, Joel L. The statistical mechanics of anharmonic lattices. Proceedings of the 40th Session of the International Statistical Institute (Warsaw, 1975), Vol. 1. Invited papers. Bull. Inst. Internat. Statist. 46 (1975), no. 1, 393--404 (1976). MR0676341
  • Erdös, Paul. On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898--902.
  • Galvin, David. On homomorphisms from the Hamming cube to ${\bf Z}$. Israel J. Math. 138 (2003), 189--213. MR2031957
  • Kahn, Jeff. Range of cube-indexed random walk. Israel J. Math. 124 (2001), 189--201. MR1856513
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937
  • Peled, Ron. High-dimensional Lipschitz functions are typically flat, arXiv preprint arXiv:1005.4636, To appear in Annals of Probability (2010).
  • Peled, Ron; Samotij, Wojciech; Yehudayoff, Amir. Lipschitz functions on expanders are typically flat. Combin. Probab. Comput. 22 (2013), no. 4, 566--591. MR3073490
  • Propp, James Gary; Wilson, David Bruce. Exact sampling with coupled Markov chains and applications to statistical mechanics. Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995). Random Structures Algorithms 9 (1996), no. 1-2, 223--252. MR1611693


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.