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.
 A: 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
A: 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.
