solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看11619次
Entropy and expansion. (arXiv:1811.09560v1 [math.PR])
来源于:arXiv
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. 查看全文>>