The Exact Mixing Time for Trees with Fixed Diameter
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |