The hitting and cover times of Metropolis walks

Given a finite graph G=(V,E)G=(V,E) and a probability distribution π=(πv)v∈Vπ=(πv)v∈V on VV, Metropolis walks, i.e., random walks on GG building on the Metropolis–Hastings algorithm, obey a transition probability matrix P=(puv)u,v∈VP=(puv)u,v∈V defined by, for any u,v∈Vu,v∈V, puv={1dumin{duπvdvπu,1}if v∈N(u),1−∑w≠upuwif u=v,0otherwise , and are guaranteed to have ππ as the stationary distribution, where N(u)N(u) is the set of adjacent vertices of u∈Vu∈V and du=|N(u)|du=|N(u)| is the degree of uu. This paper shows that the hitting and the cover times of Metropolis walks are O(fn2)O(fn2) and O(fn2logn)O(fn2logn), respectively, for any graph GG of order nn and any probability distribution ππ such that f=maxu,v∈Vπu/πv<∞f=maxu,v∈Vπu/πv<∞. We also show that there are a graph GG and a stationary distribution ππ such that any   random walk on GG realizing ππ attains Ω(fn2)Ω(fn2) hitting and Ω(fn2logn)Ω(fn2logn) cover times. It follows that the hitting and the cover times of Metropolis walks are Θ(fn2)Θ(fn2) and Θ(fn2logn)Θ(fn2logn), respectively.