Cover times of many random walkers on a discrete network
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911949840711680 |
|---|---|
| author | Kim, Hyunjoong Lawley, Sean D |
| author_facet | Kim, Hyunjoong Lawley, Sean D |
| contents | The speed of an exhaustive search can be measured by a cover time, which is defined as the time it takes a random searcher to visit every state in some target set. Cover times have been studied in both the physics and probability literatures, with most prior works focusing on a single searcher. In this paper, we prove an explicit formula for all the moments of the cover time for many searchers on an arbitrary discrete network. Our results show that such cover times depend only on properties of the network along the shortest paths to the most distant parts of the target. This mere local dependence contrasts with the well-known result that cover times for single searchers depend on global properties of the network. We illustrate our rigorous results by stochastic simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07905 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cover times of many random walkers on a discrete network Kim, Hyunjoong Lawley, Sean D Statistical Mechanics Probability 60J27, 60G70, 60G07 The speed of an exhaustive search can be measured by a cover time, which is defined as the time it takes a random searcher to visit every state in some target set. Cover times have been studied in both the physics and probability literatures, with most prior works focusing on a single searcher. In this paper, we prove an explicit formula for all the moments of the cover time for many searchers on an arbitrary discrete network. Our results show that such cover times depend only on properties of the network along the shortest paths to the most distant parts of the target. This mere local dependence contrasts with the well-known result that cover times for single searchers depend on global properties of the network. We illustrate our rigorous results by stochastic simulations. |
| title | Cover times of many random walkers on a discrete network |
| topic | Statistical Mechanics Probability 60J27, 60G70, 60G07 |
| url | https://arxiv.org/abs/2310.07905 |