Mixing trichotomy for random walks on directed stochastic block models
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908794920894464 |
|---|---|
| author | Bianchi, Alessandra Passuello, Giacomo Quattropani, Matteo |
| author_facet | Bianchi, Alessandra Passuello, Giacomo Quattropani, Matteo |
| contents | We consider a directed version of the classical Stochastic Block Model with $m\ge 2$ communities and a parameter $α$ controlling the inter-community connectivity. We show that, depending on the scaling of $α$, the mixing time of the random walk on this graph can exhibit three different behaviors, which we refer to as subcritical, critical and supercritical. In the subcritical regime, the total variation distance to equilibrium decays abruptly, providing the occurrence of the so-called cutoff phenomenon. In the supercritical regime, the mixing is governed by the inter-community jumps, and the random walk exhibits a metastable behavior: at first it collapses to a local equilibrium, then, on a larger timescale, it can be effectively described as a mean-field process on the $m$ communities, with a decay to equilibrium which is asymptotically smooth and exponential. Finally, for the critical regime, we show a sort of interpolation of the two above-mentioned behaviors. Although the metastable behavior shown in the supercritical regime appears natural from a heuristic standpoint, a substantial part of our analysis can be read as a control on the homogenization of the underlying random environment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06851 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mixing trichotomy for random walks on directed stochastic block models Bianchi, Alessandra Passuello, Giacomo Quattropani, Matteo Probability 60J10, 05C80, 05C81 We consider a directed version of the classical Stochastic Block Model with $m\ge 2$ communities and a parameter $α$ controlling the inter-community connectivity. We show that, depending on the scaling of $α$, the mixing time of the random walk on this graph can exhibit three different behaviors, which we refer to as subcritical, critical and supercritical. In the subcritical regime, the total variation distance to equilibrium decays abruptly, providing the occurrence of the so-called cutoff phenomenon. In the supercritical regime, the mixing is governed by the inter-community jumps, and the random walk exhibits a metastable behavior: at first it collapses to a local equilibrium, then, on a larger timescale, it can be effectively described as a mean-field process on the $m$ communities, with a decay to equilibrium which is asymptotically smooth and exponential. Finally, for the critical regime, we show a sort of interpolation of the two above-mentioned behaviors. Although the metastable behavior shown in the supercritical regime appears natural from a heuristic standpoint, a substantial part of our analysis can be read as a control on the homogenization of the underlying random environment. |
| title | Mixing trichotomy for random walks on directed stochastic block models |
| topic | Probability 60J10, 05C80, 05C81 |
| url | https://arxiv.org/abs/2504.06851 |