Cover times and generic chaining
arXiv:1207.1024
Abstract
A recent result of Ding, Lee and Peres expresses the cover time of the random walk on a graph in terms of generic chaining for the commute distance. Their proof is very involved and the purpose of this article is to present a simpler approach to this problem based on elementary hitting times estimates and chaining arguments. Unfortunately we fail to recover their full result, but not by much.
v2: added an example showing the gap between our lower bound and DLP's and corrected a few typos