How close $k$-sums of a random set of numbers are on average?

Question

Consider a set of random iid variables $x_1, \ldots x_n$ uniformly distributed on $[0, 1]$. For each $S \subset [n]$ with $1 \leq |S| = k < n$ take $\sigma_S = \sum_{i \in S}x_i$. Obviously $\sigma_S$ are distinct with probability 1. What is the expectation of $\Delta = \min_{|S| = |S'| = k, S \neq S'} |\sigma_S - \sigma_{S'}|$, at least asymptotically? Can we say something about concentration of $\Delta$?

Answer 1

Here is some heuristics, which should be possible to strengthen to a completely rigorous answer.

Note that $\sigma_S$ is the sum of the sample of size $k$ taken with replacement from the (random) empirical distribution corresponding to the iid sample $x_1, \ldots x_n$ from the uniform distribution on $[0, 1]$. For large $n$, this empirical distribution is close to the uniform distribution on $[0, 1]$. Also, if $k=o(\sqrt n)$ (which let us assume), then sampling with replacement differs little from sampling without replacement. So, the distribution of $\sigma_S$ (with $S$ considered a random subset of $[n]$ of size $k$) is close to the distribution of the sum of $k$ iid random variables (r.v.'s) uniformly distributed on $[0, 1]$, which, by the central limit theorem, is in turn close to $N(k/2,k/12)$ if $k$ is large, which let us assume as well.

So, the distribution of the vector $(\sigma_S\colon S \subset [n],|S| = k)$ is close to that of the vector $(X_1,\dots,X_N)$ of $N:=\binom nk$ iid r.v.'s each with a distribution close to $N(k/2,k/12)$.

Let $U_j:=F(X_j)$, where $F$ is the cdf of $N(k/2,k/12)$, so that the $U_j$'s are approximately iid uniformly distributed on $[0, 1]$
and hence the random vector $(U_{(j)}-U_{(j-1)}\colon j=2,\dots,N)$ of the spacings between the consecutive order statistics based on the $U_j$'s approximately equals in distribution $(V_2,\dots,V_N)/(V_1+\dots+V_{N+1})$, where the $V_j$'s are iid r.v.'s each with the standard exponential distribution. By the law of large numbers, $V_1+\dots+V_{N+1}\sim N$. So, $(U_{(j)}-U_{(j-1)}\colon j=2,\dots,N)$ is close in distribution to $(V_2,\dots,V_N)/N$.

On the other hand, the minimum of $|X_i-X_j|$ over all $i\ne j$ equals $\min\{X_{(j)}-X_{(j-1)}\colon j=2,\dots,N\}$, where the $X_{(j)}$'s are the order statistics based on $X_1,\dots,X_N$. Now write \begin{equation*} U_{(j)}-U_{(j-1)}=F(X_{(j)})-F(X_{(j-1)}) \sim(X_{(j)}-X_{(j-1)})F'(X_{(j)}) \end{equation*} \begin{equation*} =(X_{(j)}-X_{(j-1)})F'(F^{-1}(U_{(j)})) \sim(X_{(j)}-X_{(j-1)})F'(F^{-1}(j/N)), \end{equation*} whence, with $\tau:=F'\circ F^{-1}$,
\begin{equation*} X_{(j)}-X_{(j-1)}\sim\frac{U_{(j)}-U_{(j-1)}}{\tau(j/N)} \sim\frac1{\tau(j/N)}\frac{V_j}{V_1+\dots+V_{N+1}}\sim\frac{V_j}{N\tau(j/N)}. \end{equation*} Next, \begin{equation*} E\min\{\frac{V_2}{\tau(2/N)},\dots,\frac{V_N}{\tau(N/N)}\} =\int_0^\infty \prod_{j=2}^N P(V_2>\tau(j/N)x)dx \end{equation*} \begin{equation*} =\int_0^\infty \exp\Big(-\sum_{j=2}^N \tau(j/N)x\Big)dx =\frac1{\sum_{j=2}^N \tau(j/N)}\sim \frac1{N\int_0^1\tau(u)du}=\frac{\sqrt{\pi k/3}}N, \end{equation*} by using the substitution $u=F(z)$ in the integral $\int_0^1\tau(u)du$.

So, it should follow that \begin{equation*} E\min\{X_{(j)}-X_{(j-1)}\colon j=2,\dots,N\} \sim \frac1N\,E\min\{\frac{V_2}{\tau(2/N)},\dots,\frac{V_N}{\tau(N/N)}\} \sim\frac{\sqrt{\pi k/3}}{N^2} \end{equation*} and hence \begin{equation*} E\min_{|S| = |S'| = k, S \neq S'} |\sigma_S - \sigma_{S'}|\}\sim \sqrt{\pi k/3}\Big/\binom nk^2. \end{equation*}