Mixing cutoff for simple random walks on the Chung-Lu digraph
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910618530873344 |
|---|---|
| author | Bianchi, Alessandra Passuello, Giacomo |
| author_facet | Bianchi, Alessandra Passuello, Giacomo |
| contents | In this paper, we are interested in the mixing behaviour of simple random walks on inhomogeneous directed graphs. We focus our study on the Chung-Lu digraph, which is an inhomogeneous network that generalizes the Erdős-Rényi digraph. In particular, under the Chung-Lu model, edges are included in the graph independently and according to given Bernoulli laws, so that the average degrees are fixed. To guarantee the a.s. existence of a unique reversible measure, which is implied by the strong connectivity of the graph, we assume that the average degree grows logarithmically in the size $n$ of the graph. In this weakly dense regime, we prove that the total variation distance to equilibrium displays a cutoff behaviour at the entropic time of order $\log(n)/\log\log(n)$. Moreover, we prove that on a precise window, the cutoff profile converges to the Gaussian tail function. This is qualitatively similar to what was proved in [6,7,8] for the directed configuration model, where degrees are deterministically fixed. In terms of statistical ensembles, our analysis provides an extension of these cutoff results from a hard to a soft-constrained model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15356 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mixing cutoff for simple random walks on the Chung-Lu digraph Bianchi, Alessandra Passuello, Giacomo Probability 60J10, 05C80, 05C81 In this paper, we are interested in the mixing behaviour of simple random walks on inhomogeneous directed graphs. We focus our study on the Chung-Lu digraph, which is an inhomogeneous network that generalizes the Erdős-Rényi digraph. In particular, under the Chung-Lu model, edges are included in the graph independently and according to given Bernoulli laws, so that the average degrees are fixed. To guarantee the a.s. existence of a unique reversible measure, which is implied by the strong connectivity of the graph, we assume that the average degree grows logarithmically in the size $n$ of the graph. In this weakly dense regime, we prove that the total variation distance to equilibrium displays a cutoff behaviour at the entropic time of order $\log(n)/\log\log(n)$. Moreover, we prove that on a precise window, the cutoff profile converges to the Gaussian tail function. This is qualitatively similar to what was proved in [6,7,8] for the directed configuration model, where degrees are deterministically fixed. In terms of statistical ensembles, our analysis provides an extension of these cutoff results from a hard to a soft-constrained model. |
| title | Mixing cutoff for simple random walks on the Chung-Lu digraph |
| topic | Probability 60J10, 05C80, 05C81 |
| url | https://arxiv.org/abs/2402.15356 |