Which strategy is best for this simple probabilistic game...
The game is as follows:
There is a infinitely large bag of balls; half of them red and half of them black.
You initially draw N balls at random and the objective is to end up with all balls of one colour, and to do this you are allowed to swap/replace balls from the N you have with other balls from the bag. The two different paths/strategies you are can take from this point are either:
-
You are allowed to replace ALL (only all of them, not a subset) balls with another randomly selected set of N balls. You are allowed to repeat this up to R times (R will also be the number of times you are allowed to make replacements if you choose option 2) and if at any point all N balls are the same colour you win and the game stops.
-
You are allowed to only replace a subset of size n (n < N) of your set of N balls, where n remains constant throughout the game and again you are allowed to make a subset replacement up to R times. The subset of n balls is chosen randomly from your existing N balls at each replacement iteration and the game stops if all balls achieve the same colour.
My intuition is that strategy 1 will have the maximum likelihood of achieving a full set of the same colour, can someone please explain if this is true and if so why? I would be interested to know what the relationship is between the probability of achieving a full set and the ratio of n and N..
Solution 1:
I think strategy 1 is better. Let's make it simple and assume that $N=3$.
Strategy 1 has probability $1/4$ for success in each draw, so the expected number of draws (including the initial) until success is $4$ with this strategy.
In strategy 2 we only replace one random ball in each draw. The expected number of draws is then a bit trickier to calculate. Let's denote the expected number of draws by $x$. There is a $1/4$ chance that we succed on the first draw. Given that we do not succed on the first draw, we know that we will have $2$ of one colour and $1$ of the other. Denote the conditional expected number of additional draws we need by $x_{21}$. Then note that $% x_{21}=\frac{1}{6}(1)+\frac{5}{6}(x_{21}+1)$, i.e. we have $1/6$ chance to succed on the second try (we must first draw the right ball for replacement and then draw the right colour on the new ball, hence $\frac{1}{3}\frac{1}{2}% =\frac{1}{6}$) and $5/6$ chance to stay in the $2,1$-state (either the initial or the mirrored state, which is the same by symmetry). We can solve the equation for $x_{21}$ according to $x_{21}=6$. Hence $x=\frac{1}{4}(1)+% \frac{3}{4}(6+1)=11/2$.
Hence, the first strategy is the best. I am not competent enough to prove this in the general case, but I think the relative advantage of the first strategy will get bigger and bigger when $N$ increases.