6
$\begingroup$

We consider two urns each containing $N$ balls. One of the urns has white balls only. The other has $k$ black balls and thus $N-k$ white balls. Both $N$ and $k$ are known, and $k>0$.

What would be the best ball extraction strategy (without returning an extracted ball to any of the urns) if one wants to find out, which is the urn with the black balls? Best strategy is understood in the sense of reducing the expected number of extracted balls.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Kick over the urns. Expected number of kicks: 1. ;P $\endgroup$ – Raskolnikov Mar 4 '12 at 13:22
3
$\begingroup$

Clearly you stop when you find a black ball. You can also stop when you have taken $N-k+1$ white balls out of either of the urns. There are two obvious strategies to consider:

  1. Keep taking balls out of one particular urn until you can stop (avoiding the cost of looking in the other urn)
  2. Take a ball out of one urn and if you do not stop then take one out of the other. If you still have not stopped then repeat. One version of many equivalent versions would be to alternate between the urns until you stop.

For strategy 1, if you choose the all-white urn the expected time to stop is $N-k+1$, while if you choose the part-black urn it is $$\sum_{n=1}^{N-k+1} n\frac{k}{N-k+1}\frac{N-k+1 \choose n}{N \choose n}=\frac{N+1}{k+1}$$ so the overall expectation is $$\frac{N-k+1}{2} +\frac{N+1}{2(k+1)}.$$

For strategy 2, it is a little like looking for the the part-black urn but using two selections a time, though you may sometimes save a ball, so is $$(2N-2k+1) \frac{k}{N-k+1}\frac{N-k+1 \choose N-k+1}{N \choose N-k+1} +\sum_{n=1}^{N-k} \left(2n-\frac{1}{2}\right)\frac{k}{N-k+1}\frac{N-k+1 \choose n}{N \choose n}$$ or slightly simplified $$\frac{2(N+1)}{k+1} -\frac{1}{2} \left(1+ \frac{1}{{N \choose k}}\right). $$

Edited following joriki's comment:

The difference between the first and second expectations is $0$ when $k=N$ (no surprise, as you only have to look at $1$ ball with either strategy, and empirically is negative when $k \le 2$, $N \le 6$, or $k=N-1$ and positive otherwise. This translates into a mixed strategy depending on $k$ and $N$ vwhich varies with the number of balls left in each urn.

A mixed strategy is difficult to caclulate theoretically, but not impossible for actual values of $k$ and the number of balls in each urn at any one time (though there are many opportunities for errors). The optimal strategy becomes one of continuing until you reach a stopping condition. It seems to be:

  1. If you have an equal number of balls in each urn, choose one from either; in particular if you have $k$ balls left in each urn, choose one ball and stop.
  2. If you have $k$ balls in one urn and more in the other, take one ball from the urn with fewer balls and then stop; this means that if you start with $N=k+1$ the best strategy is to plan to take two balls from the same urn if necessary
  3. If $k=1$, always choose strategy 1, all balls from a single urn until you stop
  4. If $k\ge 3$ and there are $k+1$ or more balls left in each urn, choose a ball from the urn with more balls
  5. If $k=2$ and there is one more ball in one urn than the other, or if there are five balls in one urn and three in the other, or if there are $k$ balls in one urn, then choose a ball from the urn with fewer balls; otherwise choose a ball from the urn with more balls.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ If your calculations are correct, then I think this shows that strategies other than these two extremes need to be included. Consider the case $k=2$, $N\gg2$, and assume you've followed your strategy $1$ until half of one urn is empty. Then the half-empty urn is all-white with roughly $4/5$ probability and part-black with $1/5$. Then the expected time if you continue is roughly $$\frac45\left(\frac N2+\frac N3\right)+\frac15\frac{N/2}3=\frac7{10}N\;,$$ whereas if you switch it's roughly $$\frac45\frac N3+\frac15\left(N+\frac{N/2}3\right)=\frac N2\;,$$ i.e. less. $\endgroup$ – joriki Mar 5 '12 at 6:20
  • $\begingroup$ @joriki: you may be correct. As I said, "more calculation is needed when $k \le 4$" and by that stage I was getting tired. $\endgroup$ – Henry Mar 5 '12 at 7:17
  • $\begingroup$ @joriki: I have taken your point and altered the strategy to something which chooses balls from the fuller urn more often. $\endgroup$ – Henry Mar 5 '12 at 15:39
  • $\begingroup$ Thank you, @Henry. How would one proof analytically this strategy to be the best one and no other to be better in the above sense? $\endgroup$ – Igor Mar 6 '12 at 10:15
  • 1
    $\begingroup$ @Igor: (1) and (2) should be easy. Otherwise at each stage you have a choice: a ball from the urn with fewer balls; otherwise choose a ball from the urn with more balls. So for a formal proof you would beed to show that this gives rise to particular values (probably needed for small $k$) or to bounds (for large $k$) so you can find which option is better. $\endgroup$ – Henry Mar 6 '12 at 13:25

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.