Expected number of steps

Question

I play a game as follows. A bucket contains four red balls and three green balls. At each step, a ball is chosen at random from the bucket, with each of the balls there being equally likely to be chosen. If a red ball is chosen, it is removed from the bucket. If a green ball is chosen, it is returned to the bucket. The game continues until all of the four red balls have been removed from the bucket. What is the expected number of steps before the game ends?

Answer 1

A generalization: if $X_k \sim Geometric(p_k)$, and $Y = \sum_k X_k$, then $\mathbf{E}Y = \sum_k \mathbf{E}Y_k$. You sample balls until you find a red one (that the success event).

Answer 2

What is the expected number of steps needed for hitting a red ball for the first time? After that you somehow start over with $4-1=3$ red balls and $3$ green balls. Then ask the same question (and repeat that).

Answer 3

At the start, we have a $4/7$ chance of picking a red ball. This probability remains until we do, and then then probability becomes $3/6$ (and then $2/5$ and $1/4$). If we let the number of steps until we pick the first, second, third, fourth red be $x_1, x_2, _3, x_4$, then the expected number of steps is $\sum_i x_i$. I think the theory sort of comes to an end around here.

Answer 4

Start by drawing a directed weighted graph with the probability of each outcome. For instance, at the first step you have two possible events, R and G, such that P(R) = 4/7 and P(G) = 3/7. If you get G, you're back to square one, hence G points back at the beginning. Instead, if you get R, you move further to the second bifurcation, and so on. Something like this:

Now you can work out a formula for the expected number of steps t:

$$ t = \frac{3}{7}(1+t) + \frac{4}{7}\left ( \frac{1}{2}(1+(t-1)) +\frac{1}{2}\left ( \frac{3}{5}(1+(t-2)) +\frac{2}{5}\left(\frac{3}{4}(1+(t-3))+\frac{1}{4}(4)\right) \right ) \right ) $$

The last "4" in the formula refers to the probability that the game ends in exactly 4 turns.

Solving for t, you get an expected value of 7.