The Exact Mixing Time for Trees with Fixed Diameter
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_ | 1866918110739562496 |
|---|---|
| author | Beveridge, Andrew Heysse, Kristin O'Higgins, Rhys Vescovo, Lola |
| author_facet | Beveridge, Andrew Heysse, Kristin O'Higgins, Rhys Vescovo, Lola |
| contents | We characterize the extremal structure for the exact mixing time for random walks on trees $T_{n,d}$ of order $n$ with diameter $d$. Given a graph $G=(V,E)$, let $H(v,π)$ denote the expected length of an optimal stopping rule from vertex $v$ to the stationary distributon $π$. We show that the quantity $\max_{G \in T_{n,d} } T_{\mbox{mix}}(G) = \max_{G \in T_{n,d} } \max_{v \in V} H(v,π)$ is achieved uniquely by the balanced double broom. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06247 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Exact Mixing Time for Trees with Fixed Diameter Beveridge, Andrew Heysse, Kristin O'Higgins, Rhys Vescovo, Lola Combinatorics Probability 05C81, 05C05 We characterize the extremal structure for the exact mixing time for random walks on trees $T_{n,d}$ of order $n$ with diameter $d$. Given a graph $G=(V,E)$, let $H(v,π)$ denote the expected length of an optimal stopping rule from vertex $v$ to the stationary distributon $π$. We show that the quantity $\max_{G \in T_{n,d} } T_{\mbox{mix}}(G) = \max_{G \in T_{n,d} } \max_{v \in V} H(v,π)$ is achieved uniquely by the balanced double broom. |
| title | The Exact Mixing Time for Trees with Fixed Diameter |
| topic | Combinatorics Probability 05C81, 05C05 |
| url | https://arxiv.org/abs/2411.06247 |