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.
 A: 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<X$. We haven't learned anything about the position of $X_2$ relative to the other two, so the three possible labellings ($X_1<X<X_2$, $X_1<X_2<X$, and $X_2<X_1<X$) 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])

A: 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\}$.
