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!

  • $\begingroup$ 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. $\endgroup$ – user2566092 Sep 14 '15 at 17:48
  • $\begingroup$ Thanks for the comment, but I'm afraid that won't give me what I'm looking for... $\endgroup$ – 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.

  • $\begingroup$ Wow cool thanks, I was hoping for something a little more straight forward though, don't you think I can find a closed analytical solution? $\endgroup$ – user126743 Sep 15 '15 at 5:07
  • $\begingroup$ Anyways, I'd more than be happy to see simulations, that would be great... I might run them myself... $\endgroup$ – user126743 Sep 15 '15 at 5:08
  • $\begingroup$ 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. $\endgroup$ – MattBecker82 Sep 15 '15 at 7:35

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.