# The Hamming Ball Sampler

arXiv: https://arxiv.org/abs/1504.08133 · HTML: https://mlsanity.com/paper/1504.08133/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2015.

## Built on by (most cited first, 16 of 16)

- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Jointly Learning Consistent Causal Abstractions Over Multiple Interventional Distributions](https://mlsanity.com/paper/2301.05893/) (2023)
- [Enhanced gradient-based MCMC in discrete spaces](https://mlsanity.com/paper/2208.00040/) (2022)
- [Optimal Scaling for Locally Balanced Proposals in Discrete Spaces](https://mlsanity.com/paper/2209.08183/) (2022)
- [Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC](https://mlsanity.com/paper/2102.02374/) (2021)
- [LSB: Local Self-Balancing MCMC in Discrete Spaces](https://mlsanity.com/paper/2109.03867/) (2021)
- [Gradient GA: Gradient Genetic Algorithm for Drug Molecular Design](https://mlsanity.com/paper/2502.09860/) (2025)
- [Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces](https://mlsanity.com/paper/2404.03867/) (2024)
- [Bayesian Variable Selection in a Million Dimensions](https://mlsanity.com/paper/2208.01180/) (2022)
- [Entropy-Guided Sampling of Flat Modes in Discrete Spaces](https://mlsanity.com/paper/2505.02296/) (2025)
- [Importance is Important: Generalized Markov Chain Importance Sampling Methods](https://mlsanity.com/paper/2304.06251/) (2023)
- [Optimal Particle-based Approximation of Discrete Distributions (OPAD)](https://mlsanity.com/paper/2412.00545/) (2024)

## Abstract (arXiv)

We introduce the Hamming Ball Sampler, a novel Markov Chain Monte Carlo algorithm, for efficient inference in statistical models involving high-dimensional discrete state spaces. The sampling scheme uses an auxiliary variable construction that adaptively truncates the model space allowing iterative exploration of the full model space in polynomial time. The approach generalizes conventional Gibbs sampling schemes for discrete spaces and can be considered as a Big Data-enabled MCMC algorithm that provides an intuitive means for user-controlled balance between statistical efficiency and computational tractability. We illustrate the generic utility of our sampling algorithm through application to a range of statistical models.