The Taxicab Sampler: MCMC for Discrete Spaces with Application to Tree Models

Abstract

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ïve 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.

Expanded simulation study example in Supplementary Materials and updated related Figure 2; updated Section 2 introduction and Section 2.1; added additional references in introduction section

References in corpus (3)

• A flexible regression model for count data
• Oops I Took A Gradient: Scalable Sampling for Discrete Distributions
• Dimension-free Mixing for High-dimensional Bayesian Variable Selection