# Urn with increasing number of distinct balls

Suppose we have an urn that initially has only one labelled ball inside. At each time step, we flip a biased coin with probability $p$ $(\in(0,1))$ of landing on heads and probability $1-p$ of landing on tails. If we get heads, we add a new ball into the urn that has a distinct label from all the other balls. If we get tails, we draw a random ball from the urn, note its label, then put it back. What I would like to know is whether or not, w.p. 1, there will be a ball that will be drawn infinitely often from the urn as we indefinitely continue this experiment.

My hunch tells me that such a ball does exist a.s., but I can't seem to prove it. I tried using Borel-Cantelli on the sequence of events in which the initial ball is drawn at time $n$. However, I found the sum of the probabilities of those events to be infinite, so Borel-Cantelli can't help us (the events are neither independent nor monotone increasing).

If you have any help to offer me for this problem, I'll very much appreciate it.

• How can a ball come back to the urn once it is drawn? Jul 14, 2015 at 19:58
• Whoops, forgot to say that the drawn ball gets put back into the urn. It's corrected now. Jul 14, 2015 at 20:51

A solution similar to Conrado's works. Replace the process by one in which a ball is added after every coin flip, irrespective of the result. Clearly this does not increase the probability of drawing the first ball at any point. Now the probabilities of drawing the first ball are all independent, and are exactly given by the bound that Conrado gave for the original probabilities. Thus, by the second Borel-Cantelli lemma, the event of choosing the first ball almost surely occurs infinitely often.

• Ah, so just a simple coupling was needed. Thanks! Jul 15, 2015 at 19:02
• @srnoren: It seems more like a decoupling to me :-) Jul 15, 2015 at 22:46

The number of balls in the urn after $n$ tosses is less then or equal to $n + 1$

The event of choosing the ball $1$ (the first ball in the urn) in the round $n$ ($A_n$) (after $n-1$ tosses) is therefore given by

$$\chi_{\text{tails}} \frac{1}{\#\{\text{balls in the urn at round } n\}}$$

$$P(A_n) \geq \frac{1 - p}{n}$$

if $1 - p>0$ $\sum_n P(A_n) = \infty$ and therefore the event picking the ball $1$ occurs infinitely often (by borel cantelli). So you are right, almost surely the ball $1$ will be drawn infinitely often.

If $1 - p = 0$ the you won't pick any ball at all.

Note: check out for Borel-Cantelli lemma https://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma#Converse_result

• Correct me if I'm wrong, but doesn't Borel-Cantelli say the converse, that if the sum is finite then the ball will not be picked infinitely often? Jul 14, 2015 at 21:19
• No, consider the event $A_n = \Omega$ $\sum_n P (A_n) = \sum_n 1 = \infty$ the event $\Omega$ occurs infinitely often Jul 14, 2015 at 21:20
• That's obviously true, but how does it relate to my comment on what the content of Borel-Cantelli is? Jul 14, 2015 at 21:21
• If the events $A_n$ are independent then borell Cantelli lemma holds the other way arround, the solution is correct, once we choose a ball at each round independently. Jul 14, 2015 at 21:29
• Yes, I just posted an answer that uses this. Jul 14, 2015 at 21:29