Compute expectation of certain $N$-th largest element of uniform sample A  premier B-school has 2009 students.The dean,a math enthusiast,asks each student to submit a randomly chosen number between 0 and 1.She then ranks these numbers in a list of decreasing order and decides to use the 456th largest number as a fraction of students that are going to get an overall pass grade this year.What is the expected fraction of students that get a passing grade?
I am not able to think in any direction. As it is really difficult to comprehend.
 A: This is a question on order statistics. Let $U_i$ denote independent random variables, uniformly distributed on unit interval. The teacher picks $m$-th largest, or $n+1-m$-th smallest number in the sample $\{U_1, U_2, \ldots, U_n\}$, which is denoted as $U_{n-m+1:n}$. It is easy to evaluate the cumulative distribution function of $U_{n-m+1:n}$, for $0<u<1$
$$\begin{eqnarray}
  \mathbb{P}\left(U_{n-m+1:n} \leqslant u \right) &=& \sum_{k=n-m+1}^n \mathbb{P}\left( U_{1:n} \leqslant u, \ldots, U_{k:n} \leqslant u, U_{k+1:n} >u, \ldots, U_{n:n} >u  \right) \\ 
  &=& \mathbb{P}\left( \sum_{k=1}^n [ U_k \leqslant u] \geqslant n-m+1\right)
\end{eqnarray}
$$
where $[U_k \leqslant u]$ denotes the Iverson bracket. It equals 1 is the condition holds, and zero otherwise. Since $U_k$ are independent, $[U_k \leqslant u]$ are independent identically distributed $0-1$ random variables:
$$
   \mathbb{E}\left( [ U_k \leqslant u] \right) = \mathbb{P}\left(U_k \leqslant u\right) = u
$$
The sum of $n$ iid Bernoulli random variables equals in distribution to a binomial random variable, with parameters $n$ and $u$. Thus:
$$
  F(u) = \mathbb{P}\left(U_{n-m+1:n} \leqslant u \right) = \sum_{k=n-m+1}^n \binom{n}{k} u^{k} (1-u)^{n-k}
$$
The mean can be computed by integrating the above:
$$\begin{eqnarray}
 \mathbb{E}\left(U_{n-m+1:n}\right) &=& \int_0^1 u F^\prime(u) \mathrm{d}u = \left. u F(u) \right|_{u=0}^{u=1} - \int_0^1 F(u) \mathrm{d} u \\ &=& 1- \sum_{k=n-m+1}^n \binom{n}{k} \int_0^1 u^{k} (1-u)^{n-k} \mathrm{d} u \\
  &=& 1 - \sum_{k=n-m+1}^n \binom{n}{k} B(k+1, n-k+1) \\
  &=& 1 - \sum_{k=n-m+1}^n \frac{n!}{k! (n-k)!} \cdot \frac{(k)! (n-k)!}{(n+1)!} \\
  &=& 1 - \sum_{k=n-m+1}^n \frac{1}{n+1} = 1 - \frac{m}{n+1}
\end{eqnarray}
$$
Using $n=2009$ and $m=456$ the exact fraction equals:
$$
   \left.\mathbb{E}\left(U_{n-m+1:n}\right)\right|_{n=2009,m=456} = \frac{259}{335} \approx 0.77313
$$
A: A naive approximation would be: Assume the $N=2009$ given numbers are equidistant within $[0,1]$. The the $k$th smallest should be about $\frac{k-\frac12}N$ and hence the 456th largest = 1554th smalles $\approx \frac{1544-\frac12}{2009}=\frac{63}{82}$. But this reasoning is a bit handwaving.
To be precise you should evaluate for $x\in[0,1]$:
What is the probability $p(x)$ that exactly 1553 guesses are $<x$ and exactly 456 guesses are $\ge x$?
Then the expected value we want is $\int_0^1 x p(x) dx$. Try this latter method for some smaller values of $N$ and $k$ and see how much it dieffers from the straightforward guess $\frac{k-\frac12}N$.
