This post continues my series on favorite theorems of the 21st century. For an overview of the categories and my previous selections, see this earlier post. My choice for 2001 in Probability and Statistics is the theorem of Dembo, Peres, Rosen, and Zeitouni (Dembo et al. 2004), which determined the cover times of the disk and the torus for simple random walks in the plane.
Recall that if is a sequence of independent vector-valued random variables, each taking one of the four values , , , or with equal probability, then the sequence is called a simple random walk on . I have already discussed this process in this earlier post, where I focused on how often it revisits its most visited site, as well as on the probability that two independent such walks avoid each other.
Another natural question is how long one must wait before all points in a given region have been visited. In 1921, Pólya proved that a simple random walk in the plane visits every lattice point almost surely. But how long do we need to wait before it has visited, for example, every point in the disk of radius centred at the origin?
If we denote this time by , Kesten and Révész proved the existence of constants such that for every , In 1993, Lawler proved that this holds with and , and he stated a conjecture, attributed to Kesten, that the limit actually exists and is equal to .
One can ask analogous questions for random walks on finite grids. Let be the set of points such that and are integers. Let , , be a random sequence of points in such that, if , then is equally likely to be any of where addition and subtraction are taken modulo . Let be the cover time of , that is, the smallest integer such that every satisfies for some .
The problem of estimating was posed by Wilf in 1989, who called it “the white screen problem”. In the same year, Aldous conjectured that converges in probability to .
In a paper submitted in 2001, Dembo, Peres, Rosen, and Zeitouni (Dembo et al. 2004) confirmed both of these conjectures.
The proof of Theorem first reduces the problem to the corresponding question for two-dimensional Wiener processes. The key idea in the proof of that result is to study the process simultaneously across many different scales. The authors described this as a "multi-scale refinement of the classical second moment method".