ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

One-sample Bernoulli two-point testing

Example

Take $u = 1 / 2$ and one observation, so $P_{-} = Bern (1 / 4)$ and $P_{+} = Bern (3 / 4)$ . The deterministic test $ψ (y) = y$ has equal-prior error $1 / 4$ , and this error is minimal among all randomized tests.

Example references

Mohri et al., Foundations of Machine Learning, 2nd ed., Lemma 3.21

Shalev-Shwartz and Ben-David, Understanding Machine Learning, §28.2.1

Facts & Assumptions

Given: The two laws $P_{-}$ and $P_{+}$ on ${0, 1}$ , equal prior probabilities, and the test convention that $ψ (y)$ is the probability of deciding $+$ .

[F1]

The equal-prior average error $e_{k} (ψ)$ is the half-sum of the two conditional error probabilities A Bernoulli two-point testing lower bound.

Verification

1.1givenalgebra

Here $P_{-} (0) = 3 / 4$ , $P_{-} (1) = 1 / 4$ , $P_{+} (0) = 1 / 4$ , and $P_{+} (1) = 3 / 4$ . The test $ψ (y) = y$ has error $\frac{1}{2} (P_{-} (1) + P_{+} (0)) = \frac{1}{4}$ .

2.1givenF1algebra∎

For any randomized test $ψ$ , direct expansion gives $e_{1} (ψ) = \frac{1}{2} + \frac{1}{4} (ψ (0) - ψ (1)) \geq \frac{1}{4}$ , since $ψ (0) \geq 0$ and $ψ (1) \leq 1$ . The deterministic test attains this lower bound.

Depends on

A Bernoulli two-point testing lower bound

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

1 result within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

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