Advances in Mathematics of Communications (AMC)

The final form of Tao's inequality relating conditional expectation and conditional mutual information

Pages: 239 - 242, Volume 1, Issue 2, May 2007      doi:10.3934/amc.2007.1.239

       Abstract        Full Text (87.4K)       Related Articles

Rudolf Ahlswede - Department of Mathematics, University of Bielefeld, POB 100131, D-33501 Bielefeld, Germany (email)

Abstract: Recently Terence Tao approached Szemerédi's Regularity Lemma from the perspectives of Probability Theory and of Information Theory instead of Graph Theory and found a stronger variant of this lemma, which involves a new parameter. To pass from an entropy formulation to an expectation formulation he found the following: Let $Y$ , and $X,X'$ be discrete random variables taking values in $mathcal Y$ and $mathcal X$, respectively, where $mathcal Y \subset$ [ −1, 1 ], and with $X' = f(X)$ for a (deterministic) function $f$. Then we have
     $ \E(|\E(Y|X')-\E(Y|X)|)\leq2I(X\wedge Y|X')^{\frac12}.$
We show that the constant $2$ can be improved to $(2 \l n2)^{\frac{1}{2}}$ and that this is the best possible constant.

Keywords:  Regularity lemma, Pinsker inequality, arithmetic progressions, information theoretic methods for combinatorics and number theory.
Mathematics Subject Classification:  05C35, 05D05.

Received: December 2006;      Available Online: April 2007.