Mathematics – Probability
Scientific paper
2011-12-19
Mathematics
Probability
Scientific paper
We consider the Metropolis algorithm for the distribution \pi(x) = \theta^{S(x)} (1+\theta)^{-n} on the hypercube X=\{0,1\}^n, where S(x) is the number of ones in x \in \{0,1\}^n and \theta \in (0,1] is a constant. For n = {nu \choose 2} this distribution corresponds to the Erd"os-R\'enyi random graph model on nu vertices, where each edge is present independently with probability \frac{\theta}{1+\theta}. The lazy random walk Metropolis algorithm for this model specifies a Markov chain (X_t) on X that is known to have cutoff at \frac{1}{1+\theta} n \log n with window size n, a result derived by Fourier analyis in Diaconis and Hanlon (1992) and Ross and Xu (1994). In this work we give a new proof of this result that is purely probabilistic. This is done in the hope that probabilistic techniques will be easier to generalize to other, less symmetric distributions \pi. Our proof uses coupling and a projection to a two-dimensional Markov chain X_t \rightarrow (S(X_t),d(X_0,X_t)), where d(X_0,\cdot) is the Hamming distance to the starting state X_0.
No associations
LandOfFree
A probabilistic proof of cutoff in the Metropolis algorithm for the Erd"os-R'enyi random graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A probabilistic proof of cutoff in the Metropolis algorithm for the Erd"os-R'enyi random graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A probabilistic proof of cutoff in the Metropolis algorithm for the Erd"os-R'enyi random graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-210218