TheoremStatement: AI-adaptedProof: AI-generatedPipeline-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.

Almost-sure limiting risk of an infinite random-forest classifier

Statement

Fix a finite training dataset and a classifier $h (x, θ)$ taking values in an ordered finite class set $C = {c_{1} < \dots < c_{J}}$ with $J \geq 2$ . Let $Θ_{1}, Θ_{2}, \dots$ be IID random elements of a measurable space $(T, T)$ with common law $Q$ . Regard the sequence as a random element of $(T^{N}, T^{\otimes N})$ and assume it is independent of a test pair $(X, Y)$ with law $P$ on $X \times C$ . Assume $h$ is jointly measurable in $(x, θ)$ . For $j \in {1, \dots, J}$ define $p_{j} (x) = Q {θ : h (x, θ) = c_{j}}$ , and let

m (x, y) = p_{k} (x) - \max_{j \neq k} p_{j} (x), y = c_{k} .

For each $B \geq 1$ , let $G_{B} (x)$ be the class with the largest number of votes among $h (x, Θ_{1}), \dots, h (x, Θ_{B})$ , choosing the least class index in a tie. Define the finite-forest conditional risk by

P E_{B} (Θ_{1 : B}) = \int_{X \times C} 1 {G_{B} (x) \neq y} d P (x, y) .

If $P {(x, y) : m (x, y) = 0} = 0$ , then, almost surely with respect to the IID tree-randomization sequence,

P E_{B} (Θ_{1 : B}) ⟶ P {(x, y) : m (x, y) < 0} .

Statement references

Breiman, “Random Forests,” Theorem 1.2 and Appendix I, printed pp. 7 and 29–30

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.2, printed pp. 587–593; used for the forest construction, not as a proof of this risk limit

Facts & Assumptions

Given: The fixed training data, measurable classifier and IID tree-randomization sequence, independent test pair, finite ordered class set, and zero-margin hypothesis in the Statement.

[F1]

Bagged random-forest construction on a fixed finite sample: Classification uses the class with the largest number of tree votes and the least class index for a tie.

[F2]

Identical distribution and IID families: IID means mutual independence together with identical laws; it includes no moment assumption.

[F3]

Measurable coordinatewise functions preserve independence: Applying the same measurable map to each member of an independent family preserves independence.

[F4]

Kolmogorov iid l1 strong law: For IID real random variables with finite first absolute moment, their sample averages converge almost surely to their common mean.

[F5]

Independent random elements have product joint law: The joint law of a finite independent family of random elements is the product of their marginal laws.

[F6]

Fubini's theorem for L^1 functions on a sigma-finite product: For an integrable function on a product of sigma-finite measure spaces, either order of iterated integration gives the product integral.

[F7]

Dominated convergence: Almost-everywhere convergence under a common integrable majorant implies convergence of the integrals.

[F8]

Expectation of a nonnegative or integrable random variable: Expectation on a probability space is integration against its probability measure.

Proof

1.1givenF2F3F4

Fix a test pair $(x, y)$ outside the zero-margin set. For each class $c_{j}$ , the variables $1 {h (x, Θ_{b}) = c_{j}}$ are identically distributed because they use the same measurable map on randomizations with common law, independent by [F3], and integrable because they are bounded by $1$ . Applying [F4] to each of the finitely many classes shows that every vote proportion converges almost surely to $p_{j} (x)$ .

2.1givenF1step 1.1algebra

On a sequence where those proportions converge, if $m (x, y) > 0$ , the true class has a strictly larger limiting vote proportion than each wrong class, so the finite forest eventually predicts $y$ . If $m (x, y) < 0$ , a wrong class attaining the finite maximum in the definition of $m$ has a strictly larger limiting proportion than $y$ , so the finite forest eventually predicts a wrong class. Thus the finite-forest error indicator converges almost surely in the randomizations to $1 {m (x, y) < 0}$ for $P$ -almost every test pair.

3.1givenF5F6step 2.1

The functions $p_{j} (x)$ are measurable by [F6] applied to the bounded jointly measurable indicators $1 {h (x, θ) = c_{j}}$ . Hence the error indicators and the limiting margin indicator are jointly measurable and bounded. Independence of the sequence-valued randomization and test pair lets [F5] give their product joint law. Applying [F6] to the indicator of the nonconvergence set and using step 2.1 shows that for almost every randomization sequence the error indicators converge for $P$ -almost every test pair.

4.1F7F8step 3.1algebra∎

For each such sequence, the error indicators are dominated by the integrable constant $1$ on the probability space $(X \times C, P)$ . By [F7] their integrals converge to the integral of $1 {m < 0}$ , which by [F8] is $P {m < 0}$ . These integrals are exactly $P E_{B} (Θ_{1 : B})$ , proving the claimed limit.

Depends on

Used by

A zero-margin bootstrap forest need not approach strict-margin risk Example

Dependency tree · two levels

34 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

Leo Breiman, "Random Forests," Machine Learning 45 (2001), 5–32; full text hosted by the University of Chicago Macro Finance Research Program (standard reference, not scraped)
Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., corrected 12th printing, Chapter 15 (standard reference, not scraped)