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

- Authors
- Type
- Published Article
- Journal
- Journal of Physics A: Mathematical and Theoretical
- Publisher
- IOP Publishing
- Publication Date
- Dec 08, 2021
- Volume
- 55
- Issue
- 1
- Identifiers
- DOI: 10.1088/1751-8121/ac3a34
- Source
- ioppublishing
- Keywords
- Disciplines
- License
- Unknown

## Abstract

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 ⩾ 3). Starting from a random initial node at time t = 1, at each time step t ⩾ 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 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 C ⩽ 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 C ⩽ t) converges to a Gumbel distribution. We calculate the distribution of partial cover (PC) times P(T 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 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.