Random walk metropolis chains on the hypercube.

摘要

We consider the Metropolis algorithm for the distribution π( x) = &thetas;S (x) (1 + &thetas;) −n on the hypercube X = {0, 1}n, where S( x) is the number of ones in x ∈ {0, 1} n and &thetas; ∈ (0, 1] is a constant. The lazy random walk Metropolis algorithm for this model specifies a Markov chain ( Xt) on X that is known to have cutoff at 11+q n log n with window size n, a result derived with Fourier analysis by Diaconis and Hanlon (1992) and Ross and Xu (1994). In this work we give a new proof of this result that is purely probabilistic. It uses coupling and a projection to a two-dimensional Markov chain Xt → (S( Xt), d(X0, Xt)), where d(X 0, ·) is the Hamming distance to the starting state X0. Next we generalize this result to a broader class of distributions π on the hypercube. The distributions we consider are also unimodal and radially symmetric. Under certain smoothness conditions on π, we show that when started at an endpoint, the random walk Metropolis algorithm has cutoff of order n log n in this entire class of distributions.