The **cover time** of a graph is the expected number of steps
needed for the random walk to visit every node of the graph
at least once. (We did not specify a start vertex. In general,
one uses the start vertex from which the random walk
talks the longest expecetd time to cover.)

The *discrete torus* modulo n is the graph on vertex set with an edge between (a,b) and (c,d)
whenever (a-c, b-d) is congruent mod n to one of (1,0), (0,1), (-1,0), (0,-1). The cover time
of this graph is asymptotic to . This was
conjectured by Aldous (1989) and proved in a paper of
Dembo, Peres, Rosen, and Zeitouni.
The proof relies on the second moment method and uses
(in a sense) the fact that the second moment method works
for percolation on d-regular complete trees (like we discussed in class).
The video below shows random walk covering the torus for n=64.