Strategy in an urn problem with two urns

Question

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.

Answer 1

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.