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 lower-tail bound from a bounded mean

Statement

On any probability space, if a random variable $Z$ satisfies $0 \leq Z \leq 1$ almost surely and $0 \leq t < 1$ , then $\Pr {Z > t} \geq \frac{E Z - t}{1 - t} .$

Statement references

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

Facts & Assumptions

Given: A random variable $Z \in [0, 1]$ almost surely and a real number $t \in [0, 1)$ .

[A1]

The probability and expectation are taken with respect to the given probability measure.

Proof

1.1A1algebra

Splitting the expectation on ${Z \leq t}$ and ${Z > t}$ and using $Z \leq t$ on the first event and $Z \leq 1$ on the second gives $E Z \leq t \Pr {Z \leq t} + \Pr {Z > t} = t + (1 - t) \Pr {Z > t}$ .

2.1A1step 1.1algebra∎

Since $1 - t > 0$ , rearranging the inequality in step 1.1 gives $\Pr {Z > t} \geq (E Z - t) / (1 - t)$ .

Used by

A realizable VC minimax lower bound Theorem
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.22 (standard reference, not scraped)