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?

  • 1
    $\begingroup$ 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 ? $\endgroup$ Jul 25 '10 at 23:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – shreevatsa
    Jul 26 '10 at 1:09
  • $\begingroup$ 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. $\endgroup$ 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$.


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.

  • $\begingroup$ 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? $\endgroup$
    – shreevatsa
    Jul 26 '10 at 5:58
  • $\begingroup$ I added some references and meta-references. $\endgroup$
    – T..
    Jul 26 '10 at 7:14
  • $\begingroup$ I think what you want is Example III.10 in Flajolet and Sedgewick (which, by the way, is freely available online). $\endgroup$ Jul 26 '10 at 7:32
  • $\begingroup$ 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. $\endgroup$
    – T..
    Jul 26 '10 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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