Đang chuẩn bị liên kết để tải về tài liệu:
Đề tài " Cover times for Brownian motionand random walks in two dimensions "

Let T (x, ε) denote the first hitting time of the disc of radius ε centered at x for Brownian motion on the two dimensional torus T2 . We prove that supx∈T2 T (x, ε)/| log ε|2 → 2/π as ε → 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 Z2 is asymptotic to 4n2 (log. | Annals of Mathematics Cover times for Brownian motionand random walks in two dimensions By Amir Dembo Yuval Peres Jay Rosen and Ofer Zeitouni Annals of Mathematics 160 2004 433 464 Cover times for Brownian motion and random walks in two dimensions By Amir Dembo Yuval Peres JAy Rosen and Ofer Zeitouni Abstract Let T x e denote the first hitting time of the disc of radius e centered at x for Brownian motion on the two dimensional torus T2. We prove that sup eT2 T x e log e 2 2 n as e 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 Z2 is asymptotic to 4n2 logn 2 n. 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 nonrigorously 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 Z2 to cover the disc of radius n. 1. Introduction In this paper we introduce a unified method for analyzing cover times for random walks and Brownian motion in two dimensions and resolve several open problems in this area. 1.1. Covering the discrete torus. The time it takes a random walk to cover a finite graph is a parameter that has been studied intensively by probabilists combinatorialists and computer scientists due to its intrinsic appeal and its applications to designing universal traversal sequences 5 10 11 testing graph connectivity 5 19 and protocol testing 24 see 2 for an introduction The research of A. Dembo was partially supported by NSF grant DMS-0072331. The research of Y. Peres was partially supported by NSF grant DMS-9803597. The research of J. Rosen was supported in part by grants from