LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

A Bernoulli two-point testing lower bound

Statement

For $0 < u < 1$ , let $P_{-}$ and $P_{+}$ be the Bernoulli laws on ${0, 1}$ with success probabilities $(1 - u) / 2$ and $(1 + u) / 2$ . For an integer $k \geq 1$ , a randomized test is a function $ψ : {0, 1}^{k} \to [0, 1]$ , interpreted as the probability of deciding $+$ . Its equal-prior average error is $e_{k} (ψ) : = \frac{1}{2} (E_{P_{-}^{k}} ψ + E_{P_{+}^{k}} (1 - ψ)) .$ For finite probability laws $Q, R$ on a common finite set, define $aff (Q, R) : = \sum_{ω} \sqrt{Q (ω) R (ω)}$ and $TV (Q, R) : = \frac{1}{2} \sum_{ω} ∣ Q (ω) - R (ω) ∣$ . Set $Φ (t, u) : = \frac{1}{4} (1 - \sqrt{1 - \exp (- \frac{t u^{2}}{1 - u^{2}})}) (t \geq 0) .$ Then every such test satisfies $e_{k} (ψ) \geq \frac{1}{2} (1 - \sqrt{1 - (1 - u^{2})^{k}}) \geq 2 Φ (2 ⌈ k / 2 ⌉, u) .$ With no observations ( $k = 0$ ), every equal-prior test has average error exactly $1 / 2$ .

Statement references

Mohri et al., Foundations of Machine Learning, 2nd ed., Lemma 3.21 and Exercise D.3

Shalev-Shwartz and Ben-David, an independent two-point testing treatment with different hypotheses and constants, §28.2.1

Facts & Assumptions

Given: $0 < u < 1$ , the stated Bernoulli laws, and a randomized test $ψ$ .

[A1]

The sign has prior probability $1 / 2$ for each value, and $ψ (s) \in [0, 1]$ is the conditional probability of deciding $+$ after observing sample $s$ .

Proof

1.1A1algebra

For any randomized test, its average error is at least $(1 - TV (P_{-}^{k}, P_{+}^{k})) / 2$ : writing the two error expectations over the common finite sample space gives $e_{k} (ψ) = \frac{1}{2} (1 - \sum_{ω} ψ (ω) (P_{+}^{k} (ω) - P_{-}^{k} (ω)))$ . Each $ψ (ω) \in [0, 1]$ makes the signed sum at most the sum of the positive differences; these differences sum to $\frac{1}{2} \sum_{ω} ∣ P_{+}^{k} (ω) - P_{-}^{k} (ω) ∣$ because their total signed sum is zero. This is $TV (P_{-}^{k}, P_{+}^{k})$ by the definition in the statement.

2.1A1algebrastep 1.1

For any finite laws $Q, R$ , write $∣ Q (ω) - R (ω) ∣ = ∣ \sqrt{Q} - \sqrt{R} ∣ (\sqrt{Q} + \sqrt{R})$ . The finite Cauchy–Schwarz inequality follows by expanding $\sum_{i} (a_{i} - λ b_{i})^{2} \geq 0$ with $λ = (\sum_{i} a_{i} b_{i}) / (\sum_{i} b_{i}^{2})$ when the denominator is positive, and is immediate when it is zero. Apply it to $a_{ω} = ∣ \sqrt{Q (ω)} - \sqrt{R (ω)} ∣$ and $b_{ω} = \sqrt{Q (ω)} + \sqrt{R (ω)}$ to obtain $TV (Q, R)^{2} \leq \frac{1}{4} (\sum_{ω} (\sqrt{Q} - \sqrt{R})^{2}) (\sum_{ω} (\sqrt{Q} + \sqrt{R})^{2}) = 1 - aff (Q, R)^{2}$ . Thus $e_{k} (ψ) \geq \frac{1}{2} (1 - \sqrt{1 - aff (P_{-}^{k}, P_{+}^{k})^{2}})$ .

3.1A1algebrastep 2.1

The single-observation affinity is $2 \sqrt{(1 - u^{2}) / 4} = \sqrt{1 - u^{2}}$ . Finite product distributivity makes the $k$ -observation affinity its $k$ th power, $(1 - u^{2})^{k / 2}$ ; substituting gives the first displayed lower bound.

4.1A1algebrastep 3.1

For $0 \leq x < 1$ , $g (x) = \log (1 - x) + x / (1 - x)$ satisfies $g (0) = 0$ and $g^{'} (x) = x / (1 - x)^{2} \geq 0$ , so $(1 - u^{2})^{k} \geq \exp (- k u^{2} / (1 - u^{2}))$ . Since $2 ⌈ k / 2 ⌉ \geq k$ , the exponential with exponent $- k u^{2} / (1 - u^{2})$ is at least the one with exponent $- 2 ⌈ k / 2 ⌉ u^{2} / (1 - u^{2})$ . The map $s \mapsto 1 - \sqrt{1 - s}$ is increasing on $[0, 1]$ , so the first lower bound is at least $2 Φ (2 ⌈ k / 2 ⌉, u)$ .

5.1A1algebra∎

With no observations the test's decision distribution is the same under both signs, so its equal-prior error is $\frac{1}{2} (q + (1 - q)) = \frac{1}{2}$ for its probability $q$ of deciding $+$ .

Used by

One-sample Bernoulli two-point testing Example
An agnostic VC minimax lower bound Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Chapter 3 §3.4, Lemma 3.21 (standard reference, not scraped)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning, Chapter 28 §28.2.1 (standard reference, not scraped)