pr.probability - sum of order statistics

The inequality $E(S_K) geq E(S_i)$ holds.

To avoid any doubt, let me be more specific. Let $Y_1, Y_2, ..., Y_N$ be a collection of random variables, and write $X_1 geq X_2 geq ... geq X_N$ for their reordering in non-increasing order.

Suppose $K < N$ is fixed and let $S_K$ be the sum of the $K$ largest of the random variables, that is $S_K=X_1+...+X_K$.

Let $R$ be a random variable taking values in $0,1,...,N$ which is independent of the random variables $Y_i$. The independence from the $Y_i$ is important of course (this is how I interpret your "based on some criteria". If the $R$ is allowed to depend on the realisation of the $Y_i$ then all sorts of different behaviours are possible).

Now let $S_R$ be the sum of the $R$ largest of the random variables, that is $S_R=X_1+...+X_R$. (In your notation this is $S_i$).

Suppose that $ER=K$. Then I claim that $E S_R leq E S_K$, with equality iff $R=K$ with probability 1. (Unless the $Y_i$ are somehow degenerate, in which case equality can occur in other cases as well).

Proof: Write $p_k=P(Rgeq k)$ for $k=1,2,...,N$. We have $sum p_k=ER=K$.

Also

$S_R=sum_{k=1}^N X_k I(Rgeq k)$

so

$ES_R=sum_{k=1}^N P(Rgeq k) E X_k = sum_{k=1}^N p_k E X_k$.

(Here we used the independence of $R$ from the $X_i$).

Consider maximising this sum subject to the constraints that $sum p_k=K$ and that
$1geq p_1 geq p_2 geq p_3geq ...$.

Since the terms $E X_k$ are decreasing in $k$,
the maximum is achieved when $p_k=1$ for $kleq K$ and $p_k=0$ for $k>K$.
(Provided the $Y_i$ are not degenerate, the terms $E X_k$ are strictly decreasing,
and this is the only way to achieve the maximum. If not, the maximum may be achieved in some other cases too).

That is, the maximum value of $ES_R$ occurs precisely if $R$ is equal to $K$ with probability 1.

It doesn't matter whether the $Y_i$ are identically distributed, and also they don't need to be independent. However, it is important that $R$ is independent of the $Y_i$.

• Next linear algebra - Is there a version of inclusion/exclusion for vector spaces?
• Previous pr.probability - Integrating a simple exponential over the space of matrices that define a metric