# Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2016.

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

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Improved Financial Forecasting via Quantum Machine Learning](https://mlsanity.com/paper/2306.12965/) (2023)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Batch Active Learning of Reward Functions from Human Preferences](https://mlsanity.com/paper/2402.15757/) (2024)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](https://mlsanity.com/paper/2102.13382/) (2021)
- [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)
- [Dual Representation Learning for Out-of-Distribution Detection](https://mlsanity.com/paper/2206.09387/) (2022)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Designing Data: Proactive Data Collection and Iteration for Machine Learning](https://mlsanity.com/paper/2301.10319/) (2023)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [Establishing Reliability Metrics for Reward Models in Large Language Models](https://mlsanity.com/paper/2504.14838/) (2025)
- [On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling](https://mlsanity.com/paper/2103.11107/) (2021)
- [Decentralized Gaussian Process Classification and an Application in Subsea Robotics](https://mlsanity.com/paper/2511.15529/) (2025)
- [Greedy Volume Maximization of Gradient Embeddings for Long-Tailed Frame-Level Bioacoustic Active Learning](https://mlsanity.com/paper/2607.13555/) (2026)
- [Fair Multi-View Determinantal Coresets via Adaptive NEPv](https://mlsanity.com/paper/2608.18181/) (2026)

## Abstract (arXiv)

Strongly Rayleigh distributions are natural generalizations of product and determinantal probability distributions and satisfy strongest form of negative dependence properties. We show that the "natural" Monte Carlo Markov Chain (MCMC) is rapidly mixing in the support of a em homogeneous strongly Rayleigh distribution. As a byproduct, our proof implies Markov chains can be used to efficiently generate approximate samples of a k-determinantal point process. This answers an open question raised by Deshpande and Rademacher.