  Recently, random walks on dynamic graphs have been studied because of its
adaptivity to dynamical settings including real network analysis. However,
previous works showed a tremendous gap between static and dynamic networks for
the cover time of a lazy simple random walk: Although $O(n^3)$ cover time was
shown for any static graphs of $n$ vertices, there is an edge-changing dynamic
graph with an exponential cover time.
  We study a lazy Metropolis walk of Nonaka, Ono, Sadakane, and Yamashita
(2010), which is a weighted random walk using local degree information. We show
that this walk is robust to an edge-changing in dynamic networks: For any
connected edge-changing graphs of $n$ vertices, the lazy Metropolis walk has
the $O(n^2)$ hitting time, the $O(n^2\log n)$ cover time, and the $O(n^2)$
coalescing time, while those times can be exponential for lazy simple random
walks. All of these bounds are tight up to a constant factor. At the heart of
the proof, we give upper bounds of those times for any reversible random walks
with a time-homogeneous stationary distribution.
