# What is the distribution of the sum of differences of i.i.d. variables?

Let's suppose that $$X, X_1, X_2, \ldots, X_n$$ are i.i.d. continuous random variables.

Let's define $$D_i$$ as the difference between $$X_i$$ and $$X$$: $$D_i = X_i - X$$

My end goal is to derive the distribution of: $$\sum_{i=1}^{n} I_{D_i < 0}$$

Since the $$X_i$$ and $$X$$ follow the same distribution, the $$D_i$$ should be identically distributed. It should also hold that the $$D_i$$ are symmetric about zero. From there, the indicators follow the Bernoulli distribution with the success probability equal to $$\frac{1}{2}$$.

If the indicators were independent, the sum would follow the binomial distribution with parameters $$n$$ and $$\frac{1}{2}$$.

However, I'm not sure about independence.

On one hand, since the $$X_i$$ are independent, knowing that $$D_i < 0$$ shouldn't change the probability that other differences are lower than zero.

On the other, I subtract the same $$X$$ from all the $$X_i$$. So, there is some sort of dependence there. I'm not sure if it implies the indicators aren't statistically independent.

• That sum has value $k, 0 \leq k \leq n,$ if and only if exactly $k$ of the $X_i$ are larger than $X$ and exactly $n-k$ of the $X_i$ are smaller than $X$. So, conditioned on $X = a$, can you find the conditional distribution of that sum? Commented Aug 20, 2022 at 13:27
• If $X=a$, the conditional probability is $p(k \mid a) = \binom{n}{k}\left[ F_X(a) \right]^k \left[ 1 - F_X(a) \right]^{n-k}$, where $F$ is the CDF of $X$. So, the unconditional probability should be $\int p(k \mid a) f(a) da$, where $f$ is the density of $X$, shouldn't it? Commented Aug 20, 2022 at 14:25

Define $$Y_i=I_{D_i<0}$$.

Imagine that you've sampled 3 iid values from some distribution and you're now labelling them $$\{X,X_1,X_2\}$$. There are $$3!=6$$ possible labellings, all of which are equally likely.

It's easy to see that $$X_1$$ will be less than $$X$$ in half of these labellings, so you are right that $$Y_1=1$$ with probability $$1/2$$.

Now suppose we condition on $$Y_1=1$$, i.e. our sample space consists of the 3 labellings where $$X_1. We haven't learned anything about the position of $$X_2$$ relative to the other two, so the three possible labellings ($$X_1, $$X_1, and $$X_2) are equally probable.

We conclude that $$P(Y_2=1 | Y_1=1) = 2/3$$, so the indicators are positively correlated.

Can you work out how this result generalises to $$P(Y_n=1 | Y_1=Y_2=\ldots=Y_{n-1}=1)$$?

Edit: here's a bit of R code if you want to convince yourself. You can change the distribution in the second line to anything you like.

numSamples <- 1e6
sample1 <- matrix(rexp(3 * numSamples), nrow = numSamples)
mean(sample1[, 2] < sample1[, 1])
sample2 <- sample1[sample1[, 2] < sample1[, 1], ]
mean(sample2[, 3] < sample2[, 1])

• There should be $(n-1)!$ ways to label those smaller than $X$, times only one way for $X_n$ to be greater than $X$, so $P(Y_n=0 \land Y_1=\ldots=Y_{n-1}=1)=\frac{(n-1)!}{(n+1)!}=\frac{1}{n(n+1)}$. Then, $P(Y_1=\ldots=Y_n=1)=\frac{n!}{(n+1)!}=\frac{1}{n+1}$ because there are $(n-1)!$ labelings in which $X_i < X$ ($i=1,2,\ldots,n-1$), times $n$ ways to label $X$ and $X_n$ so that $Y_1=\ldots=Y_n=1$ holds. The conditional probability of $Y_n=0$ is then $\frac{1}{n}$, so $P(Y_n=1 \mid Y_1=\ldots=Y_n=1)=1-\frac{1}{n}$ if I didn't make a mistake somewhere. Thanks. :) Commented Aug 20, 2022 at 14:53
• Yep, that's what I got too. Commented Aug 20, 2022 at 15:15

The distribution is uniform over $$\{0, 1, \ldots, n\}$$.

Since $$X_i - X < 0 \iff X_i < X$$, the sum of the $$D_i$$ is: $$M = \sum_{i=1}^{n}I_{X > X_i}$$ i.e., the number of the $$X_i$$ smaller than $$X$$.

If $$M=k-1$$, $$X$$ is the $$k$$th order statistic of $$\{X, X_1, X_2, \ldots, X_n\}$$. Since $$X, X_1, X_2, \ldots, X_n$$ are i.i.d., all the orderings are equally likely. There are $$1 \times n!$$ orderings in which $$X$$ is the $$k$$th smallest: one way to set $$X$$ as the $$k$$th smallest, $$n!$$ to order the rest. In total, there are $$(n+1)!$$ orderings, so: $$\Pr(M=k-1)=\frac{1 \times n!}{(n+1)!} = \frac{1}{n+1} \quad k=1,2,\ldots,n+1$$

This has a nice connection to the CDF of $$X$$. If $$F$$ is the CDF of $$X$$, $$F(X)$$ follows the uniform distribution over $$[0, 1]$$. $$\frac{1}{n}M$$ is an estimator of $$F(X)$$ using the sample $$X_1, X_2, \ldots, X_n$$, and since there are $$n+1$$ possible values it can take $$\left(\frac{k}{n} \mid k=0,1,\ldots,n \right)$$, it makes sense that $$M$$ is uniform over $$\{0,1,2,\ldots, n\}$$ and $$\frac{1}{n}M$$ over $$\left\{0, \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}, 1 \right\}$$.