TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge 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.

McDiarmid bounded-differences inequality

Statement

Assume AC. Let $n \geq 1$ , let $Z_{i} : (Ω, F, P) \to (S_{i}, Σ_{i})$ be independent random elements, meaning measurable maps (Random elements and real random variables), with laws $μ_{i}$ given by pushforward (Law or distribution of a random element). Put $μ = ⨂_{i = 1}^{n} μ_{i}$ on the finite product sigma-algebra (The product sigma-algebra and its finite iterates). Let $f : \prod_{i = 1}^{n} S_{i} \to R$ be product-measurable with $\int ∣ f ∣ d μ < \infty$ . Suppose finite deterministic constants $c_{i} \geq 0$ satisfy $∣ f (z_{1}, \dots, z_{i}, \dots, z_{n}) - f (z_{1}, \dots, z_{i}^{'}, \dots, z_{n}) ∣ \leq c_{i}$ for every fixed setting of the other coordinates and every $z_{i}, z_{i}^{'}$ . The independent product-law theorem identifies the law of $Z = (Z_{1}, \dots, Z_{n})$ as $μ$ . Applying change of variables for expectation first to $∣ f ∣$ and then to $f$ makes $f (Z)$ integrable and gives $E f (Z) = \int f d μ$ . Put $V = \sum_{i = 1}^{n} c_{i}^{2}$ . For $t > 0$ , if $V > 0$ then $P (f (Z_{1}, \dots, Z_{n}) - E f (Z_{1}, \dots, Z_{n}) \geq t) \leq \exp ⁣ (- \frac{2 t^{2}}{V}),$ and if $V = 0$ this probability is $0$ . The same bound holds for the lower tail, so the two-sided probability is at most $2 e^{- 2 t^{2} / V}$ when $V > 0$ .

Facts & Assumptions

Given: AC, independent random elements $Z_{i}$ , an integrable measurable real function of them, and the deterministic coordinate oscillation bounds in the Statement.

[A1]

Assume AC, the Axiom of Choice. It is used for the conditional-expectation and conditional-Hoeffding suppliers (The Axiom of Choice).

[F1]

The product-integral construction gives integrable adapted $M_{i}$ , with $M_{n} = f (Z)$ , $M_{0} = \int f d μ$ , event-integral-zero differences, and predictable endpoints of width at most $c_{i}$ (Doob differences inherit coordinate oscillation widths).

[F2]

Conditional expectation is the almost-sure class of integrable measurable versions satisfying all event-integral identities (Conditional expectation as an ae class).

[F3]

Under AC, an integrable adapted process is a martingale when $E [M_{i} ∣ F_{i - 1}] = M_{i - 1}$ almost surely (Martingale submartingale and supermartingale).

[F4]

If a martingale difference has predictable finite endpoints of deterministic width $c_{i}$ , its conditional exponential moment is at most $e^{λ^{2} c_{i}^{2} / 8}$ (Conditional Hoeffding bound for bounded martingale differences).

[F5]

Conditional expectation preserves the unconditional expectation (Basic algebra and order properties of conditional expectation).

[F6]

A bounded measurable factor known under $F_{i - 1}$ can be taken outside conditional expectation (Taking out what is known).

[F7]

For $Y \geq 0$ and $r > 0$ , $P (Y \geq r) \leq E [Y] / r$ (Markov's inequality for random variables).

[F8]

Probability is subadditive on finite unions (Basic identities for a probability measure).

[F9]

The joint law of independent random elements is the product of their marginal laws; for measurable $f$ with $\int ∣ f ∣ d μ < \infty$ , change of variables applied to $∣ f ∣$ gives $f (Z) \in L^{1}$ and applied to $f$ gives $E f (Z) = \int f d μ$ (Independent random elements have product joint law, Change of variables for expectation).

[F10]

The real exponential is continuous and strictly increasing, positive, and satisfies $e^{- x} = 1 / e^{x}$ and $e^{x + y} = e^{x} e^{y}$ (The exponential function is strictly increasing, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ ).

[F11]

Every closed bounded interval $[a, b]$ with $a \leq b$ is compact (Heine-Borel by bisection: every closed bounded interval $[a, b]$ is compact).

[F12]

A continuous real function is bounded on a compact subset of $R$ (A continuous real function on a compact subset of $R$ is bounded).

Proof

1.1A1F1F2F3F9given

By [F9], the joint law of $Z = (Z_{1}, \dots, Z_{n})$ is $μ$ , so the product integral in the statement is $E f (Z)$ . By [F1], take the product-integral sequence $M_{i}$ and its differences $D_{i} = M_{i} - M_{i - 1}$ . For every $A \in F_{i - 1}$ , [F1] gives $\int_{A} M_{i} d P = \int_{A} M_{i - 1} d P$ . By [F2] and AC, $M_{i - 1}$ is a version of $E [M_{i} ∣ F_{i - 1}]$ , so [F3] makes $(M_{i}, F_{i})$ a martingale. The same lemma gives finite predictable endpoints $A_{i} \leq D_{i} \leq B_{i}$ with $A_{i} \leq 0 \leq B_{i}$ and $B_{i} - A_{i} \leq c_{i}$ .

2.1A1F1F2F4step 1.1

The event-integral identity of [F1] and [F2] give $E [D_{i} ∣ F_{i - 1}] = 0$ . Applying [F4] to these martingale differences and their endpoints gives $E [e^{λ D_{i}} ∣ F_{i - 1}] \leq e^{λ^{2} c_{i}^{2} / 8}$ for every real $λ$ . Since the endpoints contain zero and have width at most $c_{i}$ , $∣ D_{i} ∣ \leq c_{i}$ almost surely.

3.1F5F6F10F11F12step 2.1algebraconstruct

Put $S_{k} = M_{k} - M_{0} = \sum_{i = 1}^{k} D_{i}$ and $S_{0} = 0$ . Step 2.1 bounds each difference by $c_{i}$ , hence $S_{k - 1} \in [- C, C]$ for $C : = \sum_{i < k} c_{i}$ . This closed bounded interval is compact by [F11], and $x \mapsto e^{λ x}$ is continuous by [F10] and continuity of scalar multiplication, so [F12] makes $e^{λ S_{k - 1}}$ bounded. Also $x \mapsto e^{λ x}$ is Borel: its open-set preimages are open, and the class of Borel sets whose preimages are Borel is a sigma-algebra containing the opens, hence contains the Borel sigma-algebra (The Borel sigma-algebra of a topological space). For each Borel $B$ , the preimage of $B$ under $e^{λ S_{k - 1}}$ is $S_{k - 1}^{- 1} ((x \mapsto e^{λ x})^{- 1} (B))$ , so this factor is $F_{k - 1}$ -measurable. By the addition formula in [F10], $e^{λ S_{k}} = e^{λ S_{k - 1}} e^{λ D_{k}}$ ; conditional expectation preservation [F5] and taking out the known factor [F6] give $E e^{λ S_{k}} \leq e^{λ^{2} c_{k}^{2} / 8} E e^{λ S_{k - 1}}$ . Finite induction yields $E e^{λ S_{n}} \leq e^{λ^{2} V / 8}$ .

4.1F7F10step 2.1step 3.1algebra

If $V = 0$ , all $c_{i} = 0$ , so step 2.1 gives $D_{i} = 0$ almost surely and $S_{n} = 0$ . If $V > 0$ and $λ > 0$ , then $e^{λ S_{n}}$ is nonnegative and $S_{n} \geq t$ implies $e^{λ S_{n}} \geq e^{λ t} > 0$ by [F10]. Markov [F7] and step 3.1 give $P (S_{n} \geq t) \leq e^{λ^{2} V / 8} / e^{λ t} = e^{- λ t + λ^{2} V / 8}$ by the reciprocal and addition formulas in [F10]. Choosing $λ = 4 t / V$ gives the stated upper-tail bound.

5.1A1F8step 4.1algebra∎

Apply the same argument to $- f$ for the lower-tail bound. For $V > 0$ , [F8] combines the two tails; step 4.1 handles $V = 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

100 results within two dependency steps 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

John Duchi, Lecture Notes on Statistics and Information Theory, Chapter 4, §4.2.2, Proposition 4.2.5 (standard reference, not scraped)
Colin McDiarmid, On the Method of Bounded Differences, Surveys in Combinatorics 1989, §1 (standard reference, not scraped)