Concentration and influences (Q1806267): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:15, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Concentration and influences |
scientific article |
Statements
Concentration and influences (English)
0 references
14 March 2000
0 references
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.
0 references
concentration of measure
0 references
Hamming distance
0 references
transportation cost
0 references