Threshold for monotone symmetric properties through a logarithmic Sobolev inequality (Q858978): Difference between revisions

For \(p\in]0,1[\), let \(\mu_p\) denote the probability on \(\{0,1\}^n\) given by \(\mu_p(\{x\})=\prod_{i=1}^np^{x_i}(1-p)^{1-x_i},\) \(x=(x_1,\dots,x_n)\in\{0,1\}^n\). A nonempty set \(A\subset\{0,1\}^n\) is called monotone if \(x\in A\) whenever \(x'\in A\) and \(x\geq x'\). If \(A\neq\{0,1\}^n\) is monotone and \(\varepsilon\in\;]0,1/2[\), the quantity \(\tau(A,\varepsilon)=p(1-\varepsilon)-p(\varepsilon)\) is called the threshold width of \(A\) at level \(\varepsilon\), where \(p(\alpha)\) is the unique number in \(]0,1[\) such that \(\mu_{p(\alpha)}(A)=\alpha\). Here is the main result. Let \(A\neq\{0,1\}^n\) be monotone, and assume there exists a subgroup \(\pi\) of the group of all permutations of \(\{1,\dots,n\}\) such that for any \(i,j\in\{1,\dots,n\}\) there is \(\pi\in\Pi\) with \(\pi_i=j\), and that \(A=\pi(A)\) for all \(\pi\in\Pi\), where \(\pi(x_1,\dots,x_n)=(x_{\pi_1},\dots,x_{\pi_n})\), \(x\in\{0,1\}^n\). Then \((d/(dp))\mu_p (A)\geq s_n\mu_p(A)(1-\mu_p(A))/c(p)\), where \((s_n)_{n\geq2}\) is an intricate sequence of positive numbers with \(s_n\sim\log n\) as \(n\to\infty\), and \(c(p)\) is a concave function with \(c(0+)=0\), \(c(p)=c(1-p)\) and \(c(p)\leq c(1/2)=1/2\). From this it follows that \(\tau(A,\varepsilon)\leq(1/(s_n))\log((1-\varepsilon)/\varepsilon)\). Given the standard of ``The Annals of Probability'', the paper is somewhat negligently written.