Abstract
We show that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem in particular describes the structure of monotone set properties that do not exhibit sharp thresholds.
Our result generalizes the core of Friedgut’s seminal work on properties of random graphs to the setting of arbitrary Boolean functions on general product probability spaces and improves the result of Bourgain in his appendix to Friedgut’s paper.
-
[AlonSpencer1992]
N. Alon and J. H. Spencer, The Probabilistic Method, Second ed., New York: Wiley-Interscience [John Wiley & Sons], 2000.@book {AlonSpencer1992, MRKEY = {1885388},
AUTHOR = {Alon, Noga and Spencer, Joel H.},
TITLE = {The Probabilistic Method},
SERIES = {Wiley-Intersci. Ser. Discrete Math. Optim.},
EDITION = {Second},
PUBLISHER = {Wiley-Interscience [John Wiley \& Sons]},
ADDRESS = {New York},
YEAR = {2000},
PAGES = {xviii+301},
ISBN = {0-471-37046-0},
MRCLASS = {60-02 (05C80 60C05 60F99 60G42)},
MRNUMBER = {1885388},
MRREVIEWER = {Bert Fristedt},
DOI = {10.1002/0471722154},
ZBLNUMBER = {0996.05001},
} -
[Bourgain99] J. Bourgain, "Appendix to “Sharp thresholds of graph properties, and the $k$-sat problem”," J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1046-1053, 1999.
@article {Bourgain99, MRKEY = {1678031},
AUTHOR = {Bourgain, J.},
TITLE = {Appendix to ``{S}harp thresholds of graph properties, and the {$k$}-sat problem''},
JOURNAL = {J. Amer. Math. Soc.},
FJOURNAL = {Journal of the American Mathematical Society},
VOLUME = {12},
YEAR = {1999},
NUMBER = {4},
PAGES = {1046--1053},
ISSN = {0894-0347},
MRCLASS = {05C80 (42C10)},
MRNUMBER = {1678031},
MRREVIEWER = {Mark R. Jerrum},
DOI = {10.1090/S0894-0347-99-00305-7},
ZBLNUMBER = {0932.05084},
} -
[Bourgain2000] J. Bourgain, "Harmonic analysis and combinatorics: how much may they contribute to each other?," in Mathematics: Frontiers and Perspectives, Providence, RI: Amer. Math. Soc., 2000, pp. 13-32.
@incollection {Bourgain2000, MRKEY = {1754764},
AUTHOR = {Bourgain, J.},
TITLE = {Harmonic analysis and combinatorics: how much may they contribute to each other?},
BOOKTITLE = {Mathematics: Frontiers and Perspectives},
PAGES = {13--32},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
YEAR = {2000},
MRCLASS = {42B20 (05D10 28A78 30B50)},
MRNUMBER = {1754764},
ZBLNUMBER = {0963.42001},
} -
[BKKKL] J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson, and N. Linial, "The influence of variables in product spaces," Israel J. Math., vol. 77$ $, iss. 1-2, p. $ $55-64, 1992.
@article {BKKKL,
author = {Bourgain, J. and Kahn, J. and Kalai, G. and Katznelson, Y. and Linial, N.},
TITLE = {The influence of variables in product spaces},
JOURNAL = {Israel J. Math.},
FJOURNAL = {Israel Journal of Mathematics},
VOLUME = {77$ $},
YEAR = {1992},
NUMBER = {1-2},
PAGES = {$ $55--64},
ISSN = {0021-2172},
CODEN = {ISJMAP},
MRCLASS = {05D05 (05A20 28A35 60B15 60F15)},
MRNUMBER = {1194785},
ZBLNUMBER = {0771.60002},
DOI = {10.1007/BF02808010},
MRREVIEWER = {Wolfgang Lusky},
} -
[BK] J. Bourgain and G. Kalai, "Influences of variables and threshold intervals under group symmetries," Geom. Funct. Anal., vol. 7, iss. 3, pp. 438-461, 1997.
@article {BK, MRKEY = {1466334},
AUTHOR = {Bourgain, J. and Kalai, G.},
TITLE = {Influences of variables and threshold intervals under group symmetries},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {7},
YEAR = {1997},
NUMBER = {3},
PAGES = {438--461},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {20B35 (05C80 20B15)},
MRNUMBER = {1466334},
MRREVIEWER = {Wolfgang Lusky},
DOI = {10.1007/s000390050015},
ZBLNUMBER = {0982.20004},
} -
[MR615434] B. Efron and C. Stein, "The jackknife estimate of variance," Ann. Statist., vol. 9, iss. 3, pp. 586-596, 1981.
@article {MR615434, MRKEY = {0615434},
AUTHOR = {Efron, B. and Stein, C.},
TITLE = {The jackknife estimate of variance},
JOURNAL = {Ann. Statist.},
FJOURNAL = {The Annals of Statistics},
VOLUME = {9},
YEAR = {1981},
NUMBER = {3},
PAGES = {586--596},
ISSN = {0090-5364},
CODEN = {ASTSC7},
MRCLASS = {62G05},
MRNUMBER = {0615434},
MRREVIEWER = {Vishnu Dayal Jha},
DOI = {10.1214/aos/1176345462},
ZBLNUMBER = {0481.62035},
} -
[MR1645642] E. Friedgut, "Boolean functions with low average sensitivity depend on few coordinates," Combinatorica, vol. 18, iss. 1, pp. 27-35, 1998.
@article {MR1645642, MRKEY = {1645642},
AUTHOR = {Friedgut, Ehud},
TITLE = {Boolean functions with low average sensitivity depend on few coordinates},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
VOLUME = {18},
YEAR = {1998},
NUMBER = {1},
PAGES = {27--35},
ISSN = {0209-9683},
MRCLASS = {28A99 (05A16 05C80 28A60)},
MRNUMBER = {1645642},
DOI = {10.1007/PL00009809},
ZBLNUMBER = {0909.06008},
} -
[MR1678031] E. Friedgut, "Sharp thresholds of graph properties, and the $k$-sat problem," J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999.
@article {MR1678031, MRKEY = {1678031},
AUTHOR = {Friedgut, Ehud},
TITLE = {Sharp thresholds of graph properties, and the {$k$}-sat problem},
JOURNAL = {J. Amer. Math. Soc.},
FJOURNAL = {Journal of the American Mathematical Society},
VOLUME = {12},
YEAR = {1999},
NUMBER = {4},
PAGES = {1017--1054},
ISSN = {0894-0347},
MRCLASS = {05C80 (42C10)},
MRNUMBER = {1678031},
MRREVIEWER = {Mark R. Jerrum},
DOI = {10.1090/S0894-0347-99-00305-7},
ZBLNUMBER = {0932.05084},
} -
[MR2116574] E. Friedgut, "Hunting for sharp thresholds," Random Structures Algorithms, vol. 26, iss. 1-2, pp. 37-51, 2005.
@article {MR2116574, MRKEY = {2116574},
AUTHOR = {Friedgut, Ehud},
TITLE = {Hunting for sharp thresholds},
JOURNAL = {Random Structures Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {26},
YEAR = {2005},
NUMBER = {1-2},
PAGES = {37--51},
ISSN = {1042-9832},
MRCLASS = {05C80 (60C05)},
MRNUMBER = {2116574},
MRREVIEWER = {Michael Krivelevich},
DOI = {10.1002/rsa.20042},
ZBLNUMBER = {1059.05092},
} -
[MR1371123] E. Friedgut and G. Kalai, "Every monotone graph property has a sharp threshold," Proc. Amer. Math. Soc., vol. 124, iss. 10, pp. 2993-3002, 1996.
@article {MR1371123, MRKEY = {1371123},
AUTHOR = {Friedgut, Ehud and Kalai, Gil},
TITLE = {Every monotone graph property has a sharp threshold},
JOURNAL = {Proc. Amer. Math. Soc.},
FJOURNAL = {Proceedings of the American Mathematical Society},
VOLUME = {124},
YEAR = {1996},
NUMBER = {10},
PAGES = {2993--3002},
ISSN = {0002-9939},
CODEN = {PAMYAR},
MRCLASS = {05C80},
MRNUMBER = {1371123},
MRREVIEWER = {Andrzej Ruci{ń}ski},
DOI = {10.1090/S0002-9939-96-03732-X},
ZBLNUMBER = {0864.05078},
} -
[MR2501432] H. Hatami, "Decision trees and influences of variables over product probability spaces," Combin. Probab. Comput., vol. 18, iss. 3, pp. 357-369, 2009.
@article {MR2501432, MRKEY = {2501432},
AUTHOR = {Hatami, Hamed},
TITLE = {Decision trees and influences of variables over product probability spaces},
JOURNAL = {Combin. Probab. Comput.},
FJOURNAL = {Combinatorics, Probability and Computing},
VOLUME = {18},
YEAR = {2009},
NUMBER = {3},
PAGES = {357--369},
ISSN = {0963-5483},
MRCLASS = {42C15 (60C05 91B06)},
MRNUMBER = {2501432},
MRREVIEWER = {Konstantinos Drakakis},
DOI = {10.1017/S0963548309009833},
ZBLNUMBER = {1193.60007},
} -
[MR0026294] W. Hoeffding, "A class of statistics with asymptotically normal distribution," Ann. Math. Statistics, vol. 19, pp. 293-325, 1948.
@article {MR0026294, MRKEY = {0026294},
AUTHOR = {Hoeffding, Wassily},
TITLE = {A class of statistics with asymptotically normal distribution},
JOURNAL = {Ann. Math. Statistics},
FJOURNAL = {Annals of Mathematical Statistics},
VOLUME = {19},
YEAR = {1948},
PAGES = {293--325},
ISSN = {0003-4851},
MRCLASS = {62.0X},
MRNUMBER = {0026294},
MRREVIEWER = {S. S. Wilks},
ZBLNUMBER = {0032.04101},
} -
[KKL] J. Kahn, G. Kalai, and N. Linial, "The influence of variables on Boolean functions," in 29-th Annual Symposium on Foundations of Computer Science, 1988, pp. 68-80.
@inproceedings{KKL,
author={ Kahn, J. and Kalai, G. and Linial, N.},
TITLE={The influence of variables on Boolean functions},
BOOKTITLE = {29-th Annual Symposium on Foundations of Computer Science},
LOCATION={},
PAGES={68--80},
YEAR={1988},
NOTE={}
} -
[MR0472604] G. A. Margulis, "Probabilistic characteristics of graphs with large connectivity," Problemy Peredači Informacii, vol. 10, iss. 2, pp. 101-108, 1974.
@article {MR0472604, MRKEY = {0472604},
AUTHOR = {Margulis, G. A.},
TITLE = {Probabilistic characteristics of graphs with large connectivity},
JOURNAL = {Problemy Peredači Informacii},
FJOURNAL = {Akademiya Nauk SSSR. Institut Problem Peredachi Informatsii Akademii Nauk SSSR. Problemy Peredachi Informatsii},
VOLUME = {10},
YEAR = {1974},
NUMBER = {2},
PAGES = {101--108},
ISSN = {0555-2923},
MRCLASS = {05C99},
MRNUMBER = {0472604},
MRREVIEWER = {Andras Frank},
} -
[MR2630040] E. Mossel, R. O’Donnell, and K. Oleszkiewicz, "Noise stability of functions with low influences: invariance and optimality," Ann. of Math., vol. 171, iss. 1, pp. 295-341, 2010.
@article {MR2630040, MRKEY = {2630040},
AUTHOR = {Mossel, Elchanan and O'Donnell, Ryan and Oleszkiewicz, Krzysztof},
TITLE = {Noise stability of functions with low influences: invariance and optimality},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {171},
YEAR = {2010},
NUMBER = {1},
PAGES = {295--341},
ISSN = {0003-486X},
CODEN = {ANMAAH},
MRCLASS = {60F17 (60G99 91B14)},
MRNUMBER = {2630040},
MRREVIEWER = {Michele Zito},
DOI = {10.4007/annals.2010.171.295},
ZBLNUMBER = {1201.60031},
} -
[MR618273] L. Russo, "On the critical percolation probabilities," Z. Wahrsch. Verw. Gebiete, vol. 56, iss. 2, pp. 229-237, 1981.
@article {MR618273, MRKEY = {0618273},
AUTHOR = {Russo, Lucio},
TITLE = {On the critical percolation probabilities},
JOURNAL = {Z. Wahrsch. Verw. Gebiete},
FJOURNAL = {Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete},
VOLUME = {56},
YEAR = {1981},
NUMBER = {2},
PAGES = {229--237},
ISSN = {0044-3719},
MRCLASS = {60K35 (82A43)},
MRNUMBER = {0618273},
MRREVIEWER = {J. Theodore Cox},
DOI = {10.1007/BF00535742},
ZBLNUMBER = {0457.60084},
} -
[MR671248] L. Russo, "An approximate zero-one law," Z. Wahrsch. Verw. Gebiete, vol. 61, iss. 1, pp. 129-139, 1982.
@article {MR671248, MRKEY = {0671248},
AUTHOR = {Russo, Lucio},
TITLE = {An approximate zero-one law},
JOURNAL = {Z. Wahrsch. Verw. Gebiete},
FJOURNAL = {Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete},
VOLUME = {61},
YEAR = {1982},
NUMBER = {1},
PAGES = {129--139},
ISSN = {0044-3719},
CODEN = {ZWVGAA},
MRCLASS = {60K35},
MRNUMBER = {0671248},
MRREVIEWER = {R. T. Smythe},
DOI = {10.1007/BF00537230},
ZBLNUMBER = {0501.60043},
} -
[MR1303654] M. Talagrand, "On Russo’s approximate zero-one law," Ann. Probab., vol. 22, iss. 3, pp. 1576-1587, 1994.
@article {MR1303654, MRKEY = {1303654},
AUTHOR = {Talagrand, Michel},
TITLE = {On {R}usso's approximate zero-one law},
JOURNAL = {Ann. Probab.},
FJOURNAL = {The Annals of Probability},
VOLUME = {22},
YEAR = {1994},
NUMBER = {3},
PAGES = {1576--1587},
ISSN = {0091-1798},
CODEN = {APBYAE},
MRCLASS = {28A35 (60K35)},
MRNUMBER = {1303654},
URL = {http://links.jstor.org/sici?sici=0091-1798(199407)22:3<1576:ORAZL>2.0.CO;2-S&origin=MSN},
ZBLNUMBER = {0819.28002},
}
Full Article