  Structure learning via MCMC sampling is known to be very challenging because
of the enormous search space and the existence of Markov equivalent DAGs.
Theoretical results on the mixing behavior are lacking. In this work, we prove
the rapid mixing of a random walk Metropolis-Hastings algorithm, which reveals
that the complexity of Bayesian learning of sparse equivalence classes grows
only polynomially in $n$ and $p$, under some high-dimensional assumptions. A
series of high-dimensional consistency results is obtained, including the
strong selection consistency of an empirical Bayes model for structure
learning. Our proof is based on two new results. First, we derive a general
mixing time bound on finite state spaces, which can be applied to local MCMC
schemes for other model selection problems. Second, we construct
high-probability search paths on the space of equivalence classes with node
degree constraints by proving a combinatorial property of DAG comparisons.
Simulation studies on the proposed MCMC sampler are conducted to illustrate the
main theoretical findings.
