Attracting random walks
© 2020, Institute of Mathematical Statistics. All rights reserved. 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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematical Statistics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/133477 |
| _version_ | 1826200626680299520 |
|---|---|
| author | Gaudio, Julia Polyanskiy, Yury |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Gaudio, Julia Polyanskiy, Yury |
| author_sort | Gaudio, Julia |
| collection | MIT |
| description | © 2020, Institute of Mathematical Statistics. All rights reserved. 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(Ω(n)) when temperature is sufficiently low. When 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. |
| first_indexed | 2024-09-23T11:39:21Z |
| format | Article |
| id | mit-1721.1/133477 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:39:21Z |
| publishDate | 2021 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/1334772023-09-19T20:25:03Z Attracting random walks Gaudio, Julia Polyanskiy, Yury Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems © 2020, Institute of Mathematical Statistics. All rights reserved. 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(Ω(n)) when temperature is sufficiently low. When 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. 2021-10-27T19:53:03Z 2021-10-27T19:53:03Z 2020 2021-04-12T16:52:55Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/133477 en 10.1214/20-EJP471 Electronic Journal of Probability Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Institute of Mathematical Statistics Electronic Journal of Statistics |
| spellingShingle | Gaudio, Julia Polyanskiy, Yury Attracting random walks |
| title | Attracting random walks |
| title_full | Attracting random walks |
| title_fullStr | Attracting random walks |
| title_full_unstemmed | Attracting random walks |
| title_short | Attracting random walks |
| title_sort | attracting random walks |
| url | https://hdl.handle.net/1721.1/133477 |
| work_keys_str_mv | AT gaudiojulia attractingrandomwalks AT polyanskiyyury attractingrandomwalks |