A Random-Walk Concentration Principle for Occupancy Processes on Finite Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916429231554560 |
|---|---|
| author | Sclosa, Davide Mandjes, Michel Bick, Christian |
| author_facet | Sclosa, Davide Mandjes, Michel Bick, Christian |
| contents | This paper concerns discrete-time occupancy processes on a finite graph. Our results can be formulated in two theorems, which are stated for vertex processes, but also applied to edge process (e.g., dynamic random graphs). The first theorem shows that concentration of local state averages is controlled by a random walk on the graph. The second theorem concerns concentration of polynomials of the vertex states. For dynamic random graphs, this allows to estimate deviations of edge density, triangle density, and more general subgraph densities. Our results only require Lipschitz continuity and hold for both dense and sparse graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06807 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Random-Walk Concentration Principle for Occupancy Processes on Finite Graphs Sclosa, Davide Mandjes, Michel Bick, Christian Probability Combinatorics Dynamical Systems 60C05 (Primary), 05C80, 37A50 (Secondary) This paper concerns discrete-time occupancy processes on a finite graph. Our results can be formulated in two theorems, which are stated for vertex processes, but also applied to edge process (e.g., dynamic random graphs). The first theorem shows that concentration of local state averages is controlled by a random walk on the graph. The second theorem concerns concentration of polynomials of the vertex states. For dynamic random graphs, this allows to estimate deviations of edge density, triangle density, and more general subgraph densities. Our results only require Lipschitz continuity and hold for both dense and sparse graphs. |
| title | A Random-Walk Concentration Principle for Occupancy Processes on Finite Graphs |
| topic | Probability Combinatorics Dynamical Systems 60C05 (Primary), 05C80, 37A50 (Secondary) |
| url | https://arxiv.org/abs/2410.06807 |