3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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$
    – Mohammad Alaggan
    Commented Jul 25, 2010 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
    Commented Jul 26, 2010 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$
    – Jens Kubieziel
    Commented Jul 26, 2010 at 21:10

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Jul 26, 2010 at 5:58
  • $\begingroup$ I added some references and meta-references. $\endgroup$
    – T..
    Commented Jul 26, 2010 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$
    – Qiaochu Yuan
    Commented Jul 26, 2010 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..
    Commented Jul 26, 2010 at 8:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .