Self-switching random walks on Erdös-Rényi random graphs feel the phase transition
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917913816989696 |
|---|---|
| author | Iacobelli, Giulio Ost, Guilherme Takahashi, Daniel Y. |
| author_facet | Iacobelli, Giulio Ost, Guilherme Takahashi, Daniel Y. |
| contents | We study random walks on Erdös-Rényi random graphs in which, every time the random walk returns to the starting point, first an edge probability is independently sampled according to a priori measure $μ$, and then an Erdös-Rényi random graph is sampled according to that edge probability. When the edge probability $p$ does not depend on the size of the graph $n$ (dense case), we show that the proportion of time the random walk spends on different values of $p$ -- {\it occupation measure} -- converges to the a priori measure $μ$ as $n$ goes to infinity. More interestingly, when $p=λ/n$ (sparse case), we show that the occupation measure converges to a limiting measure with a density that is a function of the survival probability of a Poisson branching process. This limiting measure is supported on the supercritial values for the Erdös-Rényi random graphs, showing that self-witching random walks can detect the phase transition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_12355 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Self-switching random walks on Erdös-Rényi random graphs feel the phase transition Iacobelli, Giulio Ost, Guilherme Takahashi, Daniel Y. Probability Mathematical Physics We study random walks on Erdös-Rényi random graphs in which, every time the random walk returns to the starting point, first an edge probability is independently sampled according to a priori measure $μ$, and then an Erdös-Rényi random graph is sampled according to that edge probability. When the edge probability $p$ does not depend on the size of the graph $n$ (dense case), we show that the proportion of time the random walk spends on different values of $p$ -- {\it occupation measure} -- converges to the a priori measure $μ$ as $n$ goes to infinity. More interestingly, when $p=λ/n$ (sparse case), we show that the occupation measure converges to a limiting measure with a density that is a function of the survival probability of a Poisson branching process. This limiting measure is supported on the supercritial values for the Erdös-Rényi random graphs, showing that self-witching random walks can detect the phase transition. |
| title | Self-switching random walks on Erdös-Rényi random graphs feel the phase transition |
| topic | Probability Mathematical Physics |
| url | https://arxiv.org/abs/2310.12355 |