We derive an exact closed-form analytical expression for the distribution of the cover time for a random walk over an arbitrary graph. In special case, we derive simplified exact expressions for the distributions of cover time for a complete graph, a cycle graph, and a path graph. An accurate approximation for the cover time distribution, with computational complexity of $O\left(2n\right)$, is also presented. The approximation is numerically tested only for graphs with $n\le 1000$ nodes.

• Received 22 April 2009

DOI:https://doi.org/10.1103/PhysRevE.80.041102