17 Boolean Analysis — Bernoulli Cost
17.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 \).
17.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}\).
Fix natural numbers \(n\) and \(k\), and let \(E\) be any event on restrictions of \(n\) variables. Then the probability of \(E\) under the fixed-size restriction model \(R_k\) — the uniform distribution over restrictions with exactly \(k\) free variables — is nonnegative:
Let \(E\) be any event, that is, a property of restrictions on \(n\) variables, and let \(k\) be a natural number. Under the fixed-size restriction model \(R_k\) — the uniform distribution over those restrictions on \(n\) variables whose set of free variables has cardinality exactly \(k\) — the probability of \(E\) satisfies \(R_k(E) \le 1\).
Fix a natural number \(n\) and a real number \(p\) with \(0 \le p \le 1\). Then for every natural number \(k\), the binomial probability mass value \(\binom {n}{k}\, p^k\, (1-p)^{n-k}\) is nonnegative.
Let \(n\) be a natural number and let \(p\) be a real number with \(0 \le p \le 1\). Then the binomial probabilities \(\binom {n}{k}\, p^k\, (1-p)^{n-k}\) sum to one over all outcomes,
Fix \(n\) and a real parameter \(p\) with \(0 \le p \le 1\), and let \(\mathrm{event}\) be any (decidable) property of restrictions on \(n\) variables. Then the probability that \(\mathrm{event}\) holds under a Bernoulli(\(p\)) random restriction equals its average over the fixed-size restriction models, weighted by the binomial distribution on the number of free variables:
where \(R_k(\mathrm{event})\) is the fraction of restrictions with exactly \(k\) free variables that satisfy \(\mathrm{event}\).
Let \(n\) be a natural number and let \(p\) be a real number with \(0 \lt p \le 1\). Summing the binomial probability mass function \(\binom {n}{k}\, p^k\, (1-p)^{n-k}\) over those integers \(k \in \{ 0, 1, \dots , n\} \) satisfying \(k \gt 2np\) yields at most \(e^{-np/3}\); that is, the probability that \(\mathrm{Bin}(n,p)\) exceeds twice its mean is bounded by \(e^{-np/3}\).
Let \(n \ge 1\), let \(p \in \mathbb {R}\) satisfy \(0 \lt p \le 1\), and let \(w, s\) be positive integers. Let \(\mathrm{event}\) be a decidable predicate on restrictions of \(n\) variables, and suppose that for every \(k \le n\) its probability under the fixed-size restriction model \(R_k\) satisfies
Then the probability of \(\mathrm{event}\) under a Bernoulli(\(p\)) random restriction satisfies
For every real \(p \gt 0\) and every \(\varepsilon \gt 0\), there exists a natural number \(N\) such that for all natural numbers \(m \ge N\) one has
Fix a parameter \(p\) with \(0 \lt p \le 1\), positive integers \(w, s \gt 0\), and a tolerance \(\varepsilon \gt 0\). Then there exists \(N \in \mathbb {N}\) such that for every \(n \ge N\) with \(n \gt 0\) and every decidable event on restrictions of \(n\) variables, the following holds: if the fixed-size restriction probability satisfies
then the probability of the event under a Bernoulli(\(p\)) random restriction satisfies