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.

Random row splits leak repeated-group information

Example

There are $G \geq 2$ groups, each with two repeated rows $(g, Y_{g})$ , where $Y_{1}, \dots, Y_{G}$ are IID Bernoulli $(1 / 2)$ . Choose uniformly a balanced two-fold partition of the $2 G$ rows, independently of the labels. The learner memorizes the majority label for any group ID present in training (ties are resolved as zero) and predicts zero for a previously unseen ID. Use zero-one loss. This grouped design is not an IID row sample: the two rows in a group share a label and fixed group IDs.

Facts & Assumptions

Given: The repeated-group data, balanced random row partition, memorizing rule, and zero-one loss above. Compare the expected row-split score with prediction risk for a new group.

[F1]

Holdout, leave-out, V-fold, and repeated cross-validation: a K-fold schedule trains on each fold's complement and weights held-out rows equally when folds have equal size.

[F2]

Identical distribution and IID families: IID requires mutual independence; repeated rows sharing $Y_{g}$ violate this row-level condition.

[F3]

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials: For $p \in [0, 1]$ , a Bernoulli $(p)$ random variable takes the value $1$ with probability $p$ and $0$ with probability $1 - p$ .

Verification

1.1givenF1

For a fixed group $g$ , if its two rows fall in different folds, then each validation row's group ID appears in training and its memorized prediction is $Y_{g}$ , so both losses are zero. If both rows fall in one fold, neither is in the training set for that fold; both losses are $Y_{g}$ . Therefore the full row-split score is ${\hat{R}}_{r o w} = G^{- 1} \sum_{g = 1}^{G} Y_{g} 1 {the two rows of g share a fold}$ .

1.2givenalgebra

In a uniformly chosen balanced partition, the probability both rows of a fixed group lie in fold 1 is $(\binom{2 G - 2}{G - 2}) / (\binom{2 G}{G}) = (G - 1) / (2 (2 G - 1))$ ; the same probability holds for fold 2. Thus the probability they share a fold is $(G - 1) / (2 G - 1)$ .

2.1F2F3step 1.1step 1.2algebra

The split is independent of $Y_{g}$ , and [F3] gives $E Y_{g} = 1 / 2$ , so step 1.1 and the probability in step 1.2 give $E {\hat{R}}_{r o w} = (G - 1) / (2 (2 G - 1)) < 1 / 2$ . For a new group ID no training row has that ID, so the learner predicts zero and its error probability is $P (Y_{n e w} = 1) = 1 / 2$ . Row-split CV is therefore estimating an easier within-group prediction target than new-group prediction.

3.1F2F3step 2.1∎

The example violates the independent-row premise in [F2], so it is a warning about choosing the resampling unit to match deployment; it is not a counterexample to the IID risk identity.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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

Sylvain Arlot and Alain Celisse, A survey of cross-validation procedures for model selection, §8.3 (standard reference, not scraped)
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani, An Introduction to Statistical Learning, 7th printing, Chapter 5 §5.1 (standard reference, not scraped)