2
$\begingroup$

In an urn of $N$ balls, there are $B$ black ones (and $N-B$ whites).

There will be $N$ draws without replacement. Each drawn ball is put in a bin. After any $K$ of these $N$ draws the player is allowed to switch any of the white drawn balls in the bin with black balls from the urn. The player wins if no black ball was drawn.

Here is an example of a successful game with $N=4, B=2, K=2$. I'll note $w_u,b_u;w_b,b_b$ for $w_b$ white balls in the urn, $b_u$ black balls in the urn, $w_b$ white balls in the bin, $b_b$ black balls in the bin.

  • Initial situation: 2,2,0,0
  • After draw 1: 1,2,1,0
  • Player decides to make a switch: 2,1,0,1
  • After Draw 2: 1,1,1,1
  • Player decides to make a switch: 2,0,0,2
  • After Draw 3: 1,0,1,2
  • After Draw 4: 0,0,2,2

The question is when to perform these switches to maximize the probability $P$ of winning.

What follows is my progress so far.


Some obvious corner cases:

  • if $K=0$, $P=0$
  • if $B=N$, $P=0$
  • if $B=0$, $P=1$
  • if $K \geq B$, the best thing to do is to replace each of the first $B$ white balls drawn by a black one, giving $P = \left(1-\frac B N\right)\left(1-\frac {B-1} {N-1}\right)\dots{}\left(1-\frac 1 {N-B+1}\right)$

I am interested in the case $0 < K < B$.

Observation: when deciding to make a switch, it is sub-optimal to leave any white balls in the bin if there are black balls left in the urn (this should be fairly intuitive so I won't provide a proof here).

Based on that observation, we can describe any strategy $S$ by a series of integers $S_1, \dots{}, S_K$ (with $\sum S_i = B$), meaning: after $S_1$ draws, switch all white balls from the bin with black ones from the urn (there should be $S_1$ of them, unless the game is already lost); then after $S_2$ additional draws, do the same (there should be $S_2$ of them); etc.

The probability of winning with $S$ is (if I'm correct) as follows:

$$P_S = \frac {{N-B \choose S_1}} {{N \choose S_1}} \frac {{N-B \choose S_2}} {{N-S_1 \choose S_2}} \dots{} \frac {{N-B \choose S_K}} {{N-S_1-\dots{}-S_{K-1} \choose S_K}}.$$

Each factor represents the probability of not failing in the corresponding set of draws. For instance,

$$\frac {{N-B \choose S_i}} {{N-S_1-\dots{}-S_{i-1} \choose S_i}}$$

can be explained as follows. There has been $S_1+\dots{}+S_{i-1}$ balls drawn so far. Provided we have not lost, all the $N-B$ white balls are back in the urn. Among all the ways to draw $S_i$ balls in an urn with $N - (S_1+\dots{}+S_{i-1})$ balls remaining, only those ways to draw $S_i$ balls in among $N-B$ white balls will not result in a loss.

I am quite convinced that the optimal strategy is to choose $S_i = B/K$, that is to evenly spread the switches until no black ball remains in the urn. For instance, if $K=2$, one switch should be performed after $B/2$ (hopefully white) balls have been drawn, followed by another one when $B$ balls have been drawn in total.

I think one way to prove it should be to show $P_S > P_{S'}$ with $S_a \geq S_b$, $S'_a = S_a +1$, $S'_b = S_b -1$, and $S'_i = S_i$ for $i \neq a,b$. It is however just a bit too cumbersome, and I feel like there must be a much simpler, more elegant way to show optimality.

$\endgroup$
  • 1
    $\begingroup$ Why do you say "it is sub-optimal to leave any white balls in the bin"? According to your description of the game, it is not just "sub-optimal", it is illegal: "we are allowed to switch all the white drawn balls in the bin . . ." By the way, when we switch, must we switch the white balls in the bin with an equal number of black balls in the urn? So no switch is possible if there are more white balls in the bin than black balls in the urn? $\endgroup$ – bof Sep 8 '17 at 21:59
  • $\begingroup$ @bof Shrewd observations! I altered the statement so that the switch can technically be any of the white balls in the bin with black ones from the urn (even though it is sub-optimal). Yes, the number of ball put back in the urn must be equal to the number of balls taken from the urn (it is a "switch"). I see your point though, but such a situation would also be the result of a trivially sub-optimal strategy: if there are $x$ black balls left in the urn when the bin is empty, one should not wait more than $x$ draws to make a switch. $\endgroup$ – doc Sep 8 '17 at 22:46
  • $\begingroup$ What is $K$? If the rate at which we perform the swap operation is specified in advance, we have no element of strategy. If the rate at which we perform the swap operation is not specified in advance, then I'd expect it is always better to swap before each draw --- or is that not the case? $\endgroup$ – user326210 Sep 9 '17 at 1:29
  • $\begingroup$ @user326210 $K$ is the number of such swap operations you are allowed to do. $\endgroup$ – doc Sep 9 '17 at 7:59
  • $\begingroup$ I'm confused: I need to end up with no black balls drawn, but my optional operation is to ...draw black balls? $\endgroup$ – Dan Uznanski Sep 12 '17 at 18:15

Your Answer

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

Browse other questions tagged or ask your own question.