Geometric influences II: Correlation inequalities and noise sensitivity

Nathan Keller; Elchanan Mossel; Arnab Sen

Annales de l'I.H.P. Probabilités et statistiques (2014)

  • Volume: 50, Issue: 4, page 1121-1139
  • ISSN: 0246-0203

Abstract

top
In a recent paper, we presented a new definition of influences in product spaces of continuous distributions, and showed that analogues of the most fundamental results on discrete influences, such as the KKL theorem, hold for the new definition in Gaussian space. In this paper we prove Gaussian analogues of two of the central applications of influences: Talagrand’s lower bound on the correlation of increasing subsets of the discrete cube, and the Benjamini–Kalai–Schramm (BKS) noise sensitivity theorem. We then use the Gaussian results to obtain analogues of Talagrand’s bound for all discrete probability spaces and to reestablish analogues of the BKS theorem for biased two-point product spaces.

How to cite

top

Keller, Nathan, Mossel, Elchanan, and Sen, Arnab. "Geometric influences II: Correlation inequalities and noise sensitivity." Annales de l'I.H.P. Probabilités et statistiques 50.4 (2014): 1121-1139. <http://eudml.org/doc/271986>.

@article{Keller2014,
abstract = {In a recent paper, we presented a new definition of influences in product spaces of continuous distributions, and showed that analogues of the most fundamental results on discrete influences, such as the KKL theorem, hold for the new definition in Gaussian space. In this paper we prove Gaussian analogues of two of the central applications of influences: Talagrand’s lower bound on the correlation of increasing subsets of the discrete cube, and the Benjamini–Kalai–Schramm (BKS) noise sensitivity theorem. We then use the Gaussian results to obtain analogues of Talagrand’s bound for all discrete probability spaces and to reestablish analogues of the BKS theorem for biased two-point product spaces.},
author = {Keller, Nathan, Mossel, Elchanan, Sen, Arnab},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {influences; geometric influences; noise sensitivity; correlation between increasing sets; Talagrand's bound; gaussian measure; isoperimetric inequality; Gaussian measure},
language = {eng},
number = {4},
pages = {1121-1139},
publisher = {Gauthier-Villars},
title = {Geometric influences II: Correlation inequalities and noise sensitivity},
url = {http://eudml.org/doc/271986},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Keller, Nathan
AU - Mossel, Elchanan
AU - Sen, Arnab
TI - Geometric influences II: Correlation inequalities and noise sensitivity
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2014
PB - Gauthier-Villars
VL - 50
IS - 4
SP - 1121
EP - 1139
AB - In a recent paper, we presented a new definition of influences in product spaces of continuous distributions, and showed that analogues of the most fundamental results on discrete influences, such as the KKL theorem, hold for the new definition in Gaussian space. In this paper we prove Gaussian analogues of two of the central applications of influences: Talagrand’s lower bound on the correlation of increasing subsets of the discrete cube, and the Benjamini–Kalai–Schramm (BKS) noise sensitivity theorem. We then use the Gaussian results to obtain analogues of Talagrand’s bound for all discrete probability spaces and to reestablish analogues of the BKS theorem for biased two-point product spaces.
LA - eng
KW - influences; geometric influences; noise sensitivity; correlation between increasing sets; Talagrand's bound; gaussian measure; isoperimetric inequality; Gaussian measure
UR - http://eudml.org/doc/271986
ER -

References

top
  1. [1] D. Ahlberg, E. I. Broman, S. Griffith and R. Morris. Noise sensitivity in continuum percolation. Israel J. Math. To appear, 2014. Available at http://arxiv.org/abs/1108.0310. Zbl1305.60100MR3265306
  2. [2] W. Beckner. Inequalities in Fourier analysis. Ann. Math. (2) 102 (1975) 159–182. Zbl0338.42017MR385456
  3. [3] I. Benjamini, G. Kalai and O. Schramm. Noise sensitivity of boolean functions and applications to percolation. Publ. Math. Inst. Hautes Études Sci.90 (1999) 5–43. Zbl0986.60002MR1813223
  4. [4] A. Bonami. Etude des coefficients Fourier des fonctiones de L p ( G ) . Ann. Inst. Fourier20 (1970) 335–402. Zbl0195.42501MR283496
  5. [5] C. Borell. Positivity improving operators and hypercontractivity. Math. Z. 180 (2) (1982) 225–234. Zbl0472.47015MR661699
  6. [6] C. Borell. Geometric bounds on the Ornstein–Uhlenbeck velocity process. Probab. Theory Related Fields 70 (1) (1985) 1–13. Zbl0537.60084MR795785
  7. [7] J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson and N. Linial. The influence of variables in product spaces. Israel J. Math.77 (1992) 55–64. Zbl0771.60002MR1194785
  8. [8] S. Chatterjee. Chaos, concentration, and multiple valleys, 2008. Available at http://arxiv.org/abs/0810.4221. 
  9. [9] D. Cordero-Erausquin and M. Ledoux. Hypercontractive measures, Talagrand’s inequality, and influences. Preprint, 2011. Available at http://arxiv.org/abs/1105.4533. Zbl1280.60018
  10. [10] C. M. Fortuin, P. W. Kasteleyn and J. Ginibre. Correlation inequalities on some partially ordered sets. Comm. Math. Phys.22 (1971) 89–103. Zbl0346.06011MR309498
  11. [11] P. Frankl. The shifting technique in extremal set theory. In Surveys in Combinatorics 81–110. C. W. Whitehead (Ed). Cambridge Univ. Press, Cambridge, 1987. Zbl0633.05038MR905277
  12. [12] G. R. Grimmett and B. Graham. Influence and sharp-threshold theorems for monotonic measures. Ann. Probab.34 (2006) 1726–1745. Zbl1115.60099MR2271479
  13. [13] T. E. Harris. A lower bound for the critical probability in a certain percolation process. Math. Proc. Cambridge Philos. Soc.56 (1960) 13–20. Zbl0122.36403MR115221
  14. [14] H. Hatami. Decision trees and influence of variables over product probability spaces. Combin. Probab. Comput.18 (2009) 357–369. Zbl1193.60007MR2501432
  15. [15] J. Kahn, G. Kalai and N. Linial. The influence of variables on boolean functions. In Proc. 29th Ann. Symp. on Foundations of Comp. Sci. 68–80. Computer Society Press, 1988. 
  16. [16] G. Kalai and M. Safra. Threshold phenomena and influence. In Computational Complexity and Statistical Physics 25–60. A. G. Percus, G. Istrate and C. Moore (Eds). Oxford Univ. Press, New York, 2006. Zbl1156.82317
  17. [17] N. Keller. Influences of variables on boolean functions. Ph.D. thesis, Hebrew Univ. Jerusalem, 2009. 
  18. [18] N. Keller. On the influences of variables on boolean functions in product spaces. Combin. Probab. Comput. 20 (1) (2011) 83–102. Zbl1204.94120MR2745679
  19. [19] N. Keller. A simple reduction from the biased measure on the discrete cube to the uniform measure. European J. Combin. 33 1943–1957. Available at http://arxiv.org/abs/1001.1167. Zbl1248.28005MR2950492
  20. [20] N. Keller and G. Kindler. A quantitative relation between influences and noise sensitivity. Combinatorica 33 45–71. Available at http://arxiv.org/abs/1003.1839. Zbl1299.05308MR3070086
  21. [21] N. Keller, E. Mossel and A. Sen. Geometric influences. Ann. Probab. 40 (3) (2012) 1135–1166. Zbl1255.60015MR2962089
  22. [22] G. Kindler and R. O’Donnell. Gaussian noise sensitivity and Fourier tails. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity 137–147. IEEE Computer Society, Washington, DC, 2012. Available at http://www.cs.cmu.edu/~odonnell/papers/gaussian-noise-sensitivity.pdf. MR3026322
  23. [23] D. J. Kleitman. Families of non-disjoint subsets. J. Combin. Theory1 (1966) 153–155. Zbl0141.00801MR193020
  24. [24] M. Ledoux. The geometry of Markov diffusion generators. Ann. Fac. Sci. Toulouse Math. (6) 9 (2) (2000) 305–366. Zbl0980.60097MR1813804
  25. [25] E. Mossel, R. O’Donnell and K. Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Ann. Math. (2) 171 (1) (2010) 295–341. Zbl1201.60031MR2630040
  26. [26] E. Mossel, R. O’Donnell, O. Regev, J. E. Steif and B. Sudakov. Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami–Beckner inequality. Israel J. Math.154 (2006) 299–336. Zbl1140.60007MR2254545
  27. [27] R. O’Donnell. Some topics in analysis of boolean functions. In Proceedings of the 40th Annual ACM Sympsium on the Theory of Computing 569–578. ACM, New York, 2008. Zbl1231.94096MR2582688
  28. [28] M. Talagrand. On Russo’s approximate zero–one law. Ann. Probab.22 (1994) 1576–1587. Zbl0819.28002
  29. [29] M. Talagrand. How much are increasing sets positively correlated? Combinatorica 16 (2) (1996) 243–258. Zbl0861.05008MR1401897
  30. [30] P. Wolff. Hypercontractivity of simple random variables. Studia Math. 180 (3) (2007) 219–236. Zbl1133.60011MR2314078

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.