# Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2016.

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

- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Improved Financial Forecasting via Quantum Machine Learning](https://mlsanity.com/paper/2306.12965/) (2023)
- [Batch Active Learning of Reward Functions from Human Preferences](https://mlsanity.com/paper/2402.15757/) (2024)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Hardness of Maximum Likelihood Learning of DPPs](https://mlsanity.com/paper/2205.12377/) (2022)
- [Mixtures of All Trees](https://mlsanity.com/paper/2302.14202/) (2023)
- [Learning with latent group sparsity via heat flow dynamics on networks](https://mlsanity.com/paper/2201.08326/) (2022)
- [Learning under Latent Group Sparsity via Diffusion on Networks](https://mlsanity.com/paper/2507.15097/) (2025)

## Abstract (arXiv)

We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures, and develop fast Markov chain samplers for them. Our first main result is for MCMC sampling from Strongly Rayleigh (SR) measures, for which we present sharp polynomial bounds on the mixing time. As a corollary, this result yields a fast mixing sampler for Determinantal Point Processes (DPPs), yielding (to our knowledge) the first provably fast MCMC sampler for DPPs since their inception over four decades ago. Beyond SR measures, we develop MCMC samplers for probabilistic models with hard constraints and identify sufficient conditions under which their chains mix rapidly. We illustrate our claims by empirically verifying the dependence of mixing times on the key factors governing our theoretical bounds.