Expected values of a sorted sequence

629 Views Asked by At

If I have $n$ random variables uniformly distributed on [0,1]. What is the expectance value kth highest value? In other words, what is the expected value of sorting the random variables?

For $n=2$ the expectance for the highest value is $2/3$ while the second highest is $1/3$.

2

There are 2 best solutions below

0
On BEST ANSWER

You're looking for the term "order statistic". If $X_1, \ldots, X_n$ are i.i.d. random variables, then the order statistic $X_{(1)}, \ldots, X_{(n)}$ of those random variables is a reordering of the values that satisfies $X_{(1)} \le \ldots \le X_{(n)}$.

In the special case of the uniform distribution on $[0, 1]$, the distribution of the $k$-th order statistic $X_{(k)}$ is the beta-distribution $B(k, n + 1 - k)$. This means in particular that $E[X_{(k)}] = \frac{k}{n + 1}$.

You can calculate the density of the $k$-th order statistic in terms of the CDF and the density of the initial distribution via this formula. To prove it, observe that $$P(X_{(k)} \le x) = \sum \limits_{(i_1, \ldots, i_n)} P(X_1 \in A_{i_1}) \ldots P(X_n \in A_{i_n})= \sum \limits_{j = k}^n \binom{n}{j} P(X_1 \le x)^j P(X_1 > x)^{n - j}$$ where $A_0 = (x, \infty)$, $A_1 = (-\infty, x]$ and the sum goes over all tuples $(i_1, \ldots, i_n) \in \{0, 1\}^n$ with $\sum \limits_{j = 1}^n i_j \ge k$. Differentiating the term yields the desired density.

0
On

Let $X_{(1)}\le X_{(2)} \le \cdots \le X_{(n)}$ be the order statistics of the sample $X_1,X_2,\ldots,X_n$. You can calculate $E(X_{(k)})$ using the formula $$E(Y)=\int_0^\infty P(Y>y)\,dy,$$ which is valid for nonnegative $Y$. Applying this to $Y=X_{(k)}$ requires us to find $P(X_{(k)}>y)$. Notice that the event of interest ($X_{(k)}$ exceeds $y$) occurs exactly when at most $k-1$ of the $X$'s are $\le y$. In our case the number of $X$'s that are $\le$ $y$ is a binomial random variable with success probability $y$, since each $X$ is uniform $[0,1]$, so we have for $y\in(0,1)$

$$P(X_{(k)}>y)=\sum_{i=0}^{k-1}{n\choose i}y^i(1-y)^{n-i}$$ and $$ E(X_{(k)})=\int_0^1\sum_{i=0}^{k-1}{n\choose i}y^i(1-y)^{n-i}\,dy $$ Interchanging integration and summation, this equals $$ \sum_{i=0}^{k-1}\int_0^1{n\choose i}y^i(1-y)^{n-i}\,dy = \sum_{i=0}^{k-1}\frac1{n+1} =\frac k{n+1}. $$