  We apply the power-of-two-choices paradigm to a random walk on a graph:
rather than moving to a uniform random neighbour at each step, a controller is
allowed to choose from two independent uniform random neighbours. We prove that
this allows the controller to significantly accelerate the hitting and cover
times in several natural graph classes. In particular, we show that the cover
time becomes linear in the number $n$ of vertices on discrete tori and bounded
degree trees, of order $\mathcal{O}(n \log \log n)$ on bounded degree
expanders, and of order $\mathcal{O}(n (\log \log n)^2)$ on the
Erd\H{o}s-R\'{e}nyi random graph in a certain sparsely connected regime. We
also consider the algorithmic question of computing an optimal strategy, and
prove a dichotomy in efficiency between computing strategies for hitting and
cover times.
