On the joint entropy of d-wise-independent variables

0463333 - MÚ 2017 RIV CZ eng J - Článek v odborném periodiku
Gavinsky, Dmitry - Pudlák, Pavel
On the joint entropy of d-wise-independent variables.
Commentationes Mathematicae Universitatis Carolinae. Roč. 57, č. 3 (2016), s. 333-343. ISSN 0010-2628
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: d-wise-independent variables * entropy * lower bound
Obor OECD: Pure mathematics
http://hdl.handle.net/10338.dmlcz/145838

How low can the joint entropy of n d-wise independent (for d 2)discrete random variables be, subject to given constraints on the individual dis-tributions (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.
Trvalý link: http://hdl.handle.net/11104/0262546