{
  "id": "1001.0355",
  "version": "v2",
  "published": "2010-01-03T07:31:53.000Z",
  "updated": "2010-07-11T14:42:20.000Z",
  "title": "Entropy of random walk range on uniformly transient and on uniformly recurrent graphs",
  "authors": [
    "David Windisch"
  ],
  "comment": "17 pages, 2 figures",
  "journal": "Electronic Journal of Probability 2010, Vol. 15, 1143-1160",
  "categories": [
    "math.PR"
  ],
  "abstract": "We study the entropy of the distribution of the set R_n of vertices visited by a simple random walk on a graph with bounded degrees in its first n steps. It is shown that this quantity grows linearly in the expected size of R_n if the graph is uniformly transient, and sublinearly in the expected size if the graph is uniformly recurrent with subexponential volume growth. This in particular answers a question asked by Benjamini, Kozma, Yadin and Yehudayoff (arXiv:0903.3179v1).",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-07-11T14:42:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C81",
      "60C05"
    ],
    "keywords": [
      "random walk range",
      "uniformly recurrent graphs",
      "uniformly transient",
      "simple random walk",
      "subexponential volume growth"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}