11

Consider $\sum_{i=1}^N |X_i|$ where $X_1, \ldots, X_N$ are i.i.d. and the CLT holds.
How many of the biggest terms add up to half the total sum ?
For example, 10 + 9 + 8 $\approx$ (10 + 9 + 8 $\dots$ + 1) / 2: 30 % of the terms reach about half the total.

Define
$ \qquad\text{sumbiggest( j}; X_1 \dots X_N ) \equiv \text{sum of the j biggest of } |X_1| \dots |X_N| $
$ \qquad\text{halfsum}( N ) \equiv \text{the smallest j such that sumbiggest( j )} \approx \text{sumbiggest}( N ) / 2 . $

Is there a general asymptotic result for halfsum( $N, \mu, \sigma$ ) ?
A simple, intuitive derivation would be nice.

(A little Monte Carlo suggests that sometimes halfsum( $N$ ) $\approx N$/4 or so;
that is, the biggest 1/4 of the $X_i$ add up to 1/2 the total.
I get 0.24 $N$ for halfnormal, 0.19 $N$ for exponential, for $N$ = 20, 50, 100.)

denis
  • 3,187
  • 20
  • 34
  • 3
    Don't expect a CLT-like universal result. For instance, the answer for uniform(0,1) variates will be *very* different from the answer for uniform(1000,1001) variates! – whuber Dec 12 '11 at 19:23
  • Right, halfsum will of course depend on mean and sd. But why ~ N/5 for exponential ? – denis Dec 13 '11 at 10:21
  • 2
    Asymptotically, Denis, the cutoff for the halfsum will be the value $x$ for which $\int_0^x t f(t)dt = 1/2$ where $f$ is the pdf for $|X_i|$; the question asks for $N(1-F(x))$ ($F$ is the cdf for $|X_i|$). In the case of the uniform$[0,1]$ distribution you get @Dilip's answer; for an exponential, $x\approx 0.186682 N \approx N/5$. – whuber Mar 12 '12 at 14:59

3 Answers3

2

No, there isn't a general asymptotic result. Let $x_{[1]} \dots x_{[N]}$ be the ordered $x_i$, where $x_{[1]}$ is the largest.

Consider the following two examples:

1) $P(x=0) = 1$. Clearly the CLT holds. You only need $M=1$ observation for $\sum_{j=1}^M|x_{[j]}| \ge \frac{1}{2} \sum_N|x_i|$.

2) $P(x=1) = 1$. Clearly the CLT holds. You need $M=\lceil N/2\rceil$ observations for $\sum_{j=1}^M|x_{[j]}| \ge \frac{1}{2} \sum_N|x_i|$.

For a nontrivial example, the Bernoulli distribution:

3) $P(x=1) = p,\space P(x=0) = 1-p$. Once again the CLT holds. You need $\lceil pN/2\rceil $ of the observations to meet your conditions. By varying $p$ between 0 and 1, you can get as close to example 1 or example 2 as you like.

jbowman
  • 31,550
  • 8
  • 54
  • 107
  • 4
    It is indeed evident that the answer can be anywhere between $0$ and $N/2$, but that does not imply the non-existence of a general result. What it does imply is we should consider answers where the fraction depends on some properties of the underlying distribution such as its mean and SD. Those are enough, along with the CLT, to provide specific and quantitative information about how the $x[i]$ are distributed compared to their sum, so it's reasonable to hope for such a result. – whuber Dec 12 '11 at 19:37
1

Here is a crude argument giving a slightly different estimate for uniformly distributed random variables. Suppose the $X_i$ are continuous random variables uniformly distributed on $[0,1]$. Then, $\sum_i X_i$ has mean value $N/2$. Assume that by a surprising and totally unbelievable coincidence, the sum is exactly equal to $N/2$. So we want to estimate how many of the largest values of $X$ sum up to $N/4$ or more. Now, the histogram of $N$ samples ($N$ very large) drawn from the uniformm distribution $U[0,1]$ is roughly flat from $0$ to $1$, and so for any $x$, $0 < x < 1$, there are $(1-x)N$ samples distributed roughly uniformly between $x$ to $1$. These samples have average value $(1+x)/2$ and sum equal to $(1-x)N(1+x)/2) = (1-x^2)N/2$. The sum exceeds $N/4$ for $x \leq 1/\sqrt{2}$. So, the sum of $(1-1/\sqrt{2})N \approx 0.3N$ largest samples exceeds $N/4$.

You could try and generalize this a bit. If $\sum_i X_i = Y$, then for any given $Y$, we want $x$ to be such that $(1-x^2)N/2 = Y/2$ where $Y$ is normal with mean $N/2$ and variance $N/12$. Thus, conditioned on a value of $Y$, $x = \sqrt{1-(Y/N)}$. Multiply by the density of $Y$ and integrate (from $Y=0$ to $Y=N$) to find the average number of largest samples that will exceed half the random sum.

Dilip Sarwate
  • 41,202
  • 4
  • 94
  • 200
  • The distance between two points restricted to be in the interval $(0,1)$ cannot be exponentially distributed because the distance must be less than $1$ while an exponential random variable take on values in $(0,\infty)$. What is true is that if $Y_1, Y_2, \ldots, Y_{n+1}$ are independent exponential random variables, then _conditioned_ on $Y_{\max} = \alpha$, the _order statistics_ $Y_{(1)}, Y_{(2)}, \ldots, Y_{(n)}$ are uniformly distributed in $(0, \alpha)$. See, for example, [this question and answer](http://math.stackexchange.com/q/74218/15941) on the companion site math.SE. (continued) – Dilip Sarwate Dec 13 '11 at 12:16
  • In any case, my argument does not use the _distances_ between the ordered samples from the uniform distribution. – Dilip Sarwate Dec 13 '11 at 12:17
  • You're right, I misunderstood you. As a side question, aren't the pieces between uniform-random points exponentially distributed, after scaling -- the converse of your q+a ? [Broken Stick Rule from the Wolfram Demonstrations Project] (http://demonstrations.wolfram.com/BrokenStickRule) sure looks exponential, there must be an easy? proof. – denis Dec 13 '11 at 14:03
  • Please ask your side question as a separate question. – Dilip Sarwate Dec 13 '11 at 14:12
  • Started, then saw [probability-distribution-of-fragment-lengths](http://stats.stackexchange.com/questions/10897/probability-distribution-of-fragment-lengths), you could comment there. – denis Dec 13 '11 at 15:01
0

Let's assume X has just positive values to get rid of the absolute value.

Without an exact prove, I think you have to solve for k

$(1-F_{X}(k))E(X|X>=k)= \frac{1}{2} E(X)$ with F being the cumulative distribution function for X

and then the answer is given by taking the $n(1-F_X(k))$ highest values.

My logic is that asymtopically the sum of all values higher than k should be about

$n(1-F_{X}(k))E(X|X>=k)$

and asymtopically half the total sum is about

$\frac{1}{2}nE(X)$.

Numerical simulation show that the result holds for the uniform case (uniform in $[0,1]$) where $F(k)=k$ and I get $k=\sqrt(\frac{1}{2})$. I am not certain if the result always hold or if it can be simplified further, but I think it really depends on the distribution function F.

Erik
  • 6,909
  • 20
  • 48