Strongly Rayleigh distributions are a class of negatively dependent distributions. They enjoy many useful properties and they contain most of the known examples of negatively dependent distributions. They have also found numerous applications in various contexts.

Informally speaking, one expects that the repulsive force in a negatively dependent distribution cannot be strong everywhere. In accordance with this intuition, we will show that for every strongly Rayleigh measure, it is possible to find many points (of the order of the size of the underlying space) that are “almost independent”.

The proof hinges on an extension of the paving conjecture to real stable polynomials. The connection between this result and strongly Rayleigh measures is made through the notion of kernel polynomial. The roots of this polynomial play an important role; in particular, we will use them to bound the entropy.


Video Recording