# Perfect Sampling from Pairwise Comparisons arXiv: https://arxiv.org/abs/2211.12868 ยท HTML: https://mlsanity.com/paper/2211.12868/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 107 references that are in the map. - First posted on arXiv 23 Nov 2022. ## Builds on (most cited first, 30 of 32) - [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015) - [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015) - [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017) - [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015) - [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018) - [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014) - [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020) - [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019) - [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021) - [Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition](https://mlsanity.com/paper/1812.00793/) (2018) - [Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning](https://mlsanity.com/paper/1911.07357/) (2019) - [Efficiently Learning Mixtures of Mallows Models](https://mlsanity.com/paper/1808.05731/) (2018) - [Efficient Parameter Estimation of Truncated Boolean Product Distributions](https://mlsanity.com/paper/2007.02392/) (2020) - [Truncated Linear Regression in High Dimensions](https://mlsanity.com/paper/2007.14539/) (2020) - [Optimal Learning of Mallows Block Model](https://mlsanity.com/paper/1906.01009/) (2019) - [On the Analysis of EM for truncated mixtures of two Gaussians](https://mlsanity.com/paper/1902.06958/) (2019) - [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016) - [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021) - [Faster Algorithms for Testing under Conditional Sampling](https://mlsanity.com/paper/1504.04103/) (2015) - [Aggregating Incomplete and Noisy Rankings](https://mlsanity.com/paper/2011.00810/) (2020) - [Learning to Sample from Censored Markov Random Fields](https://mlsanity.com/paper/2101.06178/) (2021) - [A Chasm Between Identity and Equivalence Testing with Conditional Queries](https://mlsanity.com/paper/1411.7346/) (2014) - [Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing](https://mlsanity.com/paper/1807.06168/) (2018) - [Efficient Statistics for Sparse Graphical Models from Truncated Samples](https://mlsanity.com/paper/2006.09735/) (2020) - [Perfect Sampling for (Atomic) Lov'asz Local Lemma](https://mlsanity.com/paper/2107.03932/) (2021) - [Big Data on the Rise: Testing monotonicity of distributions](https://mlsanity.com/paper/1501.06783/) (2015) - [Faster Sublinear Algorithms using Conditional Sampling](https://mlsanity.com/paper/1608.04759/) (2016) - [Bernoulli Factories and Black-Box Reductions in Mechanism Design](https://mlsanity.com/paper/1703.04143/) (2017) - [Sampling Correctors](https://mlsanity.com/paper/1504.06544/) (2015) - [Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing](https://mlsanity.com/paper/2106.15992/) (2021) ## Built on by (most cited first, 6 of 6) - [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023) - [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024) - [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024) - [Position: Causal Machine Learning Requires Rigorous Synthetic Experiments for Broader Adoption](https://mlsanity.com/paper/2508.08883/) (2025) - [Learning Distributions from Multiple Data Providers](https://mlsanity.com/paper/2607.24732/) (2026) - [Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction](https://mlsanity.com/paper/2608.06262/) (2026) ## Abstract (arXiv) In this work, we study how to efficiently obtain perfect samples from a discrete distribution D given access only to pairwise comparisons of elements of its support. Specifically, we assume access to samples (x, S), where S is drawn from a distribution over sets Q (indicating the elements being compared), and x is drawn from the conditional distribution DS (indicating the winner of the comparison) and aim to output a clean sample y distributed according to D. We mainly focus on the case of pairwise comparisons where all sets S have size 2. We design a Markov chain whose stationary distribution coincides with D and give an algorithm to obtain exact samples using the technique of Coupling from the Past. However, the sample complexity of this algorithm depends on the structure of the distribution D and can be even exponential in the support of D in many natural scenarios. Our main contribution is to provide an efficient exact sampling algorithm whose complexity does not depend on the structure of D. To this end, we give a parametric Markov chain that mixes significantly faster given a good approximation to the stationary distribution. We can obtain such an approximation using an efficient learning from pairwise comparisons algorithm (Shah et al., JMLR 17, 2016). Our technique for speeding up sampling from a Markov chain whose stationary distribution is approximately known is simple, general and possibly of independent interest.