# Much Two U About Nothing: Extension of U-statistics to multiple independent samples

Thank you very much to the lovely Feben Alemu for pointing me in the direction of https://pungenerator.org/ as a means of ensuring we never have to go without a brilliant title! With great power comes great responsibility.

## Review

Statistical functionals are any real-valued function of a distribution function , . When is unknown, nonparametric estimation only requires that belong to a broad class of distribution functions , typically subject only to mild restrictions such as continuity or existence of specific moments.

For a single independent and identically distributed random sample of size , , a statistical functional is said to belong to the family of expectation functionals if:

1. takes the form of an expectation of a function with respect to ,

2. is a symmetric kernel of degree .

A kernel is symmetric if its arguments can be permuted without changing its value. For example, if the degree , is symmetric if .

If is an expecation functional and the class of distribution functions is broad enough, an unbiased estimator of can always be constructed. This estimator is known as a U-statistic and takes the form,

such that is the average of evaluated at all distinct combinations of size from .

For more detail on expectation functionals and their estimators, check out my blog post U-, V-, and Dupree statistics.

Since each appears in more than one summand of , the central limit theorem cannot be used to derive the limiting distribution of as it is the sum of dependent terms. However, clever conditioning arguments can be used to show that is in fact asymptotically normal with mean

and variance

where

The sketch of the proof is as follows:

1. Express the variance of in terms of the covariance of its summands,

1. Recognize that if two terms share common elements such that,

conditioning on their shared elements will make the two terms independent.

2. For , define

such that

and

Note that when , and , and when , and .

3. Use the law of iterated expecation to demonstrate that

and re-express as the sum of the ,

Recognizing that the first variance term dominates for large , approximate as

4. Identify a surrogate that has the same mean and variance as but is the sum of independent terms,

so that the central limit may be used to show

5. Demonstrate that and converge in probability,

and thus have the same limiting distribution so that

For a walkthrough derivation of the limiting distribution of for a single sample, check out my blog post Getting to know U: the asymptotic distribution of a single U-statistic.

This blog post aims to provide an overview of the extension of kernels, expectation functionals, and the definition and distribution of U-statistics to multiple independent samples, with particular focus on the common two-sample scenario.

## Definitions for multiple independent samples

Consider independent random samples denoted

where is the size of the sample and is the total sample size. Let . Then, for multiple independent samples, a statistical functional is an expectation functional if

where the kernel is a function symmetric within each of the blocks of arguments , …, . That is, each block of arguments within can be permuted independently without changing the value of . By this definition, is an unbiased estimator of .

In the single sample case, we were able to permute all arguments of without impacting ‘s value as each was identically distributed and thus “exchangeable”. Here, all arguments are not identically distributed.

The first sample may be distributed according to , the second according to , and so on. We have not required that and so we cannot assume all arguments are exchangeable in the multiple sample scenario. Instead, we are restricted to permuting arguments within each sample.

Since we have assumed that the samples are independent, permuting one sample’s, or block’s, arguments should not impact the other blocks. Hence, our new block-based definition of a symmetric kernel.

Since is symmetric within each block of arguments, we can require

Then, from each of the independent samples, we require of the possible arguments, so that there are a total of

possible combinations of the arguments.

The U-statistic for independent samples is then defined analogously to that of a single sample,

so that is the average of evaluated at all independent combinations of the blocks’ arguments.

This notation got real ugly real fast but I promise that we will pretend that the two-sample case is the only important case soon enough.

## Asymptotic distribution

As you can imagine, the derivation of the asymptotic distribution of for multiple samples is a notational nightmare. As a result, I will provide a sketch of the required elements. The remainder of the proof follows the logic of that of a single sample.

The variance of can be expressed in terms of the covariance of its summands. We start, once again, by focusing on a single covariance term. To “simplify notation”, we consider

Let represent the number of elements common to the block of the two terms such that,

Conditioning on all common elements will make the two terms conditionally independent. Thus, we can define the multiple sample analogue to the single sample . For ,

and its variance as,

Expressing in terms of , it can be shown that

when all the variance components are finite and

Thus, the variance of is essentially the sum of the variance components obtained by conditioning on a single element within each of the samples, or in each of the blocks.

Finally, it can be shown

## Two-sample scenario

Consider two independent samples denoted and . The two-sample U-statistic for and is,

If , conditioning on elements of and elements of ,

and

Then for and , we obtain

and similarly for and ,

If and are finite and

then we can approximate the limiting variance of as

such that

At this point, you may be wondering what the heck are these variance components and how am I supposed to estimate them. In my next blog post, I promise that I will provide some examples of common one and two-sample U-statistics and their limiting distributions using our results!

For examples of common one- and two-sample U-statistics and their limiting distribution, check out One, Two, U: Examples of common one- and two-sample U-statistics.