| Title:
|
On the joint entropy of $d$-wise-independent variables (English) |
| Author:
|
Gavinsky, Dmitry |
| Author:
|
Pudlák, Pavel |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
57 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
333-343 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
$d$-wise-independent variables |
| Keyword:
|
entropy |
| Keyword:
|
lower bound |
| MSC:
|
60C05 |
| idZBL:
|
Zbl 06674884 |
| idMR:
|
MR3554514 |
| DOI:
|
10.14712/1213-7243.2015.169 |
| . |
| Date available:
|
2016-09-22T15:24:59Z |
| Last updated:
|
2018-10-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145838 |
| . |
| Reference:
|
[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. Zbl 0631.68063, MR 0866792, 10.1016/0196-6774(86)90019-2 |
| Reference:
|
[AS08] Alon N., Spencer J.: The Probabilistic Method.John Wiley, Hoboken, NJ, 2008. Zbl 1333.05001, MR 2437651 |
| Reference:
|
[Bab13] Babai L.: Entropy versus pairwise independence.(preliminary version), http://people.cs.uchicago.edu/ laci/papers/13augEntropy.pdf, 2013. |
| Reference:
|
[Can10] Cantelli F.P.: Intorno ad un teorema fondamentale della teoria del rischio.Bollettino dell' Associazione degli Attuari Italiani 24 (1910), 1–23. |
| Reference:
|
[Lan65] Lancaster H.O.: Pairwise statistical independence.Ann. Math. Statist. 36 (1965), no. 4, 1313–1317. Zbl 0131.18105, MR 0176507, 10.1214/aoms/1177700007 |
| Reference:
|
[LW06] Luby M., Wigderson A.: Pairwise independence and derandomization.Found. Trends Theor. Comput. Sci. 1 (2005), no. 4, 237–301. Zbl 1140.68402, MR 2379508, 10.1561/0400000009 |
| Reference:
|
[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 |
| . |
