Concentration and influences (Q1806267): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q586460 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Rimas Norvaiša / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A measure concentration inequality for contracting Markov chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: How much are increasing sets positively correlated? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new look at independence / rank | |||
Normal rank |
Latest revision as of 09:54, 29 May 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