I have N buckets, numbered 1 to N.
I draw k random integers, uniformly distributed in the range 1 to N, with replacement, and for each integer I drop a ball into the corresponding bucket. k can be any size; specifically it can be any value from 2 to N, or larger than N.
- What are the statistical characteristics (probability distribution, etc) of the numbers of balls in each bucket at the end?
- What are the statistical characteristics of the numbers of buckets with 0,1,...k balls?
This question arises from a need to measure the 'goodness' (in some sense) of a hashing algorithm. Given a sample of distribution of keys among buckets, I need a measure of where it lies on a scale from 'Very good' to 'Very bad', and to be able to work out things like 'what are the chances of more than x balls in a bucket given k and N?'
Obviously, from the way I've written this, and from the random names I've assigned to my variables, I have absolutely no statistical sophistication. Please be gentle; I want to learn. Please feel free, for example, to change the variable names to something more conventional, or anything else.