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? 



Looking for a probability distribution
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$. 


<http://en.wikipedia.org/wiki/Coupon_collector%27s_problem>


ADDED: this and related distributions are also studied under other names such as Birthday Problem, random mappings, and random hashing. Kolchin-Sevastyanov-Chistyakov *Random Allocations*, Knuth *The Art Of Computer Programming, vol. 2*, and Flajolet & Sedgwick *Analytic Combinatorics* all discuss these problems and may contain the precise asymptotics of the distribution you are looking for. 


