Posted here too.
Hello all,
I have a probability problem that I can't figure out. I've asked several math-savvy friends, and many have come up with some possible solutions (that by their own admission were just guesses), but none of the solutions has worked out right. So I figured some smart people on the internet might provide the answer. Here goes:
Let's say you have 'n' different items in a bowl. You reach in, pull one out at random, and then put it back in. You repeat this procedure 'm' times. Assume all items have an equal chance of being pulled.
I'm looking for a probability formula. What I need is the probability that after 'm' pulls, you will have pulled every item at least once.
Now common logic tells us basically how the formula should act:
Obviously, if m < n, the probabilty would be zero. You can't get one of each item if you don't make enough pulls to get them all at least once.
In the case of m = n, the probability is pretty easy to figure out, since you know you have to get a unique item for each pull. I calculated that in this case (where m = n) the probability would be:
P = [(n-1)!]/[n^(n-1)]
Lastly, for cases where m > n, the probability would have to be greater than in the formula above. And as m approaches infinity, P would have to approach 1. For example, if you only have like 4 items in the bowl and you make a billion pulls, it's very improbable that you wouldn't get each of the four items at least once.
So I know how the formula should act, but I don't know how to figure out what the exact forumla is. Anyone want to take a stab at it?
-Divinius
P.S. My one friend says it makes more sense to think of it as rolling 'm' number of 'n'-sided dice (evenly weighted). Find the probability that you have at least one die showing each possible side. I like the fruit bowl better, but whatever...