Influence and sharp-threshold theorems for monotonic measures (Q858979): Difference between revisions

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.