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$?

  • 1
    $\begingroup$ Seemingly a loose (trivial) upper bound could be get by calculating $E[(\sigma_S-\sigma_{S'})^2]$. $\endgroup$ – Lwins Sep 26 '17 at 16:30

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*}

  • $\begingroup$ This is very interesting, thanks! I still have a few concerns: 1) If $k >> \sqrt{n}$ almost all pairs of $\sigma_S$ are dependent due to birthday paradox. Could if affect the result significantly? 2) I am not much convinced about approximating normally distr. variables with uniformly distr. ones, especially in light of order statistics where tail distribution may weigh in. Can you clarify why this is a decent approx.? 3) Could you please cite a source on difference of order statistics being equally distr. with functions of exp. distr. variables? $\endgroup$ – Mikhail Tikhomirov Sep 27 '17 at 20:41
  • $\begingroup$ @MikhailTikhomirov : 1) This concern may be valid, and it may turn out that the restriction $k<<\sqrt n$ is needed for the heuristics to go through. 2) I have added comments on what could be done without the "approximation" (anyway, the tails should matter little, as the spacings $X_{(j)}-X_{(j-1)}$ are greater there, given the distribution of $X_j$ is close to normal). 3) Concerning the spacings for the uniform distribution, this can be done by straightforward distribution transformation technique; see e.g. Theorem 6.6 in \url{bit.ly/2wkcw2f}. $\endgroup$ – Iosif Pinelis Sep 27 '17 at 21:29
  • $\begingroup$ The constant factor in the asymptotics is now specified to be $\sqrt{\pi/3}$, and the heuristic "approximation" of the normal distribution by a uniform one is completely eliminated. $\endgroup$ – Iosif Pinelis Sep 28 '17 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.