{
  "id": "2212.00958",
  "version": "v1",
  "published": "2022-12-02T03:59:49.000Z",
  "updated": "2022-12-02T03:59:49.000Z",
  "title": "A local central limit theorem for random walks on expander graphs",
  "authors": [
    "Rafael Chiclana",
    "Yuval Peres"
  ],
  "comment": "13 pages, 0 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "On a regular graph $G=(V,E)$, consider a function $\\operatorname{val} \\colon V \\longrightarrow \\{0,1\\}$ that labels the vertices of $G$, and let $(X_i)$ be the simple random walk on $G$ started from a vertex chosen uniformly at random. In this work, we show that the Hamming weight of the sequence of bits $(\\operatorname{val}(X_i))$ satisfies a local central limit theorem when the graph $G$ is expander. As a consequence, we study the pseudorandomness of random walks on expander graphs against test computed by symmetric functions $f\\colon \\{0,1\\}^t \\longrightarrow \\{0,1\\}$. We also show that the Hamming weight of $(\\operatorname{val}(X_i))$ has the same asymptotic behavior as the Hamming weight of the sticky random walk.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-02T03:59:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C81",
      "05C48"
    ],
    "keywords": [
      "local central limit theorem",
      "expander graphs",
      "hamming weight",
      "sticky random walk",
      "simple random walk"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}