Mutual Information, Information-Theoretic Thresholds and the Condensation Phenomenon at Positive Temperature
From MaRDI portal
Publication:6405735
arXiv2207.11002MaRDI QIDQ6405735FDOQ6405735
Authors: Konstantinos Panagiotou, Matija Pasch 
Publication date: 22 July 2022
Abstract: There is a vast body of recent literature on the reliability of communication through noisy channels, the recovery of community structures in the stochastic block model, the limiting behavior of the free entropy in spin glasses and the solution space structure of constraint satisfaction problems. At first glance, these topics ranging across several disciplines might seem unrelated. However, taking a closer look, structural similarities can be easily identified. Factor graphs exploit these similarities to model the aforementioned objects and concepts in a unified manner. In this contribution we discuss the asymptotic average case behavior of several quantities, where the average is taken over sparse ErdH{o}s-R'enyi type (hyper-) graphs with positive weights, under certain assumptions. For one, we establish the limit of the mutual information, which is used in coding theory to measure the reliability of communication. We also determine the limit of the relative entropy, which can be used to decide if weak recovery is possible in the stochastic block model. Further, we prove the conjectured limit of the quenched free entropy over the planted ensemble, which we use to obtain the preceding limits. Finally, we describe the asymptotic behavior of the quenched free entropy (over the null model) in terms of the limiting relative entropy.
Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
This page was built for publication: Mutual Information, Information-Theoretic Thresholds and the Condensation Phenomenon at Positive Temperature
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405735)
