Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\mathbf X = [X_1, X_2, \ldots, X_n]^\mbox{T}$ be a vector random variable drawn from a known distribution with CDF $F(x)$. The CDF for the minimum value in $\mathbf X$ is clearly $P[\min_{i=1\ldots n} X_i \leq x]$ $=$ $1 - \prod_{i=1\ldots n} P[X_i>x]$ $=$ $1 - (1 - F(x))^n$. The expected value for the minimum value in $\mathbf X$ is therefore $\int_0^\infty 1 - (1 - (1 - F(x))^n)dx$.

I am interested in the sum of the $m$ smallest values (i.e., order statistics) in $\mathbf X$.

It seems like the expected value for the sum should look something like
$\sum_{i=0}^{m-1} \int_0^\infty 1 - (1 - (1 - F(x))^{n-i})dx$,
however, my intuition tells me that that conflicts with the independence of the events.

I therefore have two questions:

  1. What is the expected value of the sum of the $m$ smallest values in $\mathbf X$?
  2. What is the PDF and/or CDF of the sum?

An answer to #2 alone would be sufficient.

share|improve this question
It seems like this paper may be useful: jstor.org/stable/4615746?seq=4 I am reading it now. –  ESultanik Feb 15 '10 at 18:27
Your claim about the expected value is correct (assuming you mean $\sum_{i=0}^{n-1}$; the expectation of a sum is the sum of the expectations, whether the summands are independent or not. –  Michael Lugo Feb 15 '10 at 18:50
@Michael: No, that is too easy. The sum of the $m$ smallest variables is called for; so far we only know the expectation of one of them (the smallest); the others will have different distributions, different expectations. @ESultanik: It seems to me you could have simplified your integrals using the trivial relation $1-(1-a)=a$ – not that it helps much, but it had me scratching my head for a moment, wondering if something had got lost in all the parentheses. –  Harald Hanche-Olsen Feb 15 '10 at 19:24
The paper to which I linked above is the special case for the Gamma distribution. Special cases for the exponential and uniform distributions also exist. It seems like solving this for any arbitrary distribution is an open problem, though. –  ESultanik Feb 15 '10 at 19:24
If you're willing to settle for asymptotics as $n\to \infty$, this question fits into extreme value theory. You can find extract (asymptotic) answers to much more general questions from, for example, the book by Leadbetter, Lindgren, and Rootzen. –  Mark Meckes Feb 16 '10 at 12:19
show 1 more comment

3 Answers

I'll address problem 1. Let the probability that the $i$th order statistic is greater than $x$ be $g_i(x)$, which means there are at most $i-1$ coordinates less than $x$.

$g_{i+1}(x)-g_{i}(x) =$ probability that exactly $i$ coordinates are less than $x$

$$= {n \choose i} F(x)^i (1-F(x))^{n-i}$$

$$ g_i(x) = \sum_{k=0}^{i-1} {n \choose k} F(x)^k (1-F(x))^{n-k}.$$

If we assume the variables are positive, the expected value of the $i$th order statistic is

$$\int_{0}^\infty g_i(x) dx .$$

So, the expected sum of the first $m$ order statistics is

$$ \sum_{i=1}^m \int_{0}^\infty \sum_{k=0}^{i-1} {n \choose k} F(x)^k (1-F(x))^{n-k} dx$$

$$= \int_{0}^\infty \sum_{k=0}^{m-1} (m-k){n \choose k}F(x)^k (1-F(x))^{n-k} dx .$$

Maybe this simplifies, but I don't see it.

share|improve this answer
add comment

This is following on from Douglas Zare's answer. While not an answer in its own right,it was getting too long for a comment. Briefly, we can hit the question with brute force and look for a generating function for the desired expected values.

So, put $$f_j(y) = \sum_{k=0}^{j-1} {n \choose k} y^k (1-y)^{n-k}$$ so that using the notation of Douglas' answer, $g_j(x)=f_j(F(x))$, and the expectation of the $j$th order statistic is $$ E_j := \int_0^\infty f_j(F(x)) \ dx $$

Put $G(y,z) = \sum_{j=1}^n f_j(y) z^j$ where $z$ is a formal variable. By linearity we have $$ \sum_{j=1}^n E_j z^j = \int_0^\infty G(F(x),z) \ dx $$

We can try to write $G$ as a rational function in $y$ and $z$. Expanding out and interchanging the order of summation gives $$ \eqalign{ G(y,z) & = \sum_{j=1}^n\sum_{k=0}^{j-1} {n\choose k} y^k (1-y)^{n-k} z^j \\\\ & = \sum_{k=0}^{n-1} \sum_{j=k+1}^n z^j {n\choose k} y^k (1-y)^{n-k} \\\\ & = \sum_{k=0}^{n-1} \left( \sum_{j=1}^{n-k} z^j \right) \cdot z^k{n\choose k} y^k (1-y)^{n-k} \\\\ } $$

Now $$ \eqalign{ \sum_{j=1}^{M-1}jz^j = z \frac{d}{dz}\sum_{j=0}^{M-1} z^j & = z \frac{d}{dz}\left[\frac{1-z^M}{1-z}\right] \\\\ & = \frac{z-z^{M+1}}{(1-z)^2} - \frac{Mz^M}{1-z} & = \frac{z-z^M}{(1-z)^2} - \frac{(M-1)z^M}{1-z} } $$ so substituting this back in we get $$ \eqalign{ G(y,z) & = \sum_{k=0}^{n-1} \left[ \frac{z-z^{n-k+1}}{(1-z)^2} - \frac{(n-k)z^{n-k+1}}{1-z} \right] \cdot z^k{n\choose k} y^k (1-y)^{n-k} \\\\ & = \sum_{k=0}^{n-1} \frac{z}{(1-z)^2}{n\choose k} (yz)^k (1-y)^{n-k} \\\\ & \ \ - \sum_{k=0}^{n-1} \frac{z^{n+1}}{(1-z)^2} {n\choose k} y^k (1-y)^{n-k} \\\\ & \ \ - \sum_{k=0}^{n-1} \frac{nz^{n+1}}{1-z} { {n-1} \choose k } y^k(1-y)^{n-k} \\\\ & = \frac{z}{(1-z)^2} \left[ (1-y+yz)^n - (yz)^n \right] - \frac{z^{n+1}}{(1-z)^2} (1-y^n) - \frac{nz^{n+1}}{1-z} } $$

I guess that in theory one could plug this back in to obtain a "formula" for the generating function $\sum_{j=1}^n E_j z^j$, but I can't see how that formula might then simplify to something calculable, unless $F$ has a rather special form.

share|improve this answer
add comment

Is anything about the distribution of the minimum, if we allow dependence between the $X_i$, i.e., remove the independence assumption?

I am specifically interested in the following, select $K$ random binary vectors $Y_i$ of length $m$ uniformly at random, but let your collection of random variables be $X_{i,j}=w(Y_i \oplus Y_j)$ where $w(\cdot)$ denotes the Hamming weight of a binary vector, i.e., the number of the nonzero coordinates in its argument. In terms of the original question we have $n=C(K,2)=K(K-1)/2$ no longer independent random variables $X_{i,j}$ with support {$0,1,\ldots,m$} and individual distribution $Bin(m,1/2)$. It seems to me that the random variables $X_{i,j}$ will be negatively correlated, if distances between pairs chosen from a subcollection of $Y_{i_1},Y_{i_2},\ldots,Y_{i_v}$ where ($v < K$) tincreases then the distances between $Y_{i_j}$ and the remaining vectors will tend to decrease.

I will be happy with any pointers to literature or any other suggestions.

share|improve this answer
I hope I haven't comitted a faux pas, by talking about a related problem but I don't know how to move the above to be a comment, if that's appropriate. –  kodlu Feb 25 '10 at 1:23
It is ok to make an answer which is a comment when your reputation is too low to make comments. However, I suggest asking a separate question, and then linking back to this one if you think it's closely related, which is unclear. –  Douglas Zare Feb 25 '10 at 1:28
Just to agree with Douglas: you definitely stand a better chance of getting your question answered if you post it as a separate question. –  Tom Leinster Feb 25 '10 at 1:34
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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