# Randomly drawing balls from an urn and putting them back in

I'm a little rusty on my probability theory, so this might be an easy question (or not). I'm interested in this for a personal project, not homework. Consider an urn with $N$ balls, each distinguished by a number $1...N$. I pick out balls from the urn indefinitely, for each pick/time step $t$ I record the ball extracted, and put it back in the urn. Given some integer value $c$, what is the probability that at time/pick $t$, I have picked any single/distinct ball for the $c$'th time?

To be concrete - suppose there are $N=1000$ balls, and $c=4$. I'm interested in the probability that at time $t$ I've picked the same ball (any one of them, not a specific ball) $4$ times. Obviously after $N*(c-1)+1=3001$ picks this will have happened surely, but this is likely to happen before, what is the probability for every time step $t$?

Thanks a lot for the help!

• I'm not sure if this is a satisfactory modification, but it might be easier to compute the expected number of draws until you get $c$ of the same ball. – user2566092 Sep 14 '15 at 17:48
• Thanks for the comment, but I'm afraid that won't give me what I'm looking for... – user126743 Sep 14 '15 at 18:33

If $N$ is large and you make enough draws, then the number of draws $c_i$ of each ball $i$ are essentially independent variables (even though their sum is fixed). Furthermore, if $N$ is large, the numbers $c_i$ are approximately Poisson distributed, with rate parameter $\lambda (t) = t / N$. So you can compute the Poisson probability $p$ that one $c_i$ is less than $c$, and then your probability is approximately $1 - p^N$. I'll do some simulations when I get some time later to show how the approximated probability matches up with the exact probability.
• You can imagine enumerating the possible states, creating a matrix $M$ to capture the state transition probabilities and then use compute $M^t$ to give you the distribution of states after $t$ draws. Unfortunately, for anything but small $c$, $N$ this will be impractical to do by hand. But it be a way to get a start. – MattBecker82 Sep 15 '15 at 7:35