LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedverified 2026-10-22 (gpt-6.1-sol)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Two-sided Hoeffding bound for Bernoulli frequencies

Statement

Let $n \geq 1$ , $p \in [0, 1]$ , and let $X_{1}, \dots, X_{n} : Ω \to {0, 1}$ be measurable on a probability space with $P (X_{1} = x_{1}, \dots, X_{n} = x_{n}) = \prod_{k = 1}^{n} b_{p} (x_{k}) for every (x_{1}, \dots, x_{n}) \in {0, 1}^{n} .$ Here $b_{p} (1) = p$ and $b_{p} (0) = 1 - p$ , including $p = 0$ and $p = 1$ . Thus the variables have the stated independent Bernoulli product law. For their frequency $f = n^{- 1} \sum_{k = 1}^{n} X_{k}$ and every $t > 0$ ,

P (∣ f - p ∣ \geq t) \leq 2 e^{- 2 n t^{2}} .

No axiom of choice is assumed.

Statement references

The Hoeffding MGF bound for a variable in a unit interval

Facts & Assumptions

Given: $n \geq 1$ , $p \in [0, 1]$ , and the finite Bernoulli product law in the Statement.

[A1]

For each tuple in ${0, 1}^{n}$ , its probability is the product of the one-coordinate probabilities $b_{p} (1) = p$ and $b_{p} (0) = 1 - p$ .

[F1]

The Hoeffding MGF bound for a variable in a unit interval: if $Y$ is measurable with $0 \leq Y \leq 1$ almost surely, then $E e^{λ (Y - E Y)} \leq e^{λ^{2} / 8}$ for every real $λ$ ; its proof does not assume choice.

Proof

1.1givenA1F1algebra

Summing the product law [A1] over the other $n - 1$ coordinates gives $P (X_{k} = 1) = p \prod_{j \neq k} (p + (1 - p)) = p$ , so $E X_{k} = p$ . Put $S = \sum_{k = 1}^{n} (X_{k} - p)$ . By [F1], $E e^{λ (X_{k} - p)} \leq e^{λ^{2} / 8}$ for every real $λ$ . Expanding the finite expectation over ${0, 1}^{n}$ and using [A1] factors it into the product of these $n$ expectations. Hence $E e^{λ S} \leq e^{n λ^{2} / 8}$ .

2.1givenA1step 1.1algebra

For $λ > 0$ , $S \geq n t$ implies $e^{λ S} \geq e^{λ n t}$ . For any nonnegative $W$ and $c > 0$ , $W \geq c 1_{{W \geq c}}$ , so $P (W \geq c) \leq E W / c$ . Apply this to $W = e^{λ S}$ and then step 1.1 to get $P (f - p \geq t) \leq e^{- λ n t + n λ^{2} / 8}$ . Setting $λ = 4 t$ gives $e^{- 2 n t^{2}}$ .

3.1step 2.1givenA1step 1.1algebra∎

Apply the same argument to $- S$ , using step 1.1 at $- 4 t$ ; it gives $P (p - f \geq t) \leq e^{- 2 n t^{2}}$ . The union bound follows from $1_{A \cup B} \leq 1_{A} + 1_{B}$ , so adding the two tails proves the claim. Endpoints $p = 0, 1$ are included by [A1]: then every $X_{k} = p$ almost surely and the left side is zero for $t > 0$ .

Depends on

The Hoeffding MGF bound for a variable in a unit interval

Dependency tree · 2 levels

Sources

Dmitry Panchenko, MIT OpenCourseWare 18.465, Lecture 07: Hoeffding’s inequality, Spring 2007