On the joint entropy of d-wise-independent variables
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00463333" target="_blank" >RIV/67985840:_____/16:00463333 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.14712/1213-7243.2015.169" target="_blank" >http://dx.doi.org/10.14712/1213-7243.2015.169</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.14712/1213-7243.2015.169" target="_blank" >10.14712/1213-7243.2015.169</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the joint entropy of d-wise-independent variables
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On the joint entropy of d-wise-independent variables
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2016
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Commentationes Mathematicae Universitatis Carolinae
ISSN
0010-2628
e-ISSN
—
Svazek periodika
57
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
CZ - Česká republika
Počet stran výsledku
11
Strana od-do
333-343
Kód UT WoS článku
000410778900007
EID výsledku v databázi Scopus
2-s2.0-85000869378