Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
$d$-wise-independent variables; entropy; lower bound
$d$-wise-independent variables; entropy; lower bound
Summary:
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$.
References:
[ABI86] Alon N., Babai L., Itai A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7 (1986), no. 4, 567–583. DOI 10.1016/0196-6774(86)90019-2 | MR 0866792 | Zbl 0631.68063
[AS08] Alon N., Spencer J.: The Probabilistic Method. John Wiley, Hoboken, NJ, 2008. MR 2437651 | Zbl 1333.05001
[Bab13] Babai L.: Entropy versus pairwise independence. (preliminary version), http://people.cs.uchicago.edu/ laci/papers/13augEntropy.pdf, 2013.
[Can10] Cantelli F.P.: Intorno ad un teorema fondamentale della teoria del rischio. Bollettino dell' Associazione degli Attuari Italiani 24 (1910), 1–23.
[Lan65] Lancaster H.O.: Pairwise statistical independence. Ann. Math. Statist. 36 (1965), no. 4, 1313–1317. DOI 10.1214/aoms/1177700007 | MR 0176507 | Zbl 0131.18105
[LW06] Luby M., Wigderson A.: Pairwise independence and derandomization. Found. Trends Theor. Comput. Sci. 1 (2005), no. 4, 237–301. DOI 10.1561/0400000009 | MR 2379508 | Zbl 1140.68402
[MS83] MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Zbl 0657.94010
Search
Partner of
