Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $D$ different kinds of candy, and $C$ children come to buy them. Each child purchases one package of candy. What is the probability that a given variety of candy is chosen by no child?

I am thinking of this as, there are $k$ locations(Candies) in which $n$ items(Children) are being hashed to. What is the probability that one of the locations have nothing hashed to it?

I also already know that the expected number of kinds of candy chosen by no child is $D(1-(1/D))^C$

Any help would be greatly appreciated!

share|improve this question

1 Answer 1

If you know that the expected number of kinds chosen by no child is $D(1-\frac 1D)^C$ you can use the linearity of expectation to conclude that the chance one given candy is chosen by no child is $(1-\frac 1D)^C$ because each kind of candy has the same probability not to be chosen.

Usually the argument goes the other way. Pick a particular candy. The chance that one child doesn't pick it is $(1-\frac 1D)$ The chance that all the children don't pick it is the product of $C$ of these, $(1-\frac 1D)^C$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.