×

Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome? (English. French summary) Zbl 1412.60052

Summary: Consider a monotone Boolean function \(f:\{0,1\}^{n}\rightarrow\{0,1\}\) and the canonical monotone coupling \(\{\eta_{p}:p\in[0,1]\}\) of an element in \(\{0,1\}^{n}\) chosen according to product measure with intensity \(p\in[0,1]\). The random point \(p\in[0,1]\) where \(f(\eta_{p})\) flips from \(0\) to \(1\) is often concentrated near a particular point, thus exhibiting a threshold phenomenon. For a sequence of such Boolean functions, we peer closely into this threshold window and consider, for large \(n\), the limiting distribution (properly normalized to be nondegenerate) of this random point where the Boolean function switches from being 0 to 1. We determine this distribution for a number of the Boolean functions which are typically studied and pay particular attention to the functions corresponding to iterated majority and percolation crossings. It turns out that these limiting distributions have quite varying behavior. In fact, we show that any nondegenerate probability measure on \(\mathbb{R}\) arises in this way for some sequence of Boolean functions.

MSC:

60F20 Zero-one laws
60F99 Limit theorems in probability theory
60K35 Interacting random processes; statistical mechanics type models; percolation theory
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] M. Aizenman. On the number of incipient spanning clusters.Nuclear Phys. B485(3) (1997) 551-582. · Zbl 0925.82112 · doi:10.1016/S0550-3213(96)00626-8
[2] 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. · Zbl 0986.60002 · doi:10.1007/BF02698830
[3] B. Bollobás.Random Graphs, 2nd edition.Cambridge Studies in Advanced Mathematics73. Cambridge University Press, Cambridge, 2001.
[4] B. Bollobás and A. Thomason. Threshold functions.Combinatorica7(1) (1987) 35-38. · Zbl 0648.05048 · doi:10.1007/BF02579198
[5] C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs. I. The scaling window under the triangle condition.Random Structures Algorithms27(2) (2005) 137-184. · Zbl 1076.05071 · doi:10.1002/rsa.20051
[6] C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs. II. The lace expansion and the triangle condition.Ann. Probab.33(5) (2005) 1886-1944. · Zbl 1079.05087 · doi:10.1214/009117905000000260
[7] J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries.Geom. Funct. Anal.7(3) (1997) 438-461. · Zbl 0982.20004 · doi:10.1007/s000390050015
[8] H. Duminil-Copin. Limit of the Wulff crystal when approaching critically for site percolation on the triangular lattice.Electron. Commun. Probab.18(93) (2013) 9. · Zbl 1307.82005
[9] R. Durrett.Probability: Theory and Examples, 4th edition.Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010.
[10] E. M. Elçi. Personal communication, 2016.
[11] P. Erdős and A. Rényi. On the evolution of random graphs.Magyar Tud. Akad. Mat. Kutató Int. Közl.5(1960) 17-61. · Zbl 0103.16301
[12] R. Fitzner and R. van der Hofstad. Nearest-neighbor percolation function is continuous for \(d>10\). Preprint. Available atarXiv:1506.07977. · Zbl 1364.60130
[13] E. Friedgut. Sharp thresholds of graph properties, and the \(k\)-sat problem.J. Amer. Math. Soc.12(4) (1999) 1017-1054. With an appendix by Jean Bourgain. · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[14] E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold.Proc. Amer. Math. Soc.124(10) (1996) 2993-3002. · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[15] C. Garban, G. Pete and O. Schramm. Pivotal, cluster, and interface measures for critical planar percolation.J. Amer. Math. Soc.26(4) (2013) 939-1024. · Zbl 1276.60111 · doi:10.1090/S0894-0347-2013-00772-9
[16] C. Garban, G. Pete and O. Schramm. The scaling limits of near-critical and dynamical percolation. Preprint. Available atarXiv:1305.5526. · Zbl 1219.60084 · doi:10.1007/s11511-010-0051-x
[17] C. Garban and J. E. Steif. Noise sensitivity and percolation. InProbability and Statistical Physics in Two and More Dimensions49-154.Clay Math. Proc.15. Amer. Math. Soc., Providence, RI, 2012.
[18] C. Garban and J. E. Steif.Noise Sensitivity of Boolean Functions and Percolation. Cambridge University Press, Cambridge, 2015. · Zbl 1355.06001
[19] G. Grimmett.Percolation, 2nd edition.Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]321. Springer-Verlag, Berlin, 1999. · Zbl 0926.60004
[20] A. Hammond, E. Mossel and G. Pete. Exit time tails from pairwise decorrelation in hidden Markov chains, with applications to dynamical percolation.Electron. J. Probab.17(68) (2012) 16. · Zbl 1260.60151
[21] T. Hara. Mean-field critical behaviour for correlation length for percolation in high dimensions.Probab. Theory Related Fields86(3) (1990) 337-385. · Zbl 0685.60102 · doi:10.1007/BF01208256
[22] T. Hara and G. Slade. Mean-field critical behaviour for percolation in high dimensions.Comm. Math. Phys.128(1990) 333-391. · Zbl 0698.60100 · doi:10.1007/BF02108785
[23] T. Hara and G. Slade. The scaling limit of the incipient infinite cluster in high-dimensional percolation, II. Integrated super-Brownian excursion.J. Math. Phys.41(3) (2000) 1244-1293. · Zbl 0977.82022 · doi:10.1063/1.533186
[24] M. Heydenreich and R. van der Hofstad. Random graph asymptotics on high-dimensional tori.Comm. Math. Phys.270(2) (2007) 335-358. · Zbl 1128.82010 · doi:10.1007/s00220-006-0152-8
[25] M. Heydenreich and R. van der Hofstad. Random graph asymptotics on high-dimensional tori II: Volume, diameter and mixing time.Probab. Theory Related Fields149(3-4) (2011) 397-415. · Zbl 1229.60108 · doi:10.1007/s00440-009-0258-y
[26] M. Heydenreich and R. van der Hofstad. Progress in high-dimensional percolation and random graphs. Lecture notes for the CRM-PIMS Summer School in Probability 2015. Available athttp://www.win.tue.nl/ rhofstad/survey-high-d-percolation.pdf.
[27] M. Heydenreich, R. van der Hofstad and T. Hulshof. Random walk on the high-dimensional IIC.Comm. Math. Phys.329(1) (2014) 57-115. · Zbl 1302.82050 · doi:10.1007/s00220-014-1931-2
[28] M. Heydenreich, R. van der Hofstad, T. Hulshof and G. Miermont. Backbone scaling limit of the high-dimensional IIC. In preparation.
[29] R. van der Hofstad and A. A. Járai. The incipient infinite cluster for high-dimensional unoriented percolation.J. Stat. Phys.114(3-4) (2004) 625-663. · Zbl 1061.82016
[30] R. van der Hofstad and A. Sapozhnikov. Cycle structure of percolation on high-dimensional tori.Ann. Inst. Henri Poincaré Probab. Stat.50(3) (2014) 999-1027. · Zbl 1297.05222 · doi:10.1214/13-AIHP565
[31] J. Kahn, G. Kalai and N. Linial. The influence of variables on Boolean functions. In29th Annual Symposium on Foundations of Computer Science68-80, 1988.
[32] G. Kalai and S. Safra. Threshold phenomena and influence: Perspectives from mathematics, computer science, and economics. InComputational Complexity and Statistical Physics25-60.St. Fe Inst. Stud. Sci. Complex.Oxford Univ. Press, New York, 2006. · Zbl 1156.82317
[33] R. Kenna and B. Berche. Universal finite-size scaling for percolation theory in high dimensions. Preprint. Available atarXiv:1606.00315. · Zbl 1375.82039
[34] H. Kesten. Scaling relations for \(2\) D-percolation.Comm. Math. Phys.109(1) (1987) 109-156. · Zbl 0616.60099
[35] G. Kozma. Personal communication, 2016.
[36] G. Kozma and A. Nachmias. The Alexander-Orbach conjecture holds in high dimensions.Invent. Math.178(2009) 635-654. · Zbl 1180.82094 · doi:10.1007/s00222-009-0208-4
[37] G. Kozma and A. Nachmias. Arm exponents in high dimensional percolation.J. Amer. Math. Soc.24(2) (2011) 375-409. · Zbl 1219.60085 · doi:10.1090/S0894-0347-2010-00684-4
[38] R. P. Langlands. The renormalization fixed point as a mathematical object. InTwenty Years of Bialowieza: A Mathematical Anthology185-216.World Sci. Monogr. Ser. Math.8. World Sci. Publ., Hackensack, NJ, 2005.
[39] R. P. Langlands and M.-A. Lafortune. Finite models for percolation. InRepresentation Theory and Analysis on Homogeneous Spaces(New Brunswick, NJ,1993) 227-246.Contemp. Math.177. Amer. Math. Soc., Providence, RI, 1994. · Zbl 0812.60092
[40] T. Łuczak. Random trees and random graphs.Random Structures Algorithms13(1998) 485-500. In Proceedings of the Eighth International Conference “Random Structures and Algorithms” (Poznan, 1997). · Zbl 0959.05111 · doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<485::AID-RSA16>3.0.CO;2-Y
[41] E. Mossel and R. O’Donnell. On the noise sensitivity of monotone functions.Random Structures Algorithms23(3) (2003) 333-350. · Zbl 1047.68106 · doi:10.1002/rsa.10097
[42] A. Nachmias and Y. Peres. The critical random graph, with martingales.Israel J. Math.176(1) (2010) 29-41. · Zbl 1215.05168
[43] P. Nolin. Near-critical percolation in two dimensions.Electron. J. Probab.13(55) (2008) 1562-1623. · Zbl 1189.60182 · doi:10.1214/EJP.v13-565
[44] R. O’Donnell, M. Saks, O. Schramm and R. Servedio. Every decision tree has an influential variable. In46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), 31-39, 2005.
[45] G. Pete. How long could it take to establish a crossing in dynamical percolation? Talk at MFO, Oberwolfach, September 2012. Available athttp://www.math.bme.hu/ gabor/DynExitOwolfach.pdf.
[46] R. Rossignol. Arbitrary threshold widths for monotone, symmetric properties.J. Appl. Probab.44(1) (2007) 164-180. · Zbl 1140.60004 · doi:10.1017/S0021900200002783
[47] L. Russo. An approximate zero-one law.Z. Wahrsch. Verw. Gebiete61(1) (1982) 129-139. · Zbl 0501.60043 · doi:10.1007/BF00537230
[48] O. Schramm and S. Smirnov. On the scaling limits of planar percolation.Ann. Probab.39(5) (2011) 1768-1814. With an appendix by Christophe Garban. · Zbl 1231.60116 · doi:10.1214/11-AOP659
[49] O. Schramm and J. Steif. Quantitative noise sensitivity and exceptional times for percolation.Ann. of Math. (2)171(2) (2010) 619-672. · Zbl 1213.60160
[50] G. Slade. Scaling limits and super-Brownian motion.Notices Amer. Math. Soc.49(9) (2002) 1056-1067. · Zbl 1126.60322
[51] S. Smirnov and W. Werner. Critical exponents for two-dimensional percolation.Math. Res. Lett.8(5-6) (2001) 729-744. · Zbl 1009.60087 · doi:10.4310/MRL.2001.v8.n6.a4
[52] M. Talagrand. On Russo’s approximate zero-one law.Ann. Probab.22(3) (1994) 1576-1587. · Zbl 0819.28002 · doi:10.1214/aop/1176988612
[53] W. Werner. Lectures on two-dimensional critical percolation. InStatistical Mechanics297-360.IAS/Park City Math. Ser.16. Amer. Math. Soc., Providence, RI, 2009. · Zbl 1180.82003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.