Expected number of draws to draw 3 of the same balls out of an urn with replacement

Question

An urn contains twelve balls numbered 1 to 12. We draw a ball, record its number, and replace it in the urn. We repeat this until we draw any number three times. What is the expected number of draws?

First post here. Anyhow, I can solve the variant with one repeat, but I am struggling to figure out how to solve it with two repeats.

My initial guess was to use a Geometric distribution with $E[X] = 1/p$, where $p = P(\text{three balls are} 1)+...+P(\text{three balls are} 12) = 12*(1/12^3)$. So $1/(12*(1/12^3)) = 144$.

It seemed a bit high, and I realized that this only works if we are drawing three at a time. Been stumped for a few hours now. I think I am overthinking this. Can anyone help?

Answer 1

Let's say the first time we have drawn the same number three times is on draw number $X$, so we want to find $E(X)$. Our approach is to find $P(X>n)$ for $n=0,1,2, \dots ,24$, and then apply the theorem $E(X) = \sum_{n>0} P(X>n)$.

$X>n$ if no number has been drawn more then two times by the $n$th draw. There are $12^n$ possible sequences of numbers in $n$ draws, all of which we assume are equally likely. We would like to count the sequences in which no number occurs more than twice; let's say this number is $a_n$. The exponential generating function for $a_n$ is $$\begin{align} f(x) &= \left( 1+x+\frac{1}{2}x^2 \right)^{12} \\ &= \left[ (1+x)+\frac{1}{2}x^2 \right]^{12} \\ &= \sum_{i=0}^{12} \binom{12}{i} (1+x)^i \left( \frac{1}{2} x^2 \right)^{12-i} \\ &= \sum_{i=0}^{12} \binom{12}{i} \left( \frac{1}{2} \right)^{12-i} x^{24-2i} \sum_{j=0}^i \binom{i}{j} x^j \\ &= \sum_{i=0}^{12} \sum_{j=0}^i \binom{12}{i} \left( \frac{1}{2} \right)^{12-i} \binom{i}{j} x^{24-2i+j} \end{align}$$ where we have applied the binomial theorem twice above.

So $a_n$ is the coefficient of $(1/n!) x^n$ in $f(x)$: $$a_n = n! \sum_{i=12-\lfloor n/2 \rfloor}^{12} \binom{12}{i} \left( \frac{1}{2} \right)^{12-i} \binom{i}{n-24+2i}$$ for $n=0,1,2, \dots ,24$, and $$P(X>n) = \frac{a_n}{12^n}$$

Finally, $$E(X) = \sum_{n=0}^{24} P(X>n) \approx 10.7821$$ which is in agreement with the Monte Carlo estimate given in a comment by Suzuteo.

Answer 2

Here is an approximate approach. If you make $n$ draws we will first consider the chance you have gotten at least three $1$s. We use a Poisson distribution to compute the probability with parameter $\lambda=\frac n{12}$. This is probably close, though $\frac 1{12}$ is not really small. The chance that you have exactly three $1$s is $\frac {\lambda ^3 e^{-\lambda}}{3!}$. Now we consider the chance of getting three of one number independent of the chance of getting three of another. If you know you did or didn't get three of one number that doesn't change the number of tries to get three of another very much. Intuitively, we want the chance of getting three of a specific number to be about $\frac 1{12}$. If we make twelve draws with a chance of $\frac 1{12}$ for each one, we have $\frac 1e \approx 0.368$ of failing on all of them, so about $0.632$ chance of getting at least one. We can solve for $\lambda$ in $$\frac {\lambda ^3 e^{-\lambda}}{3!}=\frac 1{12}\\\lambda \approx 1.17374\\n\approx 14$$ which seems amazingly small to me. I wrote a little program to simulate this using Python's random number generator and the average $n$ came out just below $11$, supporting the calculation. I was surprised how small it was.

Answer 3

