# Looking for a probability distribution

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 about for some hours, searching the web and asking some math students we couldn't find a solution.So do you know a probability distribution for this problem?

• Can you elaborate more on what you mean by "distinct hash values" ? Do you refer to the number modulo 2 or to the overall value of the binary-represented integer by the array ? – M. Alaggan Jul 25 '10 at 23:28
• I presume the question means how many distinct positions have 1s in them. To restate this as a balls-and-bins question: in each round, you pick a random bin and choose to add a ball or not. What is the distribution of the number of nonempty bins? The more crucial thing missing in the question is the number of rounds. – shreevatsa Jul 26 '10 at 1:09
• shreevatsa was right. I meant how many distinct positions have ones in them. The number of rounds we thought of is something between 50000 and 500000. – Jens Kubieziel Jul 26 '10 at 21:10

This is equivalent to (among other names) the Coupon Collector problem. Your are asking about the distribution of the number of coupons collected after $t$ steps, when the total number of possible coupons is $n$.
• The Wikipedia article doesn't say anything about the distribution of the number of coupons collected after $t$ rounds... do you know of a reference which does? – shreevatsa Jul 26 '10 at 5:58
• III.10 gives the Poisson answer $1 - \exp(-t/n)$ when the ratio is held constant, but other asymptotic regimes are also of interest especially in hashing problems. Birthday problem is when $t = O(n^{1/2})$ and one gets statistics of the number of collisions. For $t=n^k$ with $1/2 < k < 1$ the number of collisions is larger (and unbounded) so things could get more complicated. – T.. Jul 26 '10 at 8:09