×

Influence and sharp-threshold theorems for monotonic measures. (English) Zbl 1115.60099

Let \(\Omega=\{0,1\}^n\) or \([0,1]^n\), let \(K=P(\Omega)\) or the Lebesgue \(\sigma\)-algebra of \(\Omega\), and let \(\mu\) be a probability on \(K\) such that \(\mu(\{\omega\})>0\), \(\omega\in\Omega\), if \(\Omega=\{0,1\}^n\), while \(\mu(A)=\int_{A}\rho \,d\lambda\), \(A\in K\), if \(\Omega=[0,1]^n\), where \(\lambda\) is the Lebesgue measure on \(K\) and \(\rho\) is a positive Lebesgue measurable density. \(\mu\) is assumed to satisfy a certain monotonicity property. Put \(I=\{1,\dots,n\}\). For \(\omega=(\omega_1,\dots,\omega_n)\in\Omega\) and \(i\in I\), define \(X_{i}(\omega)=\omega_{i}\). A set \(A\in K\) is called increasing if \(\omega\in A\) whenever \(\omega'\in A\) and \(\omega\geq\omega'\). If \(A\) is increasing and \(i\in I\), the quantities \(I_{A}(i)=\mu(A\mid X_{i}=1)-\mu(A\mid X_{i}=0)\) are called influences. Here are the main results.
Theorem 1. There exists an absolute constant \(c\in(0,\infty)\) such that, for all \(n\) and all increasing \(A\), there is \(i\in I\) satisfying \(I_{A}(i)\geq c(\mu(A)\wedge(1-\mu(A))(\log n)/n\).
Theorem 2. Let \(\Pi\) be a subgroup of the group of all permutations of \(I\) such that for any \(i,j\in I\) there is \(\pi\in\Pi\) with \(\pi_{i}=j\), and that \(\mu(\{\omega\})=\mu(\{\pi(\omega)\})\) for all \(\omega\in\Omega\) and \(\pi\in\Pi\), where \(\pi(\omega_1,\dots,\omega_n)=(\omega_{\pi_1},\dots,\omega_{\pi_{n}})\), \(\omega\in\Omega\). For \(\Omega=\{0,1\}^n\) and \(p\in(0,1)\), define the probability \(\mu_{p}\) on \(K\) by \(\mu_{p}(\{\omega\})=C\prod_{i=1}^n p^{\omega_i}(1-p)^{1-\omega_i}\), \(\omega=(\omega_1,\dots,\omega_n)\in\Omega\), where \(C\) is the normalizing constant. Then there exists an absolute constant \(c\in(0,\infty)\) such that, for all \(n\) and all increasing \(A\) with \(A=\pi(A)\), \(\pi\in\Pi\), one has \((d/(dp))\mu_{p}(A)\geq c\xi_{p}(\mu_{p}(A)\wedge(1-\mu_{p}(A))\log n\), where \(\xi_{p}=\int_\Omega X_I \,d\mu_{p}(1-\int_\Omega X_I \,d\mu_{p})/p(1-p)\). These results have applications to problems of discrete probability such as the random cluster model.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60E15 Inequalities; stochastic orderings
82B31 Stochastic methods applied to problems in equilibrium statistical mechanics
82B43 Percolation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Batty, C. J. K. and Bollmann, H. W. (1980). Generalised Holley–Preston inequalities on measure spaces and their products. Z. Wahrsch. Verw. Gebiete 53 157–173. · Zbl 0417.60006 · doi:10.1007/BF01013313
[2] Ben-Or, M. and Linial, N. (1990). Collective coin flipping. In Randomness and Computation 91–115. Academic Press, New York.
[3] Bezuidenhout, C. E., Grimmett, G. R. and Kesten, H. (1993). Strict inequality for critical values of Potts models and random-cluster processes. Comm. Math. Phys. 158 1–16. · Zbl 0783.60100 · doi:10.1007/BF02097229
[4] Bollobás, B. and Riordan, O. (2006). The critical probability for random Voronoi percolation in the plane is \(\frac12\). Probab. Theory Related Fields 136 417–468. · Zbl 1100.60054 · doi:10.1007/s00440-005-0490-z
[5] Bollobás, B. and Riordan, O. (2006). A short proof of the Harris–Kesten theorem. Bull. London Math. Soc. 38 470–484. · Zbl 1104.60060 · doi:10.1112/S002460930601842X
[6] Bourgain, J., Kahn, J., Kalai, G., Katznelson, Y. and Linial, N. (1992). The influence of variables in product spaces. Israel J. Math. 77 55–64. · Zbl 0771.60002 · doi:10.1007/BF02808010
[7] Chayes, J. T. and Chayes, L. (1986). Percolation and random media. In Critical Phenomena , Random Systems and Gauge Theories (K. Osterwalder and R. Stora, eds.) 1001–1142. North-Holland, Amsterdam. · Zbl 0661.60120
[8] Fortuin, C. M. (1972). On the random-cluster model. III. The simple random-cluster process. Physica 59 545–570. · doi:10.1016/0031-8914(72)90087-0
[9] Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971). Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22 89–103. · Zbl 0346.06011 · doi:10.1007/BF01651330
[10] Friedgut, E. (2004). Influences in product spaces: KKL and BKKKL revisited. Combin. Probab. Comput. 13 17–29. · Zbl 1057.60007 · doi:10.1017/S0963548303005832
[11] Friedgut, E. and Kalai, G. (1996). Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993–3002. JSTOR: · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[12] Grimmett, G. R. (1999). Percolation . Springer, Berlin. · Zbl 0926.60004
[13] Grimmett, G. R. (2003). The random-cluster model. In Probability on Discrete Structures . Encyclopedia of Mathematical Sciences (H. Kesten, ed.) 110 73–123. Springer, Berlin. · Zbl 1045.60105
[14] Grimmett, G. R. (2006). The Random-Cluster Model . Springer, Berlin. · Zbl 1122.60087
[15] Häggström, O., Kalai, G. and Mossel, E. (2005). A law of large numbers for weighted majority. Adv. in Appl. Math. 37 112–123. · Zbl 1142.60006 · doi:10.1016/j.aam.2005.08.002
[16] Kahn, J., Kalai, G. and Linial, N. (1988). The influence of variables on Boolean functions. In Proceedings of 29th Symposium on the Foundations of Computer Science 68–80. Computer Science Press.
[17] Preston, C. J. (1974). A generalization of the FKG inequalities. Comm. Math. Phys. 36 233–241. · doi:10.1007/BF01645981
[18] Russo, L. (1978). A note on percolation. Z. Wahrsch.Verw. Gebiete 43 39–48. · Zbl 0363.60120 · doi:10.1007/BF00535274
[19] Russo, L. (1981). On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete 56 229–237. · Zbl 0457.60084 · doi:10.1007/BF00535742
[20] Russo, L. (1982). An approximate zero–one law. Z. Wahrsch. Verw. Gebiete 61 129–139. · Zbl 0501.60043 · doi:10.1007/BF00537230
[21] Seymour, P. D. and Welsh, D. J. A. (1978). Percolation probabilities on the square lattice. In Advances in Graph Theory (B. Bollobás, ed.) 227–245. North-Holland, Amsterdam. · Zbl 0405.60015 · doi:10.1016/S0167-5060(08)70509-0
[22] Talagrand, M. (1994). On Russo’s approximate zero–one law. Ann. Probab. 22 1576–1587. · Zbl 0819.28002 · doi:10.1214/aop/1176988612
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.