Inequalities and tail bounds for elementary symmetric polynomial with applications

الأصل · EN

We study the extent of independence needed to approximate the product of bounded random variables in expectation, a natural question that has applications in pseudorandomness and min-wise independent hashing. For random variables whose absolute value is bounded by 1, we give an error bound of the form σΩ⁽ᵏ⁾ where k is the amount of independence and σ² is the total variance of the sum. Previously known bounds only applied in more restricted settings, and were quanitively weaker. We use this to give a simpler and more modular analysis of a construction of min-wise independent hash functions and pseudorandom generators for combinatorial rectangles due to Gopalan et al., which also slightly improves their seed-length. Our proof relies on a new analytic inequality for the elementary symmetric polynomials Sₖ(x) for x ∈ Rⁿ which we believe to be of independent interest. We show that if |Sₖ(x)|,|Sₖ₊₁(x)| are small relative to |Sₖ₋₁(x)| for some k>0 then |Sℓ(x)| is also small for all ℓ > k. From these, we derive tail bounds for the elementary symmetric polynomials when the inputs are only k-wise independent.