{
  "id": "2110.13592",
  "version": "v1",
  "published": "2021-10-26T11:49:34.000Z",
  "updated": "2021-10-26T11:49:34.000Z",
  "title": "Analytical results for the distribution of cover times of random walks on random regular graphs",
  "authors": [
    "Ido Tishby",
    "Ofer Biham",
    "Eytan Katzav"
  ],
  "comment": "47 pages, 11 figures. arXiv admin note: text overlap with arXiv:2102.12195, arXiv:2106.10449",
  "doi": "10.1088/1751-8121/ac3a34",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech"
  ],
  "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 \\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-10-26T11:49:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cover time",
      "random regular graphs",
      "analytical results",
      "distribution",
      "random walks"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "IOP"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 47,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}