  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.
