Attracting random walks. (English) Zbl 1456.60177

Gaudio, Julia; Polyanskiy, Yury

Electron. J. Probab. 25, Paper No. 73, 31 p. (2020).

Summary: This paper introduces the attracting random walks model, which describes the dynamics of a system of particles on a graph with \(n\) vertices. At each step, a single particle moves to an adjacent vertex (or stays at the current one) with probability proportional to the exponent of the number of other particles at a vertex. From an applied standpoint, the model captures the rich get richer phenomenon. We show that the Markov chain exhibits a phase transition in mixing time, as the parameter governing the attraction is varied. Namely, mixing time is \(O(n\log n)\) when the temperature is sufficiently high and \(\exp (\Omega (n))\) when temperature is sufficiently low. When \(\mathcal{G}\) is the complete graph, the model is a projection of the Potts model, whose mixing properties and the critical temperature have been known previously. However, for any other graph our model is non-reversible and does not seem to admit a simple Gibbsian description of a stationary distribution. Notably, we demonstrate existence of the dynamic phase transition without decomposing the stationary distribution into phases.

MSC:

60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
60K35	Interacting random processes; statistical mechanics type models; percolation theory

Keywords:

Markov chains; Potts model; interacting particle systems

References:

[1]	D. Bertsimas and J. N. Tsitsiklis, Introduction to linear optimization, Athena Scientific, Dynamic Ideas, 1997.
[2]	P. Cuff, J. Ding, O. Louidor, E. Lubetzky, Y. Peres, and A. Sly, Glauber dynamics for the mean-field Potts model, Journal of Statistical Physics 149 (2012), 432-477. · Zbl 1254.82024
[3]	J. A. Fill, Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the Exclusion Process, The Annals of Applied Probability 1 (1991), no. 1, 62-87. · Zbl 0726.60069 · doi:10.1214/aoap/1177005981
[4]	Julia Gaudio, Investigations in applied probability and high-dimensional statistics, Ph.D. thesis, Massachusetts Institute of Technology, 2020.
[5]	Thomas P. Hayes and Eric Vigoda, Variable length path coupling, Random Structures and Algorithms 31 (2007), no. 3, 251-272. · Zbl 1137.60032 · doi:10.1002/rsa.20166
[6]	David A. Levin and Yuval Peres, Markov chains and mixing times, 2 ed., American Mathematical Society, 2017. · Zbl 1391.60175 · doi:10.4169/amer.math.monthly.124.7.637
[7]	R.