Faster random walks via infrequent steering
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911694992703488 |
|---|---|
| author | Bukh, Boris Dubroff, Quentin |
| author_facet | Bukh, Boris Dubroff, Quentin |
| contents | Random walks on graphs can be slow. To speed them up, imagine that at each step instead of choosing the neighbor at random, there is a small probability $\varepsilon>0$ that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that it visits every vertex in $n^{1+o(1)}$ steps with high probability. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18712 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster random walks via infrequent steering Bukh, Boris Dubroff, Quentin Probability Combinatorics Random walks on graphs can be slow. To speed them up, imagine that at each step instead of choosing the neighbor at random, there is a small probability $\varepsilon>0$ that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that it visits every vertex in $n^{1+o(1)}$ steps with high probability. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces. |
| title | Faster random walks via infrequent steering |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2605.18712 |