Random walk in the complete graph : hitting and cover times
Preprint
- 10 January 2024
- preprint
- Published by Springer Nature in Research Square
Abstract
We consider the moments and the distribution of the hitting and cover times of a random walk in the complete graph. We study both the time needed to reach any subset of states and the time needed to visit all the states of a subset at least once. We obtain recurrence relations for the moments of all orders and we use these relations to analyze the asymptotic behavior of the hitting and cover times distributions when the number of states tends to infinity.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Hitting times on the lollipop graphProbability in the Engineering and Informational Sciences, 2025
- Random Walks: A Review of Algorithms and ApplicationsIEEE Transactions on Emerging Topics in Computational Intelligence, 2019
- Second order centrality: Distributed assessment of nodes criticity in complex networksComputer Communications, 2011
- The hitting and cover times of random walks on finite graphs using local degree informationTheoretical Computer Science, 2009
- A tight lower bound on the cover time for random walks on graphsRandom Structures & Algorithms, 1995
- A tight upper bound on the cover time for random walks on graphsRandom Structures & Algorithms, 1995
- Expected hitting and cover times of random walks on some special graphsRandom Structures & Algorithms, 1994
- Applications of Random Walks on Finite Graphs1991