{
  "id": "1606.07639",
  "version": "v1",
  "published": "2016-06-24T10:58:43.000Z",
  "updated": "2016-06-24T10:58:43.000Z",
  "title": "Mixing times of random walks on dynamic configuration models",
  "authors": [
    "Luca Avena",
    "Hakan Guldas",
    "Remco van der Hofstad",
    "Frank den Hollander"
  ],
  "comment": "21 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "The mixing time of a simple random walk on a random graph generated according to the configuration model is known to be of order $\\log n$ when $n$ is the number of vertices. In this paper we investigate what happens when the random graph becomes dynamic, namely, at each unit of time a fraction $\\alpha_n$ of the edges is randomly relocated. For degree distributions that converge and have a second moment that is bounded in $n$, we show that the mixing time is of order $1/\\sqrt{\\alpha_n}$, provided $\\lim_{n\\to\\infty} \\alpha_n(\\log n)^2=\\infty$. We identify the sharp asymptotics of the mixing time when we additionally require that $\\lim_{n\\to\\infty} \\alpha_n=0$, and relate the relevant proportionality constant to the average probability of escape from the root by a simple random walk on an augmented Galton-Watson tree which is obtained by taking a Galton-Watson tree whose offspring distribution is the size-biased version of the limiting degree distribution and attaching to its root another Galton-Watson tree with the same offspring distribution. Our proofs are based on a randomised stopping time argument in combination with coupling estimates.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-06-24T10:58:43.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "82C20",
      "05C81"
    ],
    "keywords": [
      "mixing time",
      "dynamic configuration models",
      "galton-watson tree",
      "simple random walk",
      "random graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}