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

An out-of-bag prediction can differ from the full finite forest

Example

Take the classification sample $D = ((0, 0), (1, 1))$ with ordered labels $0 < 1$ , grow depth-zero trees, and use $B = 2$ bootstrap trees. A tree is out of bag for observation $1$ exactly when its bootstrap count for training index $1$ is zero. On the event that the first bootstrap count vector is $(2, 0)$ and the second is $(0, 2)$ , the full forest receives one vote for each class and predicts $0$ by the least-index tie rule. The out-of-bag set for observation $1$ is then ${2}$ , so its out-of-bag prediction is $1$ . This event has probability $1 / 16$ , and it exhibits a finite-forest out-of-bag prediction that differs from the full finite-forest prediction.

Example references

Bootstrap counts, class ties, and out-of-bag predictions

Classification leaf predictions

Breiman, “Random Forests,” §3.1 and Appendix II, printed pp. 11 and 31–32

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.3.1, printed pp. 592–593

Facts & Assumptions

Given: Two independent size- $2$ bootstrap samples drawn uniformly with replacement from the two-observation training sample, with depth cap zero and the class tie rule in the Example.

[F1]

Bagged random-forest construction on a fixed finite sample: The out-of-bag set for observation $i$ consists exactly of tree indices $b$ with $N_{b i} = 0$ , and no prediction is returned when this set is empty.

[F2]

Empirical axis-aligned binary decision trees: A classification leaf predicts the most frequent class, choosing the least class index in a tie.

[F3]

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.

Verification

1.1givenF1F3algebra

Each tree draws two independent uniform indices from ${1, 2}$ . The probability of counts $(2, 0)$ for tree $1$ is $1 / 4$ , and the probability of counts $(0, 2)$ for tree $2$ is $1 / 4$ . Independence of the two trees gives probability $(1 / 4) (1 / 4) = 1 / 16$ for the stated event.

2.1givenF2step 1.1

With depth cap zero, each tree is a single leaf. Its bootstrap sample contains only label $0$ for counts $(2, 0)$ and only label $1$ for counts $(0, 2)$ , so [F2] gives predictions $0$ and $1$ , respectively.

3.1F1step 1.1step 2.1algebra∎

The full forest has one vote for each class, so its least-index tie rule returns $0$ . For observation $1$ , the first tree has $N_{11} = 2$ and is excluded from the out-of-bag set, while the second has $N_{21} = 0$ and is the only included tree; its prediction is $1$ . The two predictions differ on the positive-probability event from step 1.1.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

10 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, §15.3.1 (standard reference, not scraped)