Entropy and expansion (Q2028943): Difference between revisions

The well-known Shearer inequality says that the sum of joint entropies of random variables can be estimated by the total joint entropy. The authors' aim in this paper is to give an another lower bound for the same sum in terms of the individual entropies when the variables are functions of independent random seeds. This inequality involves a constant characterizing the expansion properties of the system. The results obtained 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ás's entropy bounds in random regular graphs. The method yields inequalities for other measures of randomness, including covariance. As an application, the authors also give upper bounds for independent sets in both finite and infinite graphs. The first section of the paper contains the preliminaries, the notation and also the terminology. In Section 2, entropy inequalities for a finite system of random variables are presented and proved, while in the third section the authors deal with the infinite case under the unimodularity condition. In the fourth section, possible generalizations and further perspectives are given, while in the last section some applications are discussed. For the reader's convenience they also include an Appendix with some definitions and lemmas regarding entropy and conditional entropy.