Hitting Time Distributions of Random Walks on Finite Graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912693222375424 |
|---|---|
| author | Kumar, Anuraag |
| author_facet | Kumar, Anuraag |
| contents | We investigate the hitting times of random walks on graphs, where a hitting time is defined as the number of steps required for a random walker to move from one node to another. While much of the existing literature focuses on calculating or bounding expected hitting times, this approach is insufficient, as hitting time distributions often exhibit high variance. To address this gap, we analyze both the full distributions and variances of hitting times. Using general Markov chain techniques, as well as Fourier and spectral methods, we derive formulas and recurrence relations for computing these distributions. This is a preliminary work, and some results are being refined. A journal version will be available soon. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_04985 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hitting Time Distributions of Random Walks on Finite Graphs Kumar, Anuraag Probability Spectral Theory 60J10, 05C81, 05C50 We investigate the hitting times of random walks on graphs, where a hitting time is defined as the number of steps required for a random walker to move from one node to another. While much of the existing literature focuses on calculating or bounding expected hitting times, this approach is insufficient, as hitting time distributions often exhibit high variance. To address this gap, we analyze both the full distributions and variances of hitting times. Using general Markov chain techniques, as well as Fourier and spectral methods, we derive formulas and recurrence relations for computing these distributions. This is a preliminary work, and some results are being refined. A journal version will be available soon. |
| title | Hitting Time Distributions of Random Walks on Finite Graphs |
| topic | Probability Spectral Theory 60J10, 05C81, 05C50 |
| url | https://arxiv.org/abs/2511.04985 |