20 Boolean Analysis — Bernoulli Cost
20.1 Overview
This module compares the fixed-size restriction model \(R_k\) (uniform over restrictions with exactly \(k\) free variables) with the Bernoulli restriction model \(R_p\), and shows that switching from \(R_k\) to \(R_p\) costs nothing asymptotically: if the bad event has probability at most \((5kw/n)^s\) under every \(R_k\), then under \(R_p\) it has probability at most \((10pw)^s\) plus an exponentially small tail \(e^{-np/3}\) that vanishes as \(n \to \infty \).
20.2 Declarations
For natural numbers \(n\) and \(k\), this is the finite set of restrictions on \(n\) variables whose set of free variables has cardinality exactly \(k\).
The probability of an event under the fixed-size restriction model \(R_k\), which is uniform over restrictions with exactly \(k\) free variables. It is defined as the fraction of restrictions with exactly \(k\) free variables that satisfy the event.
The binomial probability mass function, \(\Pr [\mathrm{Bin}(n,p) = k] = \binom {n}{k}\, p^k\, (1-p)^{n-k}\).
For any event, the fixed-size restriction probability satisfies \(0 \le \mathrm{fixedSizeRestrProb}\, (\mathrm{event})\, k\).
For any event, the fixed-size restriction probability satisfies \(\mathrm{fixedSizeRestrProb}\, (\mathrm{event})\, k \le 1\).
If \(0 \le p \le 1\), then \(0 \le \mathrm{binomialPMF}\, n\, p\, k\) for every \(k\).
If \(0 \le p \le 1\), then the binomial PMF sums to \(1\) over \(k\) ranging in \(\{ 0, \dots , n\} \), i.e. \(\sum _{k=0}^{n} \mathrm{binomialPMF}\, n\, p\, k = 1\). This is the binomial theorem applied to \((p + (1-p))^n = 1\).
For \(0 \le p \le 1\) and any event, the Bernoulli\((p)\) restriction probability decomposes according to the number of free variables:
because conditioning \(R_p\) on having exactly \(k\) free variables yields exactly the model \(R_k\).
For \(0 \lt p \le 1\), the upper tail of the binomial distribution beyond \(2np\) is exponentially small: summing \(\mathrm{binomialPMF}\, n\, p\, k\) over those \(k \in \{ 0, \dots , n\} \) with \(k \gt 2np\) is at most \(e^{-np/3}\).
Let \(n \gt 0\), \(0 \lt p \le 1\), and \(w, s \gt 0\). If the event satisfies \(\mathrm{fixedSizeRestrProb}\, (\mathrm{event})\, k \le (5kw/n)^s\) for every \(k \le n\), then under the Bernoulli model,
For any \(p \gt 0\) and any \(\varepsilon \gt 0\), there exists \(N\) such that for all \(m \ge N\) one has \(e^{-mp/3} \lt \varepsilon \); that is, the tail term decays to \(0\).
Let \(0 \lt p \le 1\), \(w, s \gt 0\), and \(\varepsilon \gt 0\). Then there exists \(N\) such that for every \(n \ge N\) with \(n \gt 0\) and every event satisfying \(\mathrm{fixedSizeRestrProb}\, (\mathrm{event})\, k \le (5kw/n)^s\) for all \(k \le n\), one has \(\Pr _{R_p}[\mathrm{event}] \le (10pw)^s + \varepsilon \). Asymptotically the exponential tail vanishes, leaving only the leading bound \((10pw)^s\).