# Expected number of tries

Say there are 400 marbles in a bag. I want 4 specific marbles and those marbles have a 1/100, 1/200, 1/300 and 1/400 chance of being drawn. I keep drawing marbles 1 at a time with replacement until I have drawn all 4 marbles that I wanted.

Two questions:

1. What is the expected number of marbles I pick before I get at least 1 of each of the 4 specific marbles I was looking for?
2. What is the probability of drawing all 4 marbles at least once by the nth draw?

Thanks

• What have you tried? Since the probabilities all differ, I'd think backwards induction was the way to go. Label states according to which of the four types you have seen, so $(1,0,0,1)$ means that you have already drawn the first and fourth type but not the second and third. What's the answer if you start from $(1,1,1,0)$? How about $(0,1,1,1)$? and so on. It's a bit tedious, but it works. Helps if you can automate it.
– lulu
Nov 12, 2020 at 13:28
• As for the probability of getting all 4 desired types at least once each by the nth draw, I recommend thinking of the opposite: missing the first desired type in all of the first n draws, missing the second desired type, the third, or the fourth and then using inclusion-exclusion over these. Nov 12, 2020 at 13:35
• I was hoping there would be a simpler/more general method :( I don't know much about math; I looked up the backwards induction. I'm not sure what you mean by starting at (1,0,0,1) or (1,1,1,0). Do I go backwards or forwards from there?
– tim
Nov 12, 2020 at 15:44
• I've tried solving a similar Q1 by solving a similar simpler problem in Excel. I just summed the number of attempts and the probabilities then summed it for the expected number. I was hoping it would help me find a more general solution but it didn't. I did also see online E(X+Y) = E(X) + E(Y) but that doesn't work here I think. I don't think the correct answer is just 100 + 200 + 300 + 400 = 900. Sorry if this seems obvious, I didn't really enjoy math in school. Most of the math I've learnt is online
– tim
Nov 12, 2020 at 15:57
• For Q2, would it be correct to say after 200 attempts: Using binomial probability, the chances for 1/100, 1/200, 1/300 and 1/400 are 63.39%, 39.42%, 28.38% and 22.41% respectively. So the chances of drawing all 4 are just 63.39% x 39.42% x 28.38% x 22.41%?
– tim
Nov 12, 2020 at 16:06

We approach by recursion and markov-chains. Let our states be represented by binary 4-tuples where a $$1$$ in a position corresponds to us having drawn a marble of the corresponding type and $$0$$ if we have not drawn a marble of that type. For examples $$(1,0,0,0)$$ corresponds to having drawn at least one marble of the first type and no other marbles of the other desired types (and any number of undesired marbles).

The "game" ends when we have drawn the final missing desired marbletype.

Let $$f~:~\{0,1\}^4\to\Bbb R$$ be the function which maps a state to the expected number of remaining draws required to reach the final end-state of $$(1,1,1,1)$$.

You should be able to see that these states form a tesseract (a $$4$$-dimensional cube) and on each draw of a new marble one can travel from one state to another higher state by changing a $$0$$-bit into a $$1$$-bit or you may stay at the current state. (Tesseract image taken from wikipedia)

We can start filling in the values for $$f$$ by starting at the top and working our way down. We begin by noting that if we are in the final end-state we require no additional draws to finish since we are already done. For all others, when pulling this adds $$1$$ to our overall expected wait time and we will then need an additional amount of time based on what state we arrive at which varies based on what state it is and will occur with what probability it is to travel to that state. From there, we can with algebra and earlier found values calculate the wait time for each respective state if we had worked on finding these values from top-down.

• No missing marbletypes

$$f(1,1,1,1)=0$$

• One missing marbletype

$$f(0,1,1,1) = 1 + \frac{1}{100}f(1,1,1,1)+\frac{99}{100}f(0,1,1,1) = 100$$

$$f(1,0,1,1) = 1 + \frac{1}{200}f(1,1,1,1)+\frac{199}{200}f(1,0,1,1) = 200$$

$$f(1,1,0,1) = 1 + \frac{1}{300}f(1,1,1,1)+\frac{299}{300}f(1,1,0,1) = 300$$

$$f(1,1,1,0) = 1 + \frac{1}{400}f(1,1,1,1)+\frac{399}{400}f(1,1,1,0) = 400$$

• Two missing marbletypes

$$f(0,0,1,1) = 1 + \frac{1}{100}f(1,0,1,1) + \frac{1}{200}f(0,1,1,1) + \frac{197}{200}f(0,0,1,1) = \frac{700}{3}$$

Working through this line in more detail, we draw a marble and then from $$(0,0,1,1)$$ we could travel up to $$(1,0,1,1)$$ by having drawn a marble of the first type which occurs with probability $$\frac{1}{100}$$ or traveled to $$(0,1,1,1)$$ by having drawn a marble of the second type which occurs with probability $$\frac{1}{200}$$. Having drawn a marble of any other type we remain in the current state which occurs with probability $$1 - \frac{1}{100}-\frac{1}{200}$$. We previously calculated $$f(1,0,1,1)$$ and $$f(0,1,1,1)$$ as being $$200$$ and $$100$$ respectively. We have then $$f(0,0,1,1)=1+\frac{1}{100}\cdot 200 + \frac{1}{200}\cdot 100 + \frac{197}{200}f(0,0,1,1)$$ and after rearranging we have $$\frac{3}{200}f(0,0,1,1)=\frac{7}{2}$$. Multiplying both sides by $$\frac{200}{3}$$ gives $$f(0,0,1,1)=\frac{700}{3}$$

$$f(0,1,0,1) = 1 + \frac{1}{100}f(1,1,0,1) + \frac{1}{300}f(0,1,1,1) + \frac{296}{300}f(0,1,0,1) = 325$$

$$f(0,1,1,0) = 1 + \frac{1}{100}f(1,1,1,0)+\frac{1}{400}f(0,1,1,1)+\frac{395}{400}f(0,1,1,0) = \dots$$

$$\vdots$$

$$f(1,1,0,0) = 1 + \frac{1}{300}f(1,1,1,0)+\frac{1}{400}f(1,1,0,1)+\frac{1193}{1200}f(1,1,0,0)=\dots$$

• Three missing marbletypes

$$f(0,0,0,1) = 1 + \frac{1}{100}f(1,0,0,1) + \frac{1}{200}f(0,1,0,1)+\frac{1}{300}f(0,0,1,1) + \frac{589}{600}f(0,0,0,1) = \dots$$

$$\vdots$$

• Four missing marbletypes

$$f(0,0,0,0) = 1+\frac{1}{100}f(1,0,0,0)+\frac{1}{200}f(0,1,0,0)+\frac{1}{300}f(0,0,1,0)+\frac{1}{400}f(0,0,0,1) + \frac{1175}{1200}f(0,0,0,0) = \dots$$

This final value is what you are after. It is going to be highly tedious and so I leave it to you to complete. With some programming skill, you could automate the calculations (though be careful about floating arithmetic errors).