Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Remark: Was also posted on Math Overflow and got its answer there.

share|improve this question
2  
FYI, I wouldn't post this on MO. I made the same mistake, thinking it was the StackOverflow for Math. If you read the faq it is not. –  Jonathan Fischoff Jul 25 '10 at 23:11
    
"The question is: how many distinct hash values would we have added in 1%, 5%, 50%, 95%, 99% of all cases?" I'm afraid I don't understand the question - there are no hash values involved here. Also, what do you mean by "what would we have added" and "in 1% of cases?" Are you asking the average number of values needed to generate to fill 1% of the array, or the average percent of the array filled after generating x values? –  BlueRaja - Danny Pflughoeft Jul 25 '10 at 23:27
2  
It is not clear to me what your question is asking. It sounds like you want to choose a random position in the array, and if it is a 0, change it to a 1 with 50% probability. Then you want to find the distribution for the number of iterations it takes until the array contains n% 1's? Is that correct? –  Larry Wang Jul 26 '10 at 0:22
2  
This question has been answer-accepted on MO. What to do on this side? Someone copy the MO answer or just close it? –  KennyTM Aug 2 '10 at 8:03
1  
From my point of view closing it would be the best alternative. –  qbi Aug 2 '10 at 11:57
show 1 more comment

1 Answer

up vote 2 down vote accepted

As answered by T. on MathOverflow.

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.

III.10 in Flajolet and Sedgewick 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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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