Csóka, Endre and Harangi, Viktor and Virág, Bálint (2020) Entropy and expansion. ANNALES DE L'INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 56 (4). pp. 2428-2444. ISSN 0246-0203
|
Text
234234.pdf Available under License Creative Commons Attribution. Download (286kB) | Preview |
Abstract
Shearer’s inequality bounds the sum of joint entropies of random variables in terms of the total joint entropy. We give another lower bound for the same sum in terms of the individual entropies when the variables are functions of independent random seeds. The inequality involves a constant characterizing the expansion properties of the system. Our results generalize to entropy inequalities used in recent work in invariant settings, including the edge-vertex inequality for factor-of-IID processes, Bowen’s entropy inequalities, and Bollob´as’s entropy bounds in random regular graphs. The proof method yields inequalities for other measures of randomness, including covariance. As an application, we give upper bounds for independent sets in both finite and infinite graphs.
Item Type: | Article |
---|---|
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 26 Feb 2021 09:42 |
Last Modified: | 25 Apr 2023 09:23 |
URI: | http://real.mtak.hu/id/eprint/121707 |
Actions (login required)
![]() |
Edit Item |