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 and 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Applied Analysis, 2010, 9 (5) : 1463-1471. doi: 10.3934/cpaa.2010.9.1463
[11]

Hermes H. Ferreira, Artur O. Lopes, Silvia R. C. Lopes. Decision Theory and large deviations for dynamical hypotheses tests: The Neyman-Pearson Lemma, Min-Max and Bayesian tests. Journal of Dynamics and Games, 2022, 9 (2) : 123-150. doi: 10.3934/jdg.2021031
[12]

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
[13]

Huilian Jia, Lihe Wang, Fengping Yao, Shulin Zhou. Regularity theory in Orlicz spaces for the poisson and heat equations. Communications on Pure and 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 and Continuous Dynamical Systems, 2007, 18 (1) : 121-134. doi: 10.3934/dcds.2007.18.121
[15]

Shuhei Hayashi. Erratum and addendum to "A forward Ergodic Closing Lemma and the Entropy Conjecture for nonsingular endomorphisms away from tangencies" (Volume 40, Number 4, 2020, 2285-2313). Discrete and Continuous Dynamical Systems, 2022, 42 (5) : 2433-2437. doi: 10.3934/dcds.2021196
[16]

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

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
[18]

Tianyu Liao. The regularity lifting methods for nonnegative solutions of Lane-Emden system. Communications on Pure and Applied Analysis, 2021, 20 (4) : 1681-1698. doi: 10.3934/cpaa.2021036
[19]

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

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete and Continuous Dynamical Systems, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310

2021 Impact Factor: 1.015

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy