Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.06247 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.