Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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:
Thanks
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.
$f(1,1,1,1)=0$
$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$
$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$
$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$
$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).
