Concentration and influences (Q1806267): Difference between revisions

Let \(\Omega\) be the discrete cube \(\{0,1\}^N\) equipped with the product probability \(P\) giving mass \(p\in (0,1)\) to \(1\). For \(x, y\in\Omega\), let \(d(x,y):=\text{card}\{i\leq N\colon x_i\not =y_i\}\) be the Hamming distance. Also for a subset \(A\subset\Omega\), let \(I_i(A):=P(\{x\in A\colon T_i(x)\not\in A\})\), where \(T_i(x)\) is the point obtained from \(x\) by changing its \(i\)th coordinate, so that \(I_i(A)\) is the influence of the \(i\)th coordinate on a subset \(A\) of \(\Omega\). In the paper under review it is proved that the integral \(\int_{\Omega}d(x,A) dP(x)\), \(A\subset\Omega\), does not exceed the sum \(\sum_{i\leq N}I_i(A)\) multiplied by \(\max\{p,1-p\}/P(A)\). Also, the author proves several other related bounds and discusses their sharpness by giving illuminating examples.