Manuscript Psy01-A@1 · Psy01-A.tex · theorem · 94477fa3

Theorem: Observable concentration under bounded edge influence

Concentration: what survivor counts do and do not imply › A classical residual-influence theorem · lines 1631–1666 · proof included or linked

Psy01-A@1#thm:edgeconcentration, Psy01-A@1#eq:efronsteinmask, Psy01-A@1#eq:mcdiarmidmask

Back to manuscript

Let $M_{1}, \dots, M_{N}$ be independent Bernoulli mask variables, with probabilities $p_{i}$ . Let $F (M)$ be a bounded scalar observable, and suppose replacing coordinate $i$ can change $F$ by at most $κ_{i}$ , uniformly over the other coordinates. Then

Var F P {\abs F - E F \geq t} \leq i = 1 \sum^{N} p_{i} (1 - p_{i}) κ_{i}^{2}, \leq 2 exp (- \frac{2 t ^{2}}{\sum _{i} κ _{i} ^{2}}) .

If $p_{i} = p$ and $κ_{i} \leq C / N$ , then

Var F \leq \frac{p ( 1 - p ) C ^{2}}{N} .

Proof. Let $M^{(i)}$ replace $M_{i}$ by an independent copy. The Efron–Stein inequality EfronStein gives

Var F \leq \frac{1}{2} i \sum E (F (M) - F (M^{(i)}))^{2} .

The two Bernoulli values differ with probability $2 p_{i} (1 - p_{i})$ , and the squared difference is at most $κ_{i}^{2}$ , proving (eq:efronsteinmask). The bounded-differences inequality McDiarmid gives (eq:mcdiarmidmask). Substitute $C / N$ for the last claim.

Displayed formulas in this passage

Psy01-A@1#eq:efronsteinmask · line 1638
$Var F P {\abs F - E F \geq t} \leq i = 1 \sum^{N} p_{i} (1 - p_{i}) κ_{i}^{2}, \leq 2 exp (- \frac{2 t ^{2}}{\sum _{i} κ _{i} ^{2}}) .$
Psy01-A@1#eq:mcdiarmidmask · line 1638
$Var F P {\abs F - E F \geq t} \leq i = 1 \sum^{N} p_{i} (1 - p_{i}) κ_{i}^{2}, \leq 2 exp (- \frac{2 t ^{2}}{\sum _{i} κ _{i} ^{2}}) .$
unlabeled · line 1649
$Var F \leq \frac{p ( 1 - p ) C ^{2}}{N} .$
unlabeled · line 1657
$Var F \leq \frac{1}{2} i \sum E (F (M) - F (M^{(i)}))^{2} .$

Nearby in this section

section: A classical residual-influence theorem