3
$\begingroup$

In answering calculate the mean and variance of the highest number drawn on lottery based on the lowest number drawn, I couldn't find the mean and variance of the order statistics of a discrete uniform sample without replacement anywhere, so I figured I'd derive them here for future reference.

Draw $k$ distinct numbers uniformly from $1$ to $n$ and order them as $X_{(1)}\lt\cdots\lt X_{(k)}$. What are the mean and variance of the $X_{(i)}$?

$\endgroup$
2
$\begingroup$

Uniformly randomly permute $n-k$ white balls and $k$ red balls and take the positions of the red balls as the numbers drawn. Consider the indicator variables $Y_{im}$ that are $1$ if the $m$-th white ball is to the left of the $i$-th red ball and $0$ otherwise. Then $X_{(i)}=\sum_mY_{im}+i$.

To find the mean, we need $\def\xp#1{\mathbb E\left[#1\right]}\xp{Y_{im}}$, the probability that a given white ball is to the left of the $i$-th red ball. This happens if among the $k$ red balls and the $1$ given white ball the rank of the white ball is at most $i$, with probability $\frac i{k+1}$. Thus we have

\begin{align} \xp{X_{(i)}} &= \xp{\sum_mY_{im}+i} \\ &= \sum_m\xp{Y_{im}}+i \\ &= i\left(\frac{n-k}{k+1}+1\right) \\ &=i\cdot\frac{n+1}{k+1}\;. \end{align}

To find the variance, we need $\xp{Y_{il}Y_{im}}$, the probability that two particular white balls are both to the left of the $i$-th red ball. This happens if among the $k$ red balls and the $2$ particular white balls the ranks of the white balls are at most $i+1$, with probability $\frac{\binom{i+1}2}{\binom{k+2}2}=\frac{i(i+1)}{(k+1)(k+2)}$. Thus we have

\begin{align} \operatorname{Var}\left[X_{(i)}\right] &= \operatorname{Var}\left[X_{(i)}-i\right] \\ &= \xp{\left(X_{(i)}-i\right)^2}+\xp{X_{(i)}-i}^2 \\ &= \xp{\left(\sum_mY_{im}\right)^2}-\xp{\sum_mY_{im}}^2 \\ &= \xp{\sum_mY_{im}}+\xp{\sum_{l\ne m}Y_{il}Y_{im}}-\xp{\sum_mY_{im}}^2 \\ &= i\cdot\frac{n-k}{k+1}+(n-k)(n-k-1)\frac{i(i+1)}{(k+1)(k+2)}-\left(i\cdot\frac{n-k}{k+1}\right)^2 \\ &= i\cdot\frac{(n-k)}{k+1}\left(1+\frac{(n-k-1)(i+1)}{k+2}-\frac{i(n-k)}{k+1}\right) \\ &= i(k+1-i)\cdot\frac{(n-k)(n+1)}{(k+1)^2(k+2)} \;. \end{align}

As expected, we have symmetry under the transformation $i\to k+1-i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.