Number of the records: 1
On the joint entropy of d-wise-independent variables
- 1.
SYSNO ASEP 0463333 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title On the joint entropy of d-wise-independent variables Author(s) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAISource Title Commentationes Mathematicae Universitatis Carolinae. - : Univerzita Karlova v Praze - ISSN 0010-2628
Roč. 57, č. 3 (2016), s. 333-343Number of pages 11 s. Language eng - English Country CZ - Czech Republic Keywords d-wise-independent variables ; entropy ; lower bound Subject RIV BA - General Mathematics OECD category Pure mathematics R&D Projects GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support MU-W - RVO:67985840 UT WOS 000410778900007 EID SCOPUS 85000869378 DOI 10.14712/1213-7243.2015.169 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2017
Number of the records: 1