{
  "id": "2401.07896",
  "version": "v1",
  "published": "2024-01-15T18:52:35.000Z",
  "updated": "2024-01-15T18:52:35.000Z",
  "title": "Hitting times for Random Walks on the stochastic block model",
  "authors": [
    "Matthias Löwe",
    "Sara Terveer"
  ],
  "comment": "26 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "We analyze hitting times of simple random walk on realizations of the stochastic block model. We show that under some natural assumptions the average starting hitting time as well as the average target hitting time are asymptotically almost surely given by $N(1+o(1))$. We also show a central limit theorem for the average target hitting time. Our main techniques are a spectral decomposition of these hitting times, a spectral analysis of the adjacency matrix and the graph Laplacian, respectively, as well as a form of the Delta method.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-01-15T18:52:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C81",
      "05C80",
      "60F05"
    ],
    "keywords": [
      "stochastic block model",
      "average target hitting time",
      "simple random walk",
      "central limit theorem",
      "graph laplacian"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}