Suppose we have a $n$ balls in an urn labeled $1$ through $n$, and we draw balls without replacement. Suppose we draw a first ball , and then draw an additional $k$ balls uniformly at random without replacement. What is the expected number of balls which have a label larger than the label of the first ball?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|
Let $X$ denote the number on the first ball. Then $$ \mathbb{P}(X=x) = \frac{1}{n} $$ Conditioned on the number on the first ball, the remaining $n-1$ balls are split into two sets, those below $x$, there are $x-1$ of these, and those above, and there are $n-x$ of those. The number $Y|X$ of those above $x$ in the sample of size $k$ drawn without replaced follows hypergeometric distribution $\operatorname{Hyp}(k, n-x, n-1)$ with mean $$ \mathbb{E}(Y|X) = \frac{k(n-x)}{n-1} $$ Thus $$ \mathbb{E}(Y) = \mathbb{E}(\mathbb{E}(Y|X)) = \sum_{x=1}^n \frac{1}{n} \cdot \frac{k(n-x)}{n-1} = \frac{k}{n(n-1)} \sum_{x=0}^{n-1} x = \frac{k}{2} $$ |
|||||||
|
|
Hint: what is the probability that ball #$j$ has a label larger than that of ball #$1$? |
|||||||||||||||
|
|
If the first ball is number $i$, the urn is left with $i-1$ balls with smaller numbers and $n-i$ balls with larger numbers. The expected number in this case is clearly $k\frac{n-i}{n-1}$, provided that $k\le n-1$. The $n$ possible values of $i$ are equally likely, so the overall expected value is $$\frac1n\sum_{i=1}^n\frac{k(n-i)}{n-1}=\frac{k}{n(n-1)}\sum_{i=1}^n(n-i)=\frac{k}{n(n-1)}\sum_{i=0}^{n-1}i=\frac{k}{n(n-1)}\cdot\frac{n(n-1)}2=\frac{k}2\;.$$ You can see this even more easily by imagining that you draw the last $k$ balls first and then draw the ‘first’ ball: by symmetry it must on average be in the middle of the $k$ balls. |
|||||||
|
