The taxicab sampler: MCMC for discrete spaces with application to tree models

Vincent Geels, Matthew T. Pratola, Radu Herbei

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish (US)
Pages (from-to)1-22
Number of pages22
JournalJournal of Statistical Computation and Simulation
StatePublished - Sep 29 2022
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2022-10-03
Acknowledged KAUST grant number(s): OSR-2018-CRG7-3800.3
Acknowledgements: The work of Matthew T. Pratola was supported in part by the National Science Foundation (NSF) under Agreements DMS-1564395 and DMS-1916231 and in part by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) under Award No. OSR-2018-CRG7-3800.3.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

ASJC Scopus subject areas

  • Modeling and Simulation
  • Applied Mathematics
  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'The taxicab sampler: MCMC for discrete spaces with application to tree models'. Together they form a unique fingerprint.

Cite this