On the joint entropy of $d$-wise-independent variables

Gavinsky, Dmitry, and Pudlák, Pavel. "On the joint entropy of $d$-wise-independent variables." Commentationes Mathematicae Universitatis Carolinae 57.3 (2016): 333-343. <http://eudml.org/doc/286806>.

@article{Gavinsky2016,
abstract = {How low can the joint entropy of $n$$d$-wise independent (for $d\ge 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$.},
author = {Gavinsky, Dmitry, Pudlák, Pavel},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {$d$-wise-independent variables; entropy; lower bound},
language = {eng},
number = {3},
pages = {333-343},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On the joint entropy of $d$-wise-independent variables},
url = {http://eudml.org/doc/286806},
volume = {57},
year = {2016},
}

TY - JOUR
AU - Gavinsky, Dmitry
AU - Pudlák, Pavel
TI - On the joint entropy of $d$-wise-independent variables
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2016
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 57
IS - 3
SP - 333
EP - 343
AB - How low can the joint entropy of $n$$d$-wise independent (for $d\ge 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$.
LA - eng
KW - $d$-wise-independent variables; entropy; lower bound
UR - http://eudml.org/doc/286806
ER -