{
  "id": "math/0107191",
  "version": "v2",
  "published": "2001-07-26T10:08:25.000Z",
  "updated": "2003-11-27T03:28:30.000Z",
  "title": "Cover Times for Brownian Motion and Random Walks in Two Dimensions",
  "authors": [
    "Amir Dembo",
    "Yuval Peres",
    "Jay Rosen",
    "Ofer Zeitouni"
  ],
  "comment": "Conflict between definitions of constants in section 5 cleared on November 26, 2003",
  "categories": [
    "math.PR",
    "math.CO",
    "math.DG"
  ],
  "abstract": "Let T(x,r) denote the first hitting time of the disc of radius r centered at x for Brownian motion on the two dimensional torus. We prove that sup_{x} T(x,r)/|log r|^2 --> 2/pi as r --> 0. The same applies to Brownian motion on any smooth, compact connected, two-dimensional, Riemannian manifold with unit area and no boundary. As a consequence, we prove a conjecture, due to Aldous (1989), that the number of steps it takes a simple random walk to cover all points of the lattice torus Z_n^2 is asymptotic to (2n log n)^2/pi. Determining these asymptotics is an essential step toward analyzing the fractal structure of the set of uncovered sites before coverage is complete; so far, this structure was only studied non-rigorously in the physics literature. We also establish a conjecture, due to Kesten and Revesz, that describes the asymptotics for the number of steps needed by simple random walk in Z^2 to cover the disc of radius n.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2003-11-27T03:28:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "brownian motion",
      "cover times",
      "simple random walk",
      "dimensions",
      "asymptotic"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2001math......7191D"
    }
  }
}