# Lowest index giving half of the sum

Numbers $x_1,x_2,\ldots,x_n$ are drawn independently and uniformly from the interval $[0,1]$. Order them as $y_1\ge y_2\ge\dots\ge y_n$, and let $S$ be their sum. Let $k$ be the smallest index such that $y_1+\dots+y_k\geq S/2$.

What is $E[k]$, and what are other known properties about $k$ (e.g., variance)? Is there any reference to this? I don't know what terms to use to search.

• Quite an interesting question. A somewhat related topic, in case you don't know the name already, is order statistics. – Anthony Quas Mar 14 '16 at 22:16
• The mean should be close to $n/\sqrt 2$ (if you look at the samples from the $x_i$'s that are below $1/\sqrt 2$, there should be roughly $n/\sqrt 2$ of them and their average value should be $1/(2\sqrt 2)$, so that the sum is roughly $n/4$. On the other hand, the total of all the samples should be close to $n/2$. – Anthony Quas Mar 14 '16 at 22:21
• The variance is of order $n$: if you take the samples up to $1/\sqrt 2$, there are $n/\sqrt 2+O(\sqrt n)$ of them and their sum is $n/4+O(\sqrt n)$. The full sum is $n/2+O(\sqrt n)$. So the way to get the "scale balance point" is to start with the ones up to $1/\sqrt 2$ and then move $O(\sqrt n)$ terms of the biggest terms below $1/\sqrt 2$ or the smallest terms above $1/\sqrt 2$ to the other side to get the two sides to balance. – Anthony Quas Mar 14 '16 at 22:27
• Anthony:I think your reasoning is good for the ascending order, but the order is descending. So, the mean should be flipped to about $n-n/\sqrt2$. – Iosif Pinelis Mar 14 '16 at 23:43
• right... sorry. I should have read the question more carefully. Of course knowing one, you know the other. – Anthony Quas Mar 15 '16 at 0:27

Here's an approximate answer: let $U_1,U_2,\ldots,U_n$ be the i.i.d. uniform random variables. I will consider them ordered from smallest to largest because it makes the arithmetic cleaner. We're then asking adding from smallest to largest, how many do we need to sum in order that $U_{i_1}+\ldots +U_{i_k}>\frac S2$, where $S=U_1+\ldots+U_n$.

Define additional random variables: \begin{align*} X&=\#\{i\colon U_i<1/\sqrt 2\};\\ Y&=\sum_{U_i<1/\sqrt 2} U_i-n/4;\\ Z&=\sum_i U_i-n/2. \end{align*} It's not hard to check that $\mathbb EX=n/\sqrt 2$, $\mathbb EY=\mathbb EZ=0$.

The ideal situation is when $Z=2Y$; that is the terms below $1/\sqrt 2$ have exactly the same sum as those above. To compensate for the difference, we need to move terms totalling $\frac Z2-Y$ into the "small number subset" (if $Z>2Y$) or move terms totalling $Y-\frac Z2$ into the large number subset (if $Z<2Y$).

Since the terms on the boundary are of size approximately $\frac 1{\sqrt 2}$, one expects that the number such that $U_{i_1}+\ldots+U_{i_k}=S/2$ is well-approximated by $M=X+\sqrt 2(\frac Z2-Y)$.

From the definition, one sees $$M=\sum_{i=1}^n \Big( \mathbf 1_{U_i<1/\sqrt 2} + (1/\sqrt 2)U_i - \sqrt 2U_i\mathbf 1_{U_i<1/\sqrt 2}\Big).$$ A calculation shows that $\mathbb EM=n/\sqrt 2$ and $\text{Var}(M)=n(9\sqrt 2-2)/12$. I anticipate that the expectation is correct to $O(1)$ and the variance is correct to $O(\sqrt n)$.

BTW: If anyone can tell me how make this rigorous, I'd very much like to know.

• As a related question, if i consider the process $\sqrt{n}(y_{n-\lfloor tn \rfloor +1} - t)$, what does it converge to in law? Here is a related result on the order statistics of adjacent spacings of $n$ uniform points in $[0,1]$: projecteuclid.org/euclid.aop/1176993799 – John Jiang Mar 17 '16 at 5:11