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