On the Entropy of Locally-Independent Bernoulli Trials.
Dmitry Gavinsky, Pavel Pudlák · arXiv (Cornell University) · 2015
How low can be the joint entropy of $n$ locally-independent (i.e., $d$-wise independent for $d\ge2$) Bernoulli variables? This question has been posed and partially answered in a recent work of Babai. 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 for pair-wise and three-wise balanced Bernoulli trials for infinitely many values of $n$.