Entropy and expansion

DOI10.1214/19-AIHP1044MaRDI QIDQ2028943zbMATH OpenOpenAlexFDO

Authors Endre Csóka, Viktor Harangi, Balint Virag

Publication date 3 June 2021

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.09560, https://projecteuclid.org/euclid.aihp/1603267226

zbMATH Keywords

Cheeger constantentropy inequalityexpansionfactor-of-IIDgraph isoperimetryindependent setlocal algorithm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Group actions on combinatorial structures (05E18) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Measures of information, entropy (94A17)

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.

Review text

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.

Recommendations

• Entropy inequalities for factors of IID
• Some bounds on entropy measures in information theory
• Projections, entropy and sumsets
• scientific article; zbMATH DE number 1983989
• Independence Inequality of Entropies

Cites work

• A measure-conjugacy invariant for free group actions
• Cubic graphs with small independence ratio
• Entropy inequalities for factors of IID
• Explicit isoperimetric constants and phase transitions in the random-cluster model
• Factor of iid percolation on trees
• Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
• scientific article; zbMATH DE number 4049676 (Why is no real title available?)
• Independence ratio and random eigenvectors in transitive graphs
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Isoperimetric Constants of (d,f)-Regular Planar Graphs
• Limits of local algorithms over sparse random graphs
• Local algorithms for independent sets are half-optimal
• Mutual information decay for factors of i.i.d.
• On large‐girth regular graphs and random processes on trees
• On the almost eigenvectors of random regular graphs
• On the independence and chromatic numbers of random regular graphs
• Perfect matchings as IID factors on non-amenable groups
• Processes on unimodular random networks
• Properties of regular graphs with large girth via local algorithms
• Replica bounds by combinatorial interpolation for diluted spin systems
• Some intersection theorems for ordered sets and graphs
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• The ergodic theory of free group actions: entropy and the f-invariant
• The Independence Ratio of Regular Graphs

Cited in

(9)

• Typicality and entropy of processes on infinite trees
• On mixing of Markov chains: coupling, spectral independence, and entropy factorization
• Distributed algorithms for fractional coloring
• Block factorization of the relative entropy via spatial mixing
• Entropy inequalities for factors of IID
• Shearer's inequality and infimum rule for Shannon entropy and topological entropy
• Entropy and volume growth
• Nonlinear recombinations and generalized random transpositions
• Sparse reconstruction in spin systems. II: Ising and other factor of IID measures

This page was built for publication: Entropy and expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028943)