0463333 - MÚ 2017 RIV CZ eng J - Journal Article
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. E-ISSN 1213-7243
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : d-wise-independent variables * entropy * lower bound
OECD category: Pure mathematics
Result website:
http://hdl.handle.net/10338.dmlcz/145838
DOI: https://doi.org/10.14712/1213-7243.2015.169

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.

Permanent Link: http://hdl.handle.net/11104/0262546