Random Walks and the Meeting Time for Trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913975006920704 |
|---|---|
| author | Beveridge, Andrew Bridenbaugh, Ben Pomerance, Ari Holcombe |
| author_facet | Beveridge, Andrew Bridenbaugh, Ben Pomerance, Ari Holcombe |
| contents | Consider a random walk on a tree $G=(V,E)$. For $v,w \in V$, let the hitting time $H(v,w)$ denote the expected number of steps required for the random walk started at $v$ to reach $w$, and let $π_v = \mathrm{deg}(v)/2|E|$ denote the stationary distribution for the random walk. We characterize the extremal tree structures for the meeting time $T_{\mathrm{meet}}(G) = \max_{w \in V} \sum_{v \in V} π_v H(v,w)$. For fixed order $n$ and diameter $d$, the meeting time is maximized by the broom graph. The meeting time is minimized by the balanced double broom graph, or a slight variant, depending on the relative parities of $n$ and $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02804 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Random Walks and the Meeting Time for Trees Beveridge, Andrew Bridenbaugh, Ben Pomerance, Ari Holcombe Combinatorics Probability 05C81 (primary), 05C05 (secondary), 60J10 (secondary) Consider a random walk on a tree $G=(V,E)$. For $v,w \in V$, let the hitting time $H(v,w)$ denote the expected number of steps required for the random walk started at $v$ to reach $w$, and let $π_v = \mathrm{deg}(v)/2|E|$ denote the stationary distribution for the random walk. We characterize the extremal tree structures for the meeting time $T_{\mathrm{meet}}(G) = \max_{w \in V} \sum_{v \in V} π_v H(v,w)$. For fixed order $n$ and diameter $d$, the meeting time is maximized by the broom graph. The meeting time is minimized by the balanced double broom graph, or a slight variant, depending on the relative parities of $n$ and $d$. |
| title | Random Walks and the Meeting Time for Trees |
| topic | Combinatorics Probability 05C81 (primary), 05C05 (secondary), 60J10 (secondary) |
| url | https://arxiv.org/abs/2508.02804 |