American Institute of Mathematical Sciences

Advanced
May  2007, 1(2): 239-242. doi: 10.3934/amc.2007.1.239

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

Rudolf Ahlswede 1,

1. 

Department of Mathematics, University of Bielefeld, POB 100131, D-33501 Bielefeld, Germany

Received  December 2006 Published  April 2007

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: arithmetic progressions, information theoretic methods for combinatorics and number theory., Regularity lemma, Pinsker inequality.
Mathematics Subject Classification: 05C35, 05D0.
Citation: Rudolf Ahlswede. The final form of Tao's inequality relating conditional expectation and conditional mutual information. Advances in Mathematics of Communications, 2007, 1 (2) : 239-242. doi: 10.3934/amc.2007.1.239
[1]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[2]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169
[3]

Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365
[4]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[5]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565
[6]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[7]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[8]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[9]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[10]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[11]

Philippe G. Lefloch, Cristinel Mardare, Sorin Mardare. Isometric immersions into the Minkowski spacetime for Lorentzian manifolds with limited regularity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 341-365. doi: 10.3934/dcds.2009.23.341
[12]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044
[13]

Hyeong-Ohk Bae, Hyoungsuk So, Yeonghun Youn. Interior regularity to the steady incompressible shear thinning fluids with non-Standard growth. Networks & Heterogeneous Media, 2018, 13 (3) : 479-491. doi: 10.3934/nhm.2018021
[14]

Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (68)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences