Distribution of the sum of the $m$ smallest values in a sample of size $n$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.