Geodesic
On the joint entropy of $d$-wise-independent variables
Commentationes Mathematicae Universitatis Carolinae, Tome 57 (2016) no. 3, pp. 333-343.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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$.
DOI : 10.14712/1213-7243.2015.169
Classification : 60C05
Keywords: $d$-wise-independent variables; entropy; lower bound 
@article{10_14712_1213_7243_2015_169,
     author = {Gavinsky, Dmitry and Pudl\'ak, Pavel},
     title = {On the joint entropy of $d$-wise-independent variables},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {333--343},
     publisher = {mathdoc},
     volume = {57},
     number = {3},
     year = {2016},
     doi = {10.14712/1213-7243.2015.169},
     mrnumber = {3554514},
     zbl = {06674884},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.169/}
}
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
SP  - 333
EP  - 343
VL  - 57
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.169/
DO  - 10.14712/1213-7243.2015.169
LA  - en
ID  - 10_14712_1213_7243_2015_169
ER  - 
%0 Journal Article
%A Gavinsky, Dmitry
%A Pudlák, Pavel
%T On the joint entropy of $d$-wise-independent variables
%J Commentationes Mathematicae Universitatis Carolinae
%D 2016
%P 333-343
%V 57
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.169/
%R 10.14712/1213-7243.2015.169
%G en
%F 10_14712_1213_7243_2015_169
Gavinsky, Dmitry; Pudlák, Pavel. On the joint entropy of $d$-wise-independent variables. Commentationes Mathematicae Universitatis Carolinae, Tome 57 (2016) no. 3, pp. 333-343. doi : 10.14712/1213-7243.2015.169. http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.169/

Cité par Sources :