OctoInformBeta

OpenAI preprint, September 2026 · §2. Conventions and preliminary results · §2

Lemma 2.4: For a sum XX of independent {0,1}\{0,1\}-valued variables of equal mean, μ=𝔼X\mu = \mathbb{E}X: Pr⁡(X≤μ/2)≤e−μ/8\Pr(X \le \mu/2) \le e^{-\mu/8} and Pr⁡(X≥2μ)≤e−μ/3\Pr(X \ge 2\mu) \le e^{-\mu/3}

Chernoff bounds below half and above twice the mean.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Keep each vertex of a graph GG independently with probability pp, and fix a set ss of vertices. The number of kept vertices in ss is binomial with parameters |s||s| and pp, so its mean is p|s|p|s|, and an argument by random sampling needs that number to stay above half its mean and below twice it. The question is how unlikely a departure from that range is, as a function of the mean alone. Splitting the edges of GG at random and counting the edges of a fixed set that land on one side raises the same question.

The library states the Chernoff bounds for such a count twice, with the same hypotheses and the same conclusions: once for random vertex sampling and once for random edge splitting, each time as a lower tail bound and an upper tail bound.

The Claim

Theorem 1. Let (Xi)i∈I(X_i)_{i \in I} be independent random variables, each taking only the values 00 and 11 and each of mean pp, where p≥0p \ge 0. Let ss be a finite subset of II, and put X=∑i∈sXiX = \sum_{i \in s} X_i and μ=p|s|\mu = p|s|. In the version for vertex sampling, Pr⁡(X≤μ/2)≤e−μ/8\Pr\bigl(X \le \mu/2\bigr) \le e^{-\mu/8}(1)✦ and Pr⁡(X≥2μ)≤e−μ/3;\Pr\bigl(X \ge 2\mu\bigr) \le e^{-\mu/3};(2)✦ in the version for edge splitting, likewise Pr⁡(X≤μ/2)≤e−μ/8\Pr\bigl(X \le \mu/2\bigr) \le e^{-\mu/8}(3)✦ and Pr⁡(X≥2μ)≤e−μ/3.\Pr\bigl(X \ge 2\mu\bigr) \le e^{-\mu/3}.(4)✦

In the paper, the result reads: if XX is binomial with mean μ\mu, then Pr⁡(X≤μ/2)≤e−μ/8\Pr(X \le \mu/2) \le e^{-\mu/8} and Pr⁡(X≥2μ)≤e−μ/3\Pr(X \ge 2\mu) \le e^{-\mu/3}.

What Is Checked

The four bounds are stated over a family of independent random variables, each with values in {0,1}\{0,1\} and mean p≥0p \ge 0, a finite set ss of its indices, and the sum XX of the variables indexed by ss, whose mean is μ=p|s|\mu = p|s|.