Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T20:57:01.907Z Has data issue: false hasContentIssue false

Influence in product spaces

Published online by Cambridge University Press:  25 July 2016

Geoffrey R. Grimmett*
Affiliation:
University of Cambridge
Svante Janson*
Affiliation:
Uppsala University
James R. Norris*
Affiliation:
University of Cambridge
*
Statistical Laboratory, Centre for Mathematical Sciences, Cambridge University, Wilberforce Road, Cambridge CB3 0WB, UK. Email address: [email protected]
Department of Mathematics, Uppsala University, Box 480, 751 06 Uppsala, Sweden. Email address: [email protected]
Statistical Laboratory, Centre for Mathematical Sciences, Cambridge University, Wilberforce Road, Cambridge CB3 0WB, UK. Email address: [email protected]

Abstract

The theory of influence and sharp threshold is a key tool in probability and probabilistic combinatorics, with numerous applications. One significant aspect of the theory is directed at identifying the level of generality of the product probability space that accommodates the event under study. We derive the influence inequality for a completely general product space, by establishing a relationship to the Lebesgue cube studied by Bourgain, Kahn, Kalai, Katznelson and Linial (BKKKL) in 1992. This resolves one of the assertions of BKKKL. Our conclusion is valid also in the setting of the generalized influences of Keller.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Barlow, R. E. and Proschan, F. (1965).Mathematical Theory of Reliability.John Wiley,New York.Google Scholar
[2] Ben-Or, M. and Linial, . (1990).Collective coin flipping. In Advances in Computing Research: a Research Annual (Randomness and Computation, 1989), Vol. 5, ed. S. Micali,JAI Press,Greenwich, CT, pp. 91115.Google Scholar
[3] Bourgain, J.,Kahn, J.,Kalai, G.,Katznelson, Y. and Linial, N. (1992).The influence of variables in product spaces.Israel J. Math. 77,5564.CrossRefGoogle Scholar
[4] Duminil-Copin, H. and Tassion, V. (2015).A new proof of the sharpness of the phase transition for Bernoulli percolation on ℤ d . Preprint. Available at http://arxiv.org/abs/1502.03051v1.Google Scholar
[5] Garban, C. and Steif, J. E. (2015).Noise Sensitivity of Boolean Functions and Percolation.Cambridge University Press.Google Scholar
[6] Graham, B. T. and Grimmett, G. R. (2006).Influence and sharp-threshold theorems for monotonic measures.Ann. Prob. 34,17261745.CrossRefGoogle Scholar
[7] Graham, B. T. and Grimmett, G. R. (2011).Sharp thresholds for the random-cluster and Ising models.Ann. Appl. Prob. 21,240265.CrossRefGoogle Scholar
[8] Grimmett, G. R. (2010).Probability on Graphs: Random Processes on Graphs and Lattices.Cambridge University Press.CrossRefGoogle Scholar
[9] Halmos, P. (1950).Measure Theory(Grad. Texts in Math. 18).Springer,New York.CrossRefGoogle Scholar
[10] Hatami, H. (2009).Decision trees and influences of variables over product probability spaces.Combinatorics Prob. Comput. 18,357369.CrossRefGoogle Scholar
[11] Janson, S. (2013).Graphons, Cut Norm and Distance, Couplings and Rearrangements (New York J. Math, Monogr. 4). Available at http://nyjm.albany.edu/m/.Google Scholar
[12] Kahn, J.,Kalai, G. and Linial, N. (1988).The influence of variables on Boolean functions. In 29th Annual IEEE Symposium on Foundations of Computer Science,IEEE Computer Society Press,Washington, DC, pp. 6880.Google Scholar
[13] Kalai, G. and Safra, S. (2006).Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. In Computational Complexity and Statistical Physics, eds A. G. Percus, G. Istrate and C. Moore,Oxford University Press,New York, pp. 2560.Google Scholar
[15] Keller, N. (2011).On the influences of variables on Boolean functions in product spaces.Combinatorics Prob. Comput. 20,83102.CrossRefGoogle Scholar
[16] Kesten, H. (1980).The critical probability of bond percolation on the square lattice equals 1/2.Commun. Math. Phys. 74,4159.CrossRefGoogle Scholar
[17] Margulis, G. A. (1974).Probabilistic characteristics of graphs with large connectivity.Probl. Inf. Transm. 10,174179.Google Scholar
[18] Petersen, K. E. (1989).Ergodic Theory (Camb. Stud. Adv. Math. 2).Cambridge University Press.Google Scholar
[19] Rudolph, D. J. (1990).Fundamentals of Measurable Dynamics: Ergodic Theory on Lebesgue Spaces.Clarendon Press,Oxford.Google Scholar
[20] Russo, L. (1978).A note on percolation.Z. Wahrscheinlichkeitsth. 43,3948.CrossRefGoogle Scholar
[21] Talagrand, M. (1994).On Russo's approximate zero-one law.Ann. Prob. 22,15761587.CrossRefGoogle Scholar