Abstract
Strongly Rayleigh distributions are a class of negatively dependent distributions of binary-valued random variables (Borcea-Branden-Liggett 2009). A probability distribution over {0,1}^n is Strongly Rayleigh if its associated generating polynomial is real stable. If the distribution has exactly k entries that are 1 in every outcome, it is said to be k-homogeneous. We prove a matrix Chernoff bound that shows concentration of sums of PSD matrices scaled by coefficients that have a Strongly Rayleigh, k-homogenous distribution.
Because random spanning trees are k-homogenous Strongly Rayleigh, we can use our matrix Chernoff bound to show new results for approximation of graph Laplacians by sampling sums of random spanning trees. We show that O(epsilon^-2 log^2 n) spanning trees give a (1+eps)-spectral sparsifier of a graph Laplacian with high probability, and show from a simple lower bound that at least epsilon^-2 log n spanning trees are necessary.