{
  "id": "2406.04958",
  "version": "v1",
  "published": "2024-06-07T14:22:49.000Z",
  "updated": "2024-06-07T14:22:49.000Z",
  "title": "Meeting times of Markov chains via singular value decomposition",
  "authors": [
    "Thomas van Belle",
    "Anton Klimovsky"
  ],
  "comment": "20 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "We suggest a non-asymptotic matrix perturbation-theoretic approach to get sharp bounds on the expected meeting time of random walks on large (possibly random) graphs. We provide a formula for the expected meeting time in terms of the singular value decomposition of the diagonally killed generator of a pair of independent random walks, which we view as a perturbation of the generator. Employing a rank-one approximation of the diagonally killed generator as the proof of concept, we work out sharp bounds on the expected meeting time of simple random walks on sufficiently dense Erd\\H{o}s-R\\'enyi random graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-07T14:22:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J10",
      "60K35",
      "47A55",
      "05C81",
      "05C80",
      "60B20"
    ],
    "keywords": [
      "singular value decomposition",
      "markov chains",
      "expected meeting time",
      "non-asymptotic matrix perturbation-theoretic approach",
      "sharp bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}