LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Mixture coupling for permuted two-sample U-statistics

Statement

Use the setup of Two-sample order-r U-statistic and first projections with fixed $r$ , $m + n = N$ , and $m / N \to p \in (0, 1)$ . Assume $h$ is symmetric within each block and antisymmetric under exchange of its two blocks. For every assignment of independent P- and Q-distributed arguments to its $2 r$ positions, assume $E h^{2} < \infty$ .

Let ${\overset{ˉ}{P}}_{N} = (m / N) P + (n / N) Q$ . Couple an IID row from ${\overset{ˉ}{P}}_{N}$ to the original labelled sample by drawing mixture labels and matching observations until one labelled group is exhausted, then drawing fresh observations for the remaining labels. Reorder the coupled row to agree with the original $P^{m} Q^{n}$ ordering except at $D$ unmatched positions. For a uniform permutation $π$ independent of this coupling,

$\sqrt{m} (U_{m, n} (Z^{π}) - U_{m, n} ({\overset{ˉ}{Z}}^{π π_{0}})) ⟶ 0 in L^{2} .$

Neither the weak null nor assignment-wise kernel centering is needed for this coupling bound. No rate for $m / N - p$ is assumed.

Facts & Assumptions

Given: Fixed order, proportional sample sizes, a block-symmetric and block-antisymmetric kernel, all mixed second moments finite, and the exact triangular mixture.

[F1]

Two-sample order-r U-statistic and first projections defines the kernel average $U_{m, n}$ over $M = (\binom{m}{r}) (\binom{n}{r})$ pairs of subsets.

[F2]

Identical distribution and IID families defines the IID convention used for each source group and the constructed mixture row.

[F3]

Moments, variance, and covariance on a probability space defines variance and covariance.

[F4]

Cauchy-Schwarz inequality for $L^{2}$ bounds expected absolute deviations and yields the triangle inequality for $L^{2}$ norms.

[F5]

Independent random elements defines independence of random elements. The source groups are independent by hypothesis; independence of the auxiliary draws and permutation is imposed by the product construction [F6].

[F6]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique constructs the finite product of these laws.

[F7]

The uniform probability space on a nonempty finite set gives uniform permutations and finite conditional averaging.

[F8]

A successive-revelation variance bound for a uniform permutation bounds a permutation function's variance by half the sum of its successive-revelation averaged squared transposition differences.

[A1]

$B = \max_{η \in {P, Q}^{2 r}} E_{η} h^{2} < \infty$ by the finite family of moment assumptions.

Proof

Given: The hypotheses in the Statement. Prove the $L^{2}$ coupling bound.

1.1F2F5F6F7givenconstruct

Enlarge the source sample space by the finite product [F6] with $N$ Bernoulli $(p_{N})$ label factors, $N$ fresh P-draw factors, $N$ fresh Q-draw factors, and one uniform permutation factor [F7], where $p_{N} = m / N$ . Its rectangle formula makes all auxiliary factors mutually independent and independent of the source samples, in the sense of [F5]. Match each P label to the next unused original X and each Q label to the next unused original Y, using distinct fresh draws of the requested law after exhaustion. Conditional on the labels the constructed coordinates are independent with their respective label laws, so their unconditioned row $\overset{ˉ}{Z}$ is IID ${\overset{ˉ}{P}}_{N}$ . Align every shared observation with its original position, putting the fresh observations in the remaining positions by a fixed index order; call the resulting array $\tilde{Z} = {\overset{ˉ}{Z}}^{π_{0}}$ . With $B_{N}$ the number of P labels, its mismatch set $J$ has size $D = ∣ B_{N} - m ∣$ . Conditional on the labels and alignment, the pairs $(Z_{i}, {\tilde{Z}}_{i})$ are independent across $i$ ; at a shared position both entries coincide, and at a mismatch the original and fresh entries are independent.

1.2F1F7givenalgebra

For any deterministic array $a$ of length $N$ , the permutation average of $U_{m, n} (a^{π})$ is zero: the arguments of a fixed selected kernel term form a uniform ordered distinct $2 r$ -tuple, and exchanging its two r-blocks preserves that distribution and negates the kernel. Therefore $f (π) : = U_{m, n} (Z^{π}) - U_{m, n} ({\tilde{Z}}^{π})$ has permutation mean zero for every realized pair of arrays. This is conditional centering of the full statistic, not centering of each mixed-assignment kernel.

2.1F1F3F4step 1.1algebra

Since $B_{N}$ is binomial with parameters $N, p_{N}$ , $E B_{N} = m$ and $E D^{2} = N p_{N} (1 - p_{N}) \leq N / 4$ . Thus $E D \leq \sqrt{E D^{2}} = O (\sqrt{N})$ by [F4]. Also $m, n ≍ N$ and $M ≍ N^{2 r}$ . Constants below depend only on $r$ and bounds keeping $p_{N}$ away from $0, 1$ , not on the labels or values.

3.1A1F1F4step 1.1step 2.1algebra

Fix two positions $k, l$ and a permutation $π$ , conditioning on labels and alignment. A selected term in $U (a^{π}) - U (a^{π (k, l)})$ vanishes unless its subset pair meets ${k, l}$ ; there are at most $C N^{2 r - 1}$ such pairs. Each term in $f (π) - f (π (k, l))$ is a signed sum of four kernel evaluations, each on distinct independent population coordinates and hence with conditional second moment at most $B$ by [A1]. The $L^{2}$ triangle inequality [F4], followed by division by $M$ , bounds the norm of this difference by $C \sqrt{B} / N$ . If neither $π (k)$ nor $π (l)$ is in $J$ , a contribution also vanishes unless its selected positions meet $π^{- 1} J$ outside ${k, l}$ . There are at most $C D N^{2 r - 2}$ such pairs, giving the sharper norm bound $C \sqrt{B} D / N^{2}$ . Overlap among evaluations causes no independence requirement for this triangle inequality.

4.1F7F8step 1.2step 3.1algebra

Averaging the squared bounds in step 3.1 over uniform $π$ , the probability that either swapped entry is a mismatch is at most $2 D / N$ . Thus, for every fixed position transposition, $E_{π, v a l u e s} [(f (π) - f (π (k, l)))^{2} ∣ l a b e l s] \leq C B (D / N^{3} + D^{2} / N^{4})$ . First apply [F8] for fixed realized arrays, where its expectations and variance are only over $π$ , and then average over values conditional on labels. Its sum of inner-average coefficients is $N / 2$ . By step 1.2 the conditional permutation mean is identically zero, so $E_{π, v a l u e s} [f (π)^{2} ∣ l a b e l s] \leq C B (D / N^{2} + D^{2} / N^{3})$ .

5.1step 2.1step 4.1algebra∎

Averaging step 4.1 over labels and using $m ≍ N$ and step 2.1 yields $E [m f (π)^{2}] \leq C B (E D / N + E D^{2} / N^{2}) = O (N^{- 1 / 2}) \to 0$ . Since ${\tilde{Z}}^{π} = {\overset{ˉ}{Z}}^{π π_{0}}$ with the alignment convention in the Statement, this is the required $L^{2}$ convergence.

Remarks

The 2011 report's Lemma A.1 uses assignment-wise zero means and a fixed-mixture fraction rate. The local proof instead centers the complete statistic by antisymmetry, controls its permutation variance by transpositions, and uses the exact triangular mixture. It does not assert those extra hypotheses follow from the weak null.

Depends on

Used by

Permutation CLT for a two-sample U-statistic under a weak null Theorem

Dependency tree · two levels

37 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

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.1 and Appendix A, Lemma A.1 (standard reference, not scraped)