124 Boolean Analysis — Restriction Card Tail

124.1 Overview

Under a Bernoulli(\(p\))-random restriction with free-coordinate set \(J\), the count \(\left\lvert U \cap J\right\rvert \) of free coordinates inside a fixed set \(U\) behaves like a \(\mathrm{Binomial}(\left\lvert U\right\rvert , p)\) variable. This module computes its first and second moments from the marginal \(\Pr [T \subseteq J] = p^{\left\lvert T\right\rvert }\) and derives the elementary Chebyshev lower-tail bounds \(\Pr [\left\lvert U \cap J\right\rvert \lt k] \le 3/(4k)\) and \(\Pr [\left\lvert U \cap J\right\rvert \ge k] \ge 1/4\) used by the restriction \(\Rightarrow \) Fourier-concentration transfer (O’Donnell Lemma 4.21), together with the complement rule for Bernoulli-restriction probabilities.

124.2 Declarations

Lemma 124.1 Subset-of-free-variables indicator factors per coordinate

✓

For a set \(T \subseteq \{ 0,\dots ,n-1\} \) and a restriction \(\rho \), the indicator of the event \(T \subseteq \mathrm{freeVars}(\rho )\) equals the product over all coordinates \(i\) of the factor that is the indicator of \(\rho (i) = \star \) when \(i \in T\), and \(1\) otherwise.

Theorem 124.2 Free-set marginal \(\Pr [T \subseteq J] = p^{\left\lvert T\right\rvert }\)

✓

Under a Bernoulli(\(p\))-random restriction with free-coordinate set \(J\), the probability that a fixed set \(T\) is contained in \(J\) is

\[ \Pr [T \subseteq J] \; =\; p^{\left\lvert T\right\rvert } . \]

This is the first-moment half of O’Donnell Proposition 4.17.

Lemma 124.3 Free-coordinate count as a sum of indicators

✓

For a set \(U\) and a restriction \(\rho \) with free-coordinate set \(J\), the real number \(\left\lvert U \cap J\right\rvert \) equals \(\sum _{i \in U} \mathbf{1}[\rho (i) = \star ]\).

Lemma 124.4 Expectation of one free-coordinate indicator

✓

For each coordinate \(i\), the Bernoulli(\(p\))-weighted sum over all restrictions of the indicator that \(i\) is free equals \(p\); that is, \(\mathbb {E}[\mathbf{1}[i \in J]] = p\).

Lemma 124.5 Expectation of a product of two free-coordinate indicators

✓

For distinct coordinates \(i \ne j\), the Bernoulli(\(p\))-weighted sum over all restrictions of the product of the two indicators that \(i\) and \(j\) are free equals \(p^2\); that is, \(\mathbb {E}[\mathbf{1}[i \in J]\, \mathbf{1}[j \in J]] = p^2\).

Lemma 124.6 First moment of the free-coordinate count

✓

Under a Bernoulli(\(p\))-random restriction with free set \(J\), for every set \(U\),

\[ \mathbb {E}\bigl[\left\lvert U \cap J\right\rvert \bigr] \; =\; p \cdot \left\lvert U\right\rvert . \]

Lemma 124.7 Second moment of the free-coordinate count

✓

Under a Bernoulli(\(p\))-random restriction with free set \(J\), for every set \(U\),

\[ \mathbb {E}\bigl[\left\lvert U \cap J\right\rvert ^2\bigr] \; =\; p \cdot \left\lvert U\right\rvert \; +\; p^2\bigl(\left\lvert U\right\rvert ^2 - \left\lvert U\right\rvert \bigr). \]

Lemma 124.8 Variance of the free-coordinate count

✓

For \(0 \le p \le 1\) and every set \(U\), the Bernoulli(\(p\))-weighted mean squared deviation of \(\left\lvert U \cap J\right\rvert \) from \(p\left\lvert U\right\rvert \) is

\[ \mathbb {E}\bigl[(p\left\lvert U\right\rvert - \left\lvert U \cap J\right\rvert )^2\bigr] \; =\; p \cdot \left\lvert U\right\rvert \cdot (1 - p). \]

Theorem 124.9 Chebyshev lower tail for the free-coordinate count

✓

Let \(0 \le p \le 1\), let \(U\) be a set of coordinates and let \(k \ge 1\) satisfy \(3k \le p\left\lvert U\right\rvert \). Then, under a Bernoulli(\(p\))-random restriction with free set \(J\),

\[ \Pr \bigl[\left\lvert U \cap J\right\rvert \lt k\bigr] \; \le \; \frac{3}{4k}. \]

This is the Bernoulli-restriction analogue of the binomial lower tail used in O’Donnell Lemma 4.21, with the textbook bound \(e^{-2k/3}\) replaced by the elementary \(3/(4k) \le 3/4 \lt 1\).

Lemma 124.10 Complement rule for Bernoulli-restriction probability

✓

For \(0 \le p \le 1\) and any decidable event \(E\) on restrictions, \(\Pr [\neg E] = 1 - \Pr [E]\) under the Bernoulli(\(p\))-restriction measure.

Theorem 124.11 Lower bound on the probability of many free coordinates

✓

Let \(0 \le p \le 1\), let \(U\) be a set of coordinates and let \(k \ge 1\) satisfy \(3k \le p\left\lvert U\right\rvert \). Then, under a Bernoulli(\(p\))-random restriction with free set \(J\),

\[ \Pr \bigl[k \le \left\lvert U \cap J\right\rvert \bigr] \; \ge \; \frac{1}{4}, \]

which is the form consumed by the concentration transfer of O’Donnell Lemma 4.21.