I would like to complement the answer given by awkward. Let's consider sequences that contain only one symbol, e.g., the number $1$. If we define $a_n$ as the number of sequences of length $n$ that we can form such that no two symbols appear more than twice, then it follows that $a_0 = 1$ with the empty sequence, $a_1 = 1$ with the sequence $(1)$, and $a_2=1$ with the obvious sequence $(1,1)$. Evidently, $a_n = 0$ for $n>2$ (remember we only have one symbol). The associated exponential generating function is $$ g(x) =\sum_{n=0}^{\infty} \frac{a_n}{n!}x^n = 1 + x + \frac{1}{2}x^2. $$ One could say that we have imposed the $g$-structure on the set of sequences of length $n$ that only use the symbol $1$. Now, if we want to use two symbols, we can think that we have a set of $n$ elements $A = \{1,2,\ldots,n\}$, and we are trying to count the number of functions $f:A\to \{1,2\}$ such that after the assignment: $$ 1 \mapsto 2 \\ 2 \mapsto 1 \\ 3 \mapsto 1 \\ \vdots \mapsto \vdots \\ n \mapsto 2 $$ no more than two arrows point to an element in the range. Note that for any such valid assignment $f$, $A$ can be partitioned as $A=A_1 \uplus A_2$, where $A_1$ is the subset that gets mapped by $f$ to $1$, and $A_2$ is the subset that gets mapped by $f$ to $2$. Observe that $A_1$ has the $g$-structure mentioned earlier since we are using only one symbol. Similarly, $A_2$ has the $g$-structure. Since $A_1$ and $A_2$ are mutually exclusive, it follows by the multiplication principle for exponential generating functions that we can impose the $(g\times g)$-structure on $A$, and the associated exponential generating function is $$ G(x) = g(x)\cdot g(x).$$ Generalizing this to $12$ symbols, we have that the exponential generating function is $$ G(x) = g^{12}(x) = \left( 1 + x + \frac{1}{2}x^2\right)^{12} = \sum_{n=0}^{24} G_{n}x^n, $$ i.e., $$ G(x) = \frac{1}{4096} \, x^{24} + \frac{3}{512} \, x^{23} + \frac{9}{128} \, x^{22} + \frac{143}{256} \, x^{21} + \frac{1683}{512} \, x^{20} + \frac{1947}{128} \, x^{19} + \frac{1837}{32} \, x^{18} + \frac{11583}{64} \, x^{17} + \frac{124047}{256} \, x^{16} + \frac{17831}{16} \, x^{15} + \frac{8877}{4} \, x^{14} + \frac{30771}{8} \, x^{13} + \frac{93109}{16} \, x^{12} + \frac{30771}{4} \, x^{11} + 8877 \, x^{10} + \frac{17831}{2} \, x^{9} + \frac{124047}{16} \, x^{8} + \frac{11583}{2} \, x^{7} + 3674 \, x^{6} + 1947 \, x^{5} + \frac{1683}{2} \, x^{4} + 286 \, x^{3} + 72 \, x^{2} + 12 \, x + 1. $$ Now consider the random variable $X$ that produces the minimum number of draws necessary to get three times the same symbol from a list of $12$ symbols. Let's focus on the event $X>n$ for $n\in\{0,\ldots,24\}$. This means that up to draw number $n$, no symbol has appeared more than twice. Whatever happens after the $n$-th draw is irrelevant at this point. Hence, we are considering sequences of size $n$, where no symbol appears more than twice. The number of such sequences is given by $n! \cdot G_n$. Consequetly, $$ P(X>n) = n! \cdot G_n \cdot \frac{1}{12^n}, $$
where the factor $\frac{1}{12^n}$ is because the probability of getting each symbol is $\frac{1}{12}$, and the draws are independent. Lastly, $$ \begin{align} E(X) &= \sum_{n=0}^{24} P(X>n) = \sum_{n=0}^{24} n! \cdot G_n \cdot \frac{1}{12^n}\\ &= \frac{14175601924881625891}{1314732507698036736}\\ &\approx 10.78211867576140. \end{align} $$