Skip to main content
PathsFinite union bound

Theorem trail

Finite union bound

The subadditivity step behind finite-class learning bounds.

Open topicExplore AtlasClaim evidenceEvidence panel

Record

Research Record

A compact audit view for the theorem before the full source, proof, diagnostic, and failure-mode sections.

Claim scope
theorem
Evidence level
Exact Lean wrapper
Source precision
reviewed / B
Diagnostics
1 item
Exercises
2 exercises
Failure checks
2 checks
Open Atlas traceOpen evidence recordJump to sourcesJump to failures

Theorem Statement

For any finite family of events ,

Assumptions

  • P is a probability measure
  • The index set is finite
  • The indexed sets are events

Proof Sketch

Reduce a finite union to a sum of indicators, or prove finite subadditivity by induction from the two-event case. Overlap only makes the sum larger than the true union probability, which is why no independence assumption is required.

Proof Obligations

Finite event family in one probability space

assumption

Verify every event belongs to the same sigma-algebra and the index set is finite before using the finite union-bound statement.

Mixing events from different spaces or silently moving to an infinite family changes the theorem being applied.

Overlap is paid for by subadditivity

proof step

The core proof step is that overlap can only make the union probability smaller than the sum of individual probabilities.

Multiplying probabilities or assuming disjointness introduces an unnecessary and often false independence-style condition.

Union price is additive before logarithms appear

boundary

In finite-class learning bounds the union bound first adds failure probabilities; the log |H| term appears only after solving the tail inequality.

Skipping this accounting hides exactly where model-class size enters the sample-complexity bound.

No independence discount is available

boundary

The finite union bound does not use independence, so it also does not provide any product-probability improvement when events happen to be independent.

Replacing the union-bound sum by a product or disjoint-event calculation can understate the probability of the bad event.

Source Locators

Probability and Measure (1995)

proof

Chapter 1 — Probability measure foundations

billingsley-1995:ch1

kind
chapter
review
reviewed / B
extract
manual

Chapter-level support for finite subadditivity and union bounds for probability measures.

Probability: Theory and Examples (2019)

background

Chapter 1 — Measure theory background for probability

durrett-2019:ch1

kind
chapter
review
reviewed / B
extract
manual

Measure-theoretic probability background for subadditivity and finite unions.

Probability and Measure (1995)

proof

Pages 24-25 — Boole's inequality and countable subadditivity

billingsley-1995:pg24

kind
page_range
review
reviewed / B
extract
manual
pages
24-25

Anchor: Boole's inequality; countable subadditivity

Reviewed page-range support for Boole inequality and finite subadditivity.

Curated Trace

  1. 1
    Probability measurefoundation

    Subadditivity is a measure property before it is a learning-theory trick.

    Checkpoint

    The indexed sets must be events in the same sigma-algebra.

  2. 2
    Finite subadditivitymeasure step

    The union bound is finite subadditivity specialized to probability.

    Checkpoint

    Do not multiply probabilities; overlap is allowed.

  3. 3
    Finite union boundtheorem

    A bad event over many candidates is bounded by the sum of candidate failures.

    Checkpoint

    The price of many candidates is additive in probability.

  4. 4
    Finite-class proofdownstream

    Union bounding Hoeffding failures over H introduces log |H| after rearrangement.

    Checkpoint

    Find exactly where the finite class assumption enters.

Failure Modes

Union price is additive before logarithms appear

In finite-class learning bounds the union bound first adds failure probabilities; the log |H| term appears only after solving the tail inequality.

Risk: Skipping this accounting hides exactly where model-class size enters the sample-complexity bound.

Check: In finite-class learning bounds the union bound first adds failure probabilities; the log |H| term appears only after solving the tail inequality.

No independence discount is available

The finite union bound does not use independence, so it also does not provide any product-probability improvement when events happen to be independent.

Risk: Replacing the union-bound sum by a product or disjoint-event calculation can understate the probability of the bad event.

Check: The finite union bound does not use independence, so it also does not provide any product-probability improvement when events happen to be independent.