  The success of Bayesian inference with MCMC depends critically on Markov
chains rapidly reaching the posterior distribution. Despite the plentitude of
inferential theory for posteriors in Bayesian non-parametrics, convergence
properties of MCMC algorithms that simulate from such ideal inferential targets
are not thoroughly understood. This work focuses on the Bayesian CART algorithm
which forms a building block of Bayesian Additive Regression Trees (BART). We
derive upper bounds on mixing times for typical posteriors under various
proposal distributions. Exploiting the wavelet representation of trees, we
provide sufficient conditions for Bayesian CART to mix well (polynomially)
under certain hierarchical connectivity restrictions on the signal. We also
derive a negative result showing that Bayesian CART (based on simple grow and
prune steps) cannot reach deep isolated signals in faster than exponential
mixing time. To remediate myopic tree exploration, we propose Twiggy Bayesian
CART which attaches/detaches entire twigs (not just single nodes) in the
proposal distribution. We show polynomial mixing of Twiggy Bayesian CART
without assuming that the signal is connected on a tree. Going further, we show
that informed variants achieve even faster mixing. A thorough simulation study
highlights discrepancies between spike-and-slab priors and Bayesian CART under
a variety of proposals.
