On the joint entropy of $d$-wise-independent variables
Gavinsky Dmitry, Pudlák Pavel · Commentationes Mathematicae Universitatis Carolinae · 2016
How low can the joint entropy of $n$ $d$-wise independent (for $d\geq 2$) discrete random variables be, subject to given constraints on the individual distributions (say, no value may be taken by a variable with probability greater than $p$, for $p< 1$)? This question has been posed and partially answered in a recent work of Babai [{Entropy versus pairwise independence} (preliminary version), {http://people.cs.uchicago.edu/~laci/papers/13augEntropy.pdf}, 2013]. In this paper we improve some of his bounds, prove new bounds in a wider range of parameters and show matching upper bounds in some special cases. In particular, we prove tight lower bounds for the min-entropy (as well as the entropy) of pairwise and three-wise independent balanced binary variables for infinitely many values of $n$.