  Motivated by the problem of exploring discrete but very complex state spaces
in Bayesian models, we propose a novel Markov Chain Monte Carlo search
algorithm: the taxicab sampler. We describe the construction of this sampler
and discuss how its interpretation and usage differs from that of standard
Metropolis-Hastings as well as the related Hamming ball sampler. The proposed
sampling algorithm is then shown to demonstrate substantial improvement in
computation time without any loss of efficiency relative to a na\"ive
Metropolis-Hastings search in a motivating Bayesian regression tree count
model, in which we leverage the discrete state space assumption to construct a
novel likelihood function that allows for flexibly describing different
mean-variance relationships while preserving parameter interpretability
compared to existing likelihood functions for count data.
