Recently I discussed an experiment with a friend. Assume we start a random experiment. At first there is an array with size $100,000$, all set to $0$. We calculate at each round a random number modulo $2$ and select one random position in that array. If the number in the array is $1$, nothing is changed and otherwise the pre-computed value is set. The question is: how many distinct hash values would we have added in $1$%, $5$%, $50$%, $95$%, $99$% of all cases?
Example: $4$ rounds with array of size $10$:
Array Position random number
[0,...,0] 5 0
[0,...,0] 7 1
[0,...0,1,0,0,0] 6 1
[0,..0,.1,1,0,0,0] 6 0
[0,..0,.1,1,0,0,0] 2 0
First we considered this a somehow simple problem, but after thinking for some hours, searching the web, and asking some math students, we couldn't find a solution. Do you know a probability distribution for this problem?
Remark: Was also posted on Math Overflow and got its answer there.