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]

Tanja Eisner, Rainer Nagel. Arithmetic progressions -- an operator theoretic view. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 657-667. doi: 10.3934/dcdss.2013.6.657
[2]

Gregory S. Chirikjian. Information-theoretic inequalities on unimodular Lie groups. Journal of Geometric Mechanics, 2010, 2 (2) : 119-158. doi: 10.3934/jgm.2010.2.119
[3]

Wenxiong Chen, Congming Li, Shijie Qi. A Hopf lemma and regularity for fractional $ p $-Laplacians. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3235-3252. doi: 10.3934/dcds.2020034
[4]

Tero Laihonen. Information retrieval and the average number of input clues. Advances in Mathematics of Communications, 2017, 11 (1) : 203-223. doi: 10.3934/amc.2017013
[5]

Michał Jóźwikowski, Mikołaj Rotkiewicz. Bundle-theoretic methods for higher-order variational calculus. Journal of Geometric Mechanics, 2014, 6 (1) : 99-120. doi: 10.3934/jgm.2014.6.99
[6]

Lingyu Jin, Yan Li. A Hopf's lemma and the boundary regularity for the fractional p-Laplacian. Discrete & Continuous Dynamical Systems - A, 2019, 39 (3) : 1477-1495. doi: 10.3934/dcds.2019063
[7]

Michael Hochman. Lectures on dynamics, fractal geometry, and metric number theory. Journal of Modern Dynamics, 2014, 8 (3&4) : 437-497. doi: 10.3934/jmd.2014.8.437
[8]

E. Muñoz Garcia, R. Pérez-Marco. Diophantine conditions in small divisors and transcendental number theory. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1401-1409. doi: 10.3934/dcds.2003.9.1401
[9]

Daniela De Silva, Ovidiu Savin. A note on higher regularity boundary Harnack inequality. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 6155-6163. doi: 10.3934/dcds.2015.35.6155
[10]

Philipp Reiter. Regularity theory for the Möbius energy. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1463-1471. doi: 10.3934/cpaa.2010.9.1463
[11]

Yang Yu. Introduction: Special issue on computational intelligence methods for big data and information analytics. Big Data & Information Analytics, 2017, 2 (1) : i-ii. doi: 10.3934/bdia.201701i
[12]

Weifu Sun, Xu Yang, Yijun Chen. Elimination algorithm of complex network redundant data stream based on information theory. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020256
[13]

Huilian Jia, Lihe Wang, Fengping Yao, Shulin Zhou. Regularity theory in Orlicz spaces for the poisson and heat equations. Communications on Pure & Applied Analysis, 2008, 7 (2) : 407-416. doi: 10.3934/cpaa.2008.7.407
[14]

Sun-Sig Byun, Hongbin Chen, Mijoung Kim, Lihe Wang. Lp regularity theory for linear elliptic systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (1) : 121-134. doi: 10.3934/dcds.2007.18.121
[15]

Weizhu Bao, Yongyong Cai. Mathematical theory and numerical methods for Bose-Einstein condensation. Kinetic & Related Models, 2013, 6 (1) : 1-135. doi: 10.3934/krm.2013.6.1
[16]

Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015
[17]

Chun Liu. Dynamic theory for incompressible Smectic-A liquid crystals: Existence and regularity. Discrete & Continuous Dynamical Systems - A, 2000, 6 (3) : 591-608. doi: 10.3934/dcds.2000.6.591
[18]

Jerrold E. Marsden, Alexey Tret'yakov. Factor analysis of nonlinear mappings: p-regularity theory. Communications on Pure & Applied Analysis, 2003, 2 (4) : 425-445. doi: 10.3934/cpaa.2003.2.425
[19]

Jungho Park. Dynamic bifurcation theory of Rayleigh-Bénard convection with infinite Prandtl number. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 591-604. doi: 10.3934/dcdsb.2006.6.591
[20]

Pedro A. S. Salomão. The Thurston operator for semi-finite combinatorics. Discrete & Continuous Dynamical Systems - A, 2006, 16 (4) : 883-896. doi: 10.3934/dcds.2006.16.883

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (29)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences