Quantitative noise sensitivity and exceptional times for percolation. (English) Zbl 1213.60160

In percolation theory, typical events of interest depend on a huge (or infinite) number of independent Bernoulli random variables. How does the outcome of such an event change if we allow a growing number of these random variables to change value each with small probability? The notion of noise sensitivity formalizes this question and allows for quantitative answers.
The authors derive noise sensitivity estimates for the event of an open left to right crossing in an (approximate) square box both for critical bond percolation on the two-dimensional integer lattice and for critical site percolation on the triangular lattice. A key step for the proofs is a bound on the Fourier coefficients of a function \(f(x)\) depending on the number of bits of \(x\) that a randomized algorithm needs in order to determine the value of \(f(x)\).
While classical percolation is a static model with the bonds or sites declared open or closed according to the values of independent Bernoulli random variables (with success probability \(p\)), in the dynamical percolation model, these Bernoulli random variables undergo a time evolution. In the simplest situation, they perform the evolution of indepedent two-state Markov chains (in equilibrium) that change value to “open” at rate \(p\) and to “closed” at rate \(1-p\).
It is well known that for critical site percolation on the triangular lattice, almost surely, there is no infinite open cluster. The main result of Schramm and Steif is that for dynamical critical site percolation on the triangular lattice, with probability one there are “exceptional times” where an infinite open cluster exists. In addition, they show that the Hausdorff dimension of the set of such times is almost surely constant and takes a value in the interval \([1/6,31/36]\). Furthermore, the authors show that there are no times where more than one infinite open cluster exists.
The results depend on the so-called critical exponents of percolation that are known explicitly for site percolation on the triangular lattice. For bond percolation on the integer lattice, even existence of these exponents has not been established. For this case, the authors have analogous but less complete results.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
82C43 Time-dependent percolation in statistical mechanics
03D15 Complexity of computation (including implicit computational complexity)
42B05 Fourier series and coefficients in several variables
Full Text: DOI arXiv Link


