1
$\begingroup$

In an urn there are $a$ indistinguishable red balls and $b$ indistinguishable blue balls. Every round, you take one ball in random from the urn. If this ball is blue, game over. If this ball is red, you put it back into the urn and put an extra indistinguishable red ball in (so the urn has an extra red ball than before). Let $E_{a,b}$ be the expected number of total rounds of games.

Suppose we know the total number of balls $N = a+b$ but don't know the exact number of $a,b$. Let $a$ follow an uniform a prioir distribution in set $\{ 1, ..., N-1 \}$. On which round, if you draw a red ball, you have are more than 90% certain that $E_{a,b}$ is infinity?

I guess the first step would be trying to derive $E_{a,b}$ in some way. $E_{a,b} = \frac{a}{b+a} (E_{a+1,b} + 1) + \frac{b}{a+b}$. Then $(a+b)E_{a,b} = a E_{a+1,b} + a + b$, so $E_{a+1,b} = \frac{a+b}{a}E_{a,b} - \frac{a+b}{a}$. Obviously $E_{0,b} = 1$, but this looks wrong..

$\endgroup$
1
  • $\begingroup$ Can you find an initial condition, like $ E_{0, b }$? $\endgroup$
    – Calvin Lin
    Apr 18 '20 at 21:22
0
$\begingroup$

This calculation of $E_{a,b}$ will get you started. On the $n-$th round, the urn contins $a+n-1$ red balls and $b$ blue balls. The probability that the $n-$ th round is the last is $\frac{b}{a+b+n-1}$. The only way of playing the $n-$th round is by surviving all the previous rounds.Thus the probability that the game ends in exactly $n$ rounds is $$E_{a,b}=\frac{a}{a+b}.\frac{a+1}{a+b+1}...\frac{a+n-2}{a+b+n-2}.\frac{b}{a+b+n-1}$$ $$=\frac{(a+n-2)!(a+b-1)!b}{(a-1)!(a+b+n-1)!}$$The expected number of rounds is $$\sum_{n=1}^{\infty}\frac{(a+n-2)!(a+b-1)!bn}{(a-1)!(a+b+n-1)!}$$ $$=\frac{b(a+b-1)!}{(a-1)!}\sum_{n=1}^{\infty}\frac{(a+n-2)!n}{(a+b+n-1)!}$$

$\endgroup$
1
  • 1
    $\begingroup$ I think $E_{a,b}=$ should be at the start of the second displayed equation, not the first, which gives a probability, not the expected number of rounds. (Also, I think it's worth mentioning that the probability in the first equation telescopes, so for large $n$ it's approximately the first $b$ numerators times $b$ over $n^{b+1}$, so the series converges for $b\ge2$.) $\endgroup$
    – joriki
    Apr 18 '20 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.