Part 1

Start with a setting where I’m estimating $\delta$. Sample $(x_1,y_1)$, then $(x_2,y_2)$. Let’s assume $x_1=0$ and $x_2=1$. Obviously the comparison of these two observations is informative for $\delta$.

Next I sample $(x_3,y_3)$. Now consider how $(x_1,y_1)$ and $(x_2,y_2)$ each compares to $(x_3,y_3)$. Let’s say $x_3=1$. Since $y_3$ is new information about population 1, $y_3-y_1$ seems clearly informative for $\delta$. Let’s add it to the input for the algorithm. But $y_3-y_2$? Since $y_3-y_2=(y_3-y_1)-(y_2-y_1)$, the information that $y_3-y_2$ represents is already in the rest of the data. There shouldn’t be any reason to provide that value.

Continue with sampling $(x_4,y_4)$, and let’s say $x_4=0$. The difference $y_4-y_1$ is a difference within group 0, which could affect the estimate of $\text{E}(Y|X=0)$ and thereby affect the estimate of $\delta$, so I include it in the input. However, $y_4-y_2=(y_4-y_1)-(y_2-y_1)$ and $y_4-y_3=(y_4-y_1)-(y_3-y_1)$, so those are redundant.

For each subsequent sample, all that the algorithm would need to know is the difference between the new $y_i$ and $y_1$. All other differences are redundant. Therefore, after $n$ samples, there will be $n-1$ informative differences — in other words, $n-1$ degrees of freedom.

Part 2

What if I’m interested in $\varphi$ instead?

My intuition here is that what matters for $\varphi$ is the order of the $y_i$ values. This might be obvious. The Wilcoxon test, which is based on ranking the combined sample, clearly returns the same result as long as the order of the outcome values is the same.

More specifically, what matters is where outcomes from group $x=0$ and group $x=1$ appear in the sequence of outcomes. Suppose I assign indices $i$ so that $y_1<y_2<...<y_n$. Then I look at $x_1,x_2,...,x_n$, which is a sequence of 0s and 1s. What matters for estimating $\varphi$ is that there are, say, three 0s, then one 1, then two 0s, etc., in the sequence of $x$s. Any other set of outcomes producing the same sequence of 0s and 1s should contain the same information about $\varphi$.²

Suppose I sample $(x_i,y_j)$ one at-a-time with the $x_i$s being the same as before.

Clearly comparing $(x_1,y_1)$ to $(x_2,y_2)$ is informative. I use it to determine which of the following is the sequence of 0s and 1s.

$$\begin{array}{cc}(x_1=0)& \cdot (x_2=1)\\ (x_2=1)& \cdot (x_1=0)\end{array}$$

Suppose $c(y_2,y_1)=1$, so I have the first sequence above. Now I sample $(x_3,y_3)$ and look at $c(y_3,y_1)$. Suppose $c(y_3,y_1)=1$. Then the possible sequences are

$$\begin{array}{cc}(x_1=0)& \cdot (x_3=1)\cdot (x_2=1)\\ (x_1=0)& \cdot (x_2=1)\cdot (x_3=1)\end{array}$$

Then it doesn’t matter whether $y_3>y_2$ or $y_2>y_3$; it doesn’t change the pattern of 0s and 1s, so $c(y_3,y_2)$ isn’t informative.

On the other hand, if $c(y_3,y_1)=0$, the only possibility is

$$\begin{array}{cc}(x_3=1)\cdot (x_1=0)& \cdot (x_2=1)\end{array}$$

in which case $c(y_3,y_2)$ isn’t informative because it must be equal to 0.

When I sample $(x_4,y_4)$, the situation gets a little complicated. But I wrote some code to determine which combinations of $c(y_i,y_j)$ comparisons are sufficient to determine the Mann-Whitney statistic from 4 observations, and it showed that (perhaps not surprisingly)

1. The minimum number of comparisons occurs when using all between-group comparisons (each observation having $x_i=1$ compared with each having $x_j=0$).
2. Those between-group comparisons are always necessary; the Mann-Whitney statistic isn’t guaranteed to be completely determined by the data unless all of those comparisons are included in the data.

