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

Abstract

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