[1] M. Aizenman, S. Duplantier, and A. Aharony, ”Connectivity exponents and external perimeter in 2D percolation models,” Phys. Rev. Lett., vol. 83, pp. 1359-1362, 1999.
[2] I. Benjamini, G. Kalai, and O. Schramm, ”Noise sensitivity of Boolean functions and applications to percolation,” Inst. Hautes Études Sci. Publ. Math., iss. 90, pp. 5-43 (2001), 1999. · Zbl 0986.60002 · doi:10.1007/BF02698830
[3] I. Benjamini and O. Schramm, ”Exceptional planes of percolation,” Probab. Theory Related Fields, vol. 111, iss. 4, pp. 551-564, 1998. · Zbl 0910.60076 · doi:10.1007/s004400050177
[4] I. Benjamini, O. Schramm, and D. B. Wilson, ”Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read,” in STOC’05: Proc. 37th Annual ACM Symposium on Theory of Computing, New York: ACM, 2005, pp. 244-250. · Zbl 1192.68851 · doi:10.1145/1060590.1060627
[5] J. van den Berg, R. Meester, and D. G. White, ”Dynamic Boolean models,” Stochastic Process. Appl., vol. 69, iss. 2, pp. 247-257, 1997. · Zbl 0911.60083 · doi:10.1016/S0304-4149(97)00044-6
[6] E. I. Broman and J. E. Steif, ”Dynamical stability of percolation for some interacting particle systems and \(\epsilon\)-movability,” Ann. Probab., vol. 34, iss. 2, pp. 539-576, 2006. · Zbl 1107.82058 · doi:10.1214/009117905000000602
[7] F. Camia and C. M. Newman, ”Two-dimensional critical percolation: the full scaling limit,” Comm. Math. Phys., vol. 268, iss. 1, pp. 1-38, 2006. · Zbl 1117.60086 · doi:10.1007/s00220-006-0086-1
[8] R. Diestel, Graph Theory, New York: Springer-Verlag, 1997. · Zbl 1086.05001
[9] S. N. Evans, ”Local properties of Lévy processes on a totally disconnected group,” J. Theoret. Probab., vol. 2, iss. 2, pp. 209-259, 1989. · Zbl 0683.60010 · doi:10.1007/BF01053411
[10] P. J. Fitzsimmons and R. K. Getoor, ”On the potential theory of symmetric Markov processes,” Math. Ann., vol. 281, iss. 3, pp. 495-512, 1988. · Zbl 0627.60067 · doi:10.1007/BF01457159
[11] R. K. Getoor and M. J. Sharpe, ”Naturality, standardness, and weak duality for Markov processes,” Z. Wahrsch. Verw. Gebiete, vol. 67, iss. 1, pp. 1-62, 1984. · Zbl 0553.60070 · doi:10.1007/BF00534082
[12] G. Grimmett, Percolation, Second ed., New York: Springer-Verlag, 1999. · Zbl 0926.60004
[13] O. Häggström, Y. Peres, and J. E. Steif, ”Dynamical percolation,” Ann. Inst. H. Poincaré Probab. Statist., vol. 33, iss. 4, pp. 497-528, 1997. · Zbl 0894.60098 · doi:10.1016/S0246-0203(97)80103-3
[14] T. Hara and G. Slade, ”Mean-field behaviour and the lace expansion,” in Probability and Phase Transition (Cambridge, 1993), Dordrecht: Kluwer Acad. Publ., 1994, pp. 87-122. · Zbl 0831.60107
[15] T. E. Harris, ”A lower bound for the critical probability in a certain percolation process,” Proc. Cambridge Philos. Soc., vol. 56, pp. 13-20, 1960. · Zbl 0122.36403
[16] J. Hawkes, ”Some geometric aspects of potential theory,” in Stochastic Analysis and Applications (Swansea, 1983), New York: Springer-Verlag, 1984, pp. 130-154. · Zbl 0558.60055
[17] J. Kahane, Some Random Series of Functions, Second ed., Cambridge: Cambridge Univ. Press, 1985. · Zbl 0571.60002
[18] H. Kesten, Percolation Theory for Mathematicians, Mass.: Birkhäuser, 1982. · Zbl 0522.60097
[19] H. Kesten, ”Scaling relations for \(2\)D-percolation,” Comm. Math. Phys., vol. 109, iss. 1, pp. 109-156, 1987. · Zbl 0616.60099 · doi:10.1007/BF01205674
[20] H. Kesten, V. Sidoravicius, and Y. Zhang, ”Almost all words are seen in critical site percolation on the triangular lattice,” Electron. J. Probab., vol. 3, p. 10, 1998. · Zbl 0908.60082
[21] H. Kesten and Y. Zhang, ”Strict inequalities for some critical exponents in two-dimensional percolation,” J. Statist. Phys., vol. 46, iss. 5-6, pp. 1031-1055, 1987. · Zbl 0683.60081 · doi:10.1007/BF01011155
[22] G. F. Lawler, Conformally Invariant Processes in the Plane, Providence, RI: Amer. Math. Soc., 2005. · Zbl 1074.60002
[23] G. F. Lawler, O. Schramm, and W. Werner, ”One-arm exponent for critical 2D percolation,” Electron. J. Probab., vol. 7, p. 13, 2002. · Zbl 1015.60091
[24] G. F. Lawler, O. Schramm, and W. Werner, ”Sharp estimates for Brownian non-intersection probabilities,” in In and Out of Equilibrium (Mambucaba, 2000), Boston, MA: Birkhäuser, 2002, pp. 113-131. · Zbl 1011.60062
[25] Y. Peres, O. Schramm, S. Sheffield, and D. B. Wilson, ”Random-turn hex and other selection games,” Amer. Math. Monthly, vol. 114, iss. 5, pp. 373-387, 2007. · Zbl 1153.91012
[26] Y. Peres and J. E. Steif, ”The number of infinite clusters in dynamical percolation,” Probab. Theory Related Fields, vol. 111, iss. 1, pp. 141-165, 1998. · Zbl 0906.60069 · doi:10.1007/s004400050165
[27] D. Reimer, ”Proof of the van den Berg-Kesten conjecture,” Combin. Probab. Comput., vol. 9, iss. 1, pp. 27-32, 2000. · Zbl 0947.60093 · doi:10.1017/S0963548399004113
[28] O. Schramm, ”Scaling limits of loop-erased random walks and uniform spanning trees,” Israel J. Math., vol. 118, pp. 221-288, 2000. · Zbl 0968.60093 · doi:10.1007/BF02803524
[29] S. Smirnov, ”Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits,” C. R. Acad. Sci. Paris Sér. I Math., vol. 333, iss. 3, pp. 239-244, 2001. · Zbl 0985.60090 · doi:10.1016/S0764-4442(01)01991-7
[30] S. Smirnov, Critical percolation in the plane. I. Conformal invariance and Cardy’s formula, II. Continuum scaling limit (long version).
[31] S. Smirnov and W. Werner, ”Critical exponents for two-dimensional percolation,” Math. Res. Lett., vol. 8, iss. 5-6, pp. 729-744, 2001. · Zbl 1009.60087 · doi:10.4310/MRL.2001.v8.n6.a4
[32] M. Talagrand, ”Concentration of measure and isoperimetric inequalities in product spaces,” Inst. Hautes Études Sci. Publ. Math., iss. 81, pp. 73-205, 1995. · Zbl 0864.60013 · doi:10.1007/BF02699376
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.