Running similar code, the same was true when a 5th observation, having $x_5=0$, was added to the mix.

Part 3

Here’s another way to see mathematically why $\text{E}(Y_1-Y_0)$ doesn’t require looking at all pairwise differences.

Suppose the outcomes for population 1 are $x_1,\dots ,x_n$, and the outcomes for population 0 are $y_1,\dots ,y_n,y_{n+1},\dots ,y_{n+k}$. That is, population 0 has more individuals. (Things would work similarly if population 1 had more.)

The mean difference between all pairs is

$$\begin{array}{cc}\text{E}(X-Y)& =\frac{1}{n(n+k)}\sum _{i=1}^n\sum _{j=1}^{n+k}(x_i-y_j)\\ & =\frac{1}{n(n+k)}\left[\sum _{i=1}^n\sum _{j=1}^n\right(x_i-y_i)+\sum _{i=1}^n\sum _{j=n+1}^{n+k}(x_i-y_j\left)\right]\end{array}$$

How do some of these comparisons become redundant? Note that

$$x_i-y_j=(x_i-y_i)+(x_j-y_j)-(x_j-y_i)$$

so

$$(x_i-y_j)+(x_j-y_i)=(x_i-y_i)+(x_j-y_j)$$

As a result, in the sum over all pairwise differences among the first $n$ individuals in each population, ${\sum }_{i=1}^n{\sum }_{j=1}^n(x_i-y_i)$, the differences with $i\ne j$ can be substituted with $i=j$ differences, yielding

$$\sum _{i=1}^n\sum _{j=1}^n(x_i-y_i)=n\sum _{i=1}^n(x_i-y_i)$$

Thus, for comparing the first $n$ individuals in each population, I need only $x_1-y_1$, …, $x_n-y_n$.

What remains is the $n\times k$ differences between $x_1,\dots ,x_n$ and $y_{n+1},\dots ,y_{n+k}$: ${\sum }_{i=1}^n{\sum }_{j=n+1}^{n+k}(x_i-y_j)$. These too can be reduced to a smaller number of differences. Suppose I start by committing to use $x_n-y_{n+1}$, $x_n-y_{n+2}$, …, $x_n-y_{n+k}$ (each “extra” $y$ outcome compared to the last $x$ outcome). Then for the remaining differences, I need only $x_n-x_j$, for $j=1,\dots ,n-1$:

$$x_i-y_j=(x_n-y_j)+(x_i-x_n)$$

Then I’m using only $n+k-1$ differences, rather than $n\times k$. This part actually can simplify in a different, interesting way:

$$\begin{array}{cc}\sum _{i=1}^n\sum _{j=n+1}^{n+k}(x_i-y_j)& =k\sum _{i=1}^n{x}_i-n\sum _{j=n+1}^{n+k}{y}_j\\ & =kn\overline{x}-kn{\overline{y}}_{(-n)}\end{array}$$

where ${\overline{y}}_{(-n)}$ indicates the mean of the “extra” $y$ values, i.e. after excluding the first $n$ which are matched with corresponding $x$ values.

The result is

$$\begin{array}{cc}\text{E}(X-Y)& =\frac{1}{n(n+k)}\left[n\sum _{i=1}^n\right(x_i-y_i)+kn(\overline{x}-{\overline{y}}_{(-n)}\left)\right]\\ & =\frac{n}{n+k}{\overline{d}}_{\left(n\right)}+\frac{k}{n+k}(\overline{x}-{\overline{y}}_{(-n)})\\ & =\frac{n}{n+k}(\overline{x}-{\overline{y}}_{\left(n\right)})+\frac{k}{n+k}(\overline{x}-{\overline{y}}_{(-n)})\end{array}$$

where $d_i=x_i-y_i$, ${\overline{d}}_{\left(n\right)}$ is the mean of $d_1,\dots ,d_n$, and ${\overline{y}}_{\left(n\right)}$ is the mean of $y_1,\dots ,y_n$. Thus, $\text{E}(X-Y)$ can be calculated as a weighted average, combining the average of $n$ “one-to-one” differences with an adjustment for the additional outcomes of the individuals in the larger population.