The final form of Tao's inequality relating conditional expectation and conditional mutual information
Rudolf Ahlswede - Department of Mathematics, University of Bielefeld, POB 100131, D-33501 Bielefeld, Germany (email)
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
Keywords: Regularity lemma, Pinsker inequality, arithmetic progressions,
information theoretic methods for combinatorics and number theory.
Received: December 2006; Available Online: April 2007.
2015 Impact Factor.631