Kth largest element from N chosen with a non-standard distribution

Question

I have the following problem:

$n$ values $U_1, \ldots, U_n$ are chosen randomly and independently from the interval $[0,1]$.

When choosing $U_i$, the probability that $U_i$ is smaller than a certain $x$ is $\Pr(U_i \lt x) = f(x)$. For this example let's assume $f(x) = x^2$ (i.e. $\Pr(U_i \lt x) = x^2)$, although a generalization would be welcome.

The question is: after sorting the $n$ values, what is the expected value of the $K$'th element? In other words, if $U_1 \lt \ldots \lt U_n$, then what is the expected value of $U_K$?

I have tried to apply the following logic:

I want to find the $K$'th largest element, so I want to compute the probability that $K$ numbers are smaller than $x$ and $N - K$ numbers are greater than $x$. Since the values are chosen independently, I have $F(i) = \Pr(U_i < x)^{K} (1 - \Pr(U_i < x))^{n - K}$. In our example, that would be $F(i) = x^{2k}(1-x^2)^{n - K}$. I take the derivative of this function to find the density function $F'(x)$, then I integrate $xF'(x)$ on $[0,1]$ to get the expected value. However, this gives me a negative value ($\approx -0.133$) for $n=2$ and $K=1$, so I figure it must be wrong.

Can someone lend me a hand? Thank you in advance.

Answer 1

Your idea is on the right path but you are missing something. $F(i)$ in your notation is the probability that some $U_{i_1},\ldots,U_{i_K}$ values are smaller than $x$, however you can pick indexes $i_1,\ldots,i_K$ in $\binom{n}{K}$ ways therefore the probability that $U_{(K)}$ ($K^{\text{th}}$ order statistic = $K^{\text{th}}$ smallest element) is smaller than $x$ is
$$P[U_{(K)} \leq x ] = \binom{n}{K} \left( P(U_1 \leq x ) \right)^K \left( 1- P(U_1 \leq x ) \right)^{n-K} $$

---

Edit: In the equation above I denoted $U_{(K)}$ the $K^{\text{th}}$ smallest element, what would change if you need $K^{\text{th}}$ largest element?

Answer 2

What you wrote down isn't the probability for the $K$-th smallest element (you wrote "largest" but it seems you meant "smallest") to be less than $x$; it's the probability that $K$ particular elements are less than $x$ and the other $N-K$ are greater. But the $K$-th smallest element is less than $x$ even if all $N$ elements are less. You can tell that your $F$ isn't a cumulative distribution function by the fact that $F(1)=0$ instead of $F(1)=1$.

You need the probability density that one number is $x$, $K-1$ are smaller and $N-K$ are larger. This is proportional to $f'(x)f(x)^{K-1}(1-f(x))^{N-K}$, so the expected value is

$$ \frac{\int_0^1f'(x)f(x)^{K-1}(1-f(x))^{N-K}x\mathrm dx}{\int_0^1f'(x)f(x)^{K-1}(1-f(x))^{N-K}\mathrm dx}=\frac{\int_0^12xx^{2(K-1)}(1-x^2)^{N-K}x\mathrm dx}{\int_0^12xx^{2(K-1)}(1-x^2)^{N-K}\mathrm dx}=\frac{\Gamma\left(K+\frac12\right)\Gamma(N+1)}{\Gamma(K)\Gamma\left(N+\frac32\right)}\;. $$

For $K=1$, $N=2$, this is $\frac8{15}$.