LemmaStatement: Literature-sourcedProof: 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.

Two-sample Hoeffding decomposition

Statement

In the setup of Two-sample order-r U-statistic and first projections, assume $h \in L^{2} (P^{\otimes r} \otimes Q^{\otimes r})$ . For each $X$ -coordinate $u$ let $P_{u}$ integrate that coordinate under $P$ ; for each $Y$ -coordinate let $P_{u}$ integrate under $Q$ , and put $Q_{u} = I - P_{u}$ . These coordinate operators commute on $h$ by Fubini. For $0 \leq a, b \leq r$ , choose any $a$ of the $X$ -coordinates and any $b$ of the $Y$ -coordinates, apply $Q_{u}$ in those coordinates and $P_{u}$ in all others, and call the resulting (reindexed) kernel $h_{a, b}$ . Separate block symmetry makes it independent of the chosen coordinate subsets. It is canonical in each of its $a + b$ arguments: integrating it in any such argument gives zero. Let $U_{a, b} (h_{a, b})$ be its average over all $a$ -subsets of the $X$ sample and all $b$ -subsets of the $Y$ sample, with the zero-order convention $U_{0, 0} = θ (P, Q; h)$ . Then

$U_{m, n} - θ (P, Q; h) = \sum_{\begin{array}{c} 0 \leq a, b \leq r \\ a + b \geq 1 \end{array}} (\binom{r}{a}) (\binom{r}{b}) U_{a, b} (h_{a, b}) .$

In particular,

$U_{m, n} - θ (P, Q; h) = \frac{r}{m} \sum_{i = 1}^{m} g_{X} (X_{i}) + \frac{r}{n} \sum_{j = 1}^{n} g_{Y} (Y_{j}) + R_{m, n},$

where $R_{m, n}$ is the sum of the terms with $a + b \geq 2$ .

Facts & Assumptions

Given: Independent IID samples from $P$ and $Q$ , a symmetric order- $(r, r)$ kernel with finite second moment, and the projection definitions.

[F1]

Two-sample order-r U-statistic and first projections defines $U_{m, n}$ , $g_{X}$ , and $g_{Y}$ .

[F2]

First projections are measurable and square-integrable supplies measurable square-integrable coordinate integrals and the Fubini equalities needed for each projection operator.

[F3]

Fubini's theorem for L^1 functions on a sigma-finite product permits the coordinate-integration operators on different coordinates to commute.

[F4]

Cauchy-Schwarz inequality for $L^{2}$ gives the $L^{2}$ contraction bound for integration over a probability coordinate.

Proof

Given: The hypotheses in the Statement. Prove the finite decomposition and identify its order-one terms.

1.1F2F3F4algebra

For each coordinate $u$ , Cauchy–Schwarz [F4] on its probability marginal and Fubini [F3] give $∥ P_{u} h ∥_{2} \leq ∥ h ∥_{2}$ . The pointwise inequality $∣ h - P_{u} h ∣^{2} \leq 2 ∣ h ∣^{2} + 2 ∣ P_{u} h ∣^{2}$ then gives $∥ Q_{u} h ∥_{2} \leq 2 ∥ h ∥_{2}$ . Thus every finite product of the coordinate operators is a well-defined $L^{2}$ class. The operator $P_{u}$ is idempotent because integrating an already coordinate-independent function changes nothing. For distinct coordinates $u, v$ , Fubini [F3] gives $P_{u} P_{v} = P_{v} P_{u}$ on each integrable section, so $P_{u}, Q_{u}$ commute across distinct coordinates.

2.1step 1.1algebra

Since $I = P_{u} + Q_{u}$ for every one of the $2 r$ coordinates, multiplying these finitely many identities and using commutativity expands $h$ as the sum over all subsets of coordinates of the corresponding products of $P_{u}$ and $Q_{u}$ . This is a finite algebraic expansion; its empty selected subset is $P_{1} \dots P_{2 r} h = θ (P, Q; h)$ .

3.1step 1.1step 2.1algebra

If coordinate $u$ is selected, applying $P_{u}$ to that component gives zero because $P_{u} Q_{u} = P_{u} - P_{u}^{2} = 0$ ; the other commuting factors do not alter this identity. Thus each component is canonical in each selected coordinate. Block symmetry identifies the $(\binom{r}{a}) (\binom{r}{b})$ components with $a$ selected $X$ -coordinates and $b$ selected $Y$ -coordinates as reindexed copies of $h_{a, b}$ .

4.1F1step 2.1step 3.1algebra

Apply the expansion in step 2.1 to each summand $h (X_{I}; Y_{J})$ in $U_{m, n}$ , summing over sample subsets and selected kernel coordinates together. Each fixed $a$ -subset of the $X$ sample is contained in exactly $(\binom{m - a}{r - a})$ sample $r$ -subsets; in each, exactly one choice of $a$ kernel coordinates selects it. Thus its coefficient after averaging is $(\binom{m - a}{r - a}) / (\binom{m}{r}) = (\binom{r}{a}) / (\binom{m}{a})$ . Similarly, each fixed $b$ -subset of the $Y$ sample has coefficient $(\binom{r}{b}) / (\binom{n}{b})$ . These identities also hold when $a = 0$ or $b = 0$ . Block symmetry identifies the resulting functions with $h_{a, b}$ , so the combined contribution is $(\binom{r}{a}) (\binom{r}{b}) U_{a, b} (h_{a, b})$ . Removing the constant component gives the first displayed decomposition.

5.1F1step 4.1algebra∎

For $(a, b) = (1, 0)$ , the integrated kernel is exactly $g_{X}$ from [F1], and its subset average is $m^{- 1} \sum_{i} g_{X} (X_{i})$ ; its coefficient is $(\binom{r}{1}) = r$ . For $(a, b) = (0, 1)$ the average is $n^{- 1} \sum_{j} g_{Y} (Y_{j})$ with the same coefficient $r$ . All remaining pairs have $a + b \geq 2$ and are, by definition, the remainder $R_{m, n}$ .

Depends on

Used by

Dependency tree · two levels

20 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

Péter Major, Some Results About U-statistics, in On the Estimation of Multiple Random Integrals and U-Statistics, Lecture Notes in Mathematics 2079, Theorem 9.1 and proof, printed pp. 77–78 (standard reference, not scraped)
E. Y. Chung and J. P. Romano, Asymptotically Valid and Exact Permutation Tests Based on Two-Sample U-Statistics, Stanford Technical Report 2011-09, §3.2 (standard reference, not scraped)