Analytical results for the distribution of cover times of random walks on random regular graphs

Ido Tishby, Ofer Biham, Eytan Katzav

Published 2021-10-26Version 1

We present analytical results for the distribution of cover times of random walks (RWs) on random regular graphs consisting of $N$ nodes of degree $c$ ($c \ge 3$). Starting from a random initial node at time $t=1$, at each time step $t \ge 2$ an RW hops into a random neighbor of its previous node. In some of the time steps the RW may visit a new, yet-unvisited node, while in other time steps it may revisit a node that has already been visited before. The cover time $T_{\rm C}$ is the number of time steps required for the RW to visit every single node in the network at least once. We derive a master equation for the distribution $P_t(S=s)$ of the number of distinct nodes $s$ visited by an RW up to time $t$ and solve it analytically. Inserting $s=N$ we obtain the cumulative distribution of cover times, namely the probability $P(T_{\rm C} \le t) = P_t(S=N)$ that up to time $t$ an RW will visit all the $N$ nodes in the network. Taking the large network limit, we show that $P(T_{\rm C} \le t)$ converges to a Gumbel distribution. We calculate the distribution of partial cover (PC) times $P( T_{{\rm PC},k} = t )$, which is the probability that at time $t$ an RW will complete visiting $k$ distinct nodes. We also calculate the distribution of random cover (RC) times $P( T_{{\rm RC},k} = t )$, which is the probability that at time $t$ an RW will complete visiting all the nodes in a subgraph of $k$ randomly pre-selected nodes at least once. The analytical results for the distributions of cover times are found to be in very good agreement with the results obtained from computer simulations.