  In this work, we study how to efficiently obtain perfect samples from a
discrete distribution $\mathcal{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 $\mathcal{Q}$ (indicating the
elements being compared), and $x$ is drawn from the conditional distribution
$\mathcal{D}_S$ (indicating the winner of the comparison) and aim to output a
clean sample $y$ distributed according to $\mathcal{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 $\mathcal{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 $\mathcal{D}$ and can be even exponential in the support of
$\mathcal{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 $\mathcal{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.
