Skip to main content
Max's user avatar
Max's user avatar
Max's user avatar
Max
  • Member for 13 years, 11 months
awarded
comment
Reference Request: Cover time for simple random walk on $n \times n$ torus
For the case of $n\times n$ grid, I don't know the exact rate but I can provide an upper bound on the cover time. By the same Matthews method (Theorem 11.2 of the reference), the cover time is bounded from above by the (largest) hitting time multiplied by $2\log n$. The largest hitting time in this case is of order $n^2\log n$, which can be calculated through effective resistance and commute time identity (Propositions 9.16 and 10.6). Therefore, the cover time in the grid case can be bounded by $O(n^2(\log n)^2)$ too.
comment
Reference Request: Cover time for simple random walk on $n \times n$ torus
Actually, if you look at the notes on p. 152, for your original problem, the expected cover time $E(\tau_{cov}) \sim \frac4\pi n^2(\log n)^2$.
Loading…
awarded
answered
Loading…
awarded
answered
Loading…
Loading…