Seeking a probability circulation

Lately I reviewed a trying out a close friend. Think we start an arbitrary experiment. In the beginning there is an array with dimension $100,000$, ready to $0$. We compute at each round an arbitrary number modulo $2$ and also select one arbitrary placement because array. If the number in the array is $1$, absolutely nothing is transformed and also or else the pre-computed value is set. The inquiry is: the amount of distinctive hash values would certainly we have included $1$%, $5$%, $50$%, $95$%, $99$% of all instances?

Instance: $4$ rounds with array of dimension $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 an in some way straightforward trouble, yet after assuming for some hrs, looking the internet, and also asking some mathematics pupils, we could not locate a remedy. Do you recognize a probability circulation for this trouble?

Statement: Was additionally uploaded on Math Overflow and also obtained its solution there.

2019-05-07 02:55:03
Source Share
Answers: 1

As addressed by T. on MathOverflow.

This amounts (to name a few. names) the Coupon Collector trouble. Your are inquiring about the circulation. of the variety of promo codes accumulated. after t actions, when the complete number. of feasible promo codes is n.

ADDED : this and also connected circulations. are additionally researched under various other names. such as Birthday Problem, arbitrary. mappings, and also arbitrary hashing. Kolchin - Sevastyanov - Chistyakov Random. Appropriations , Knuth The Art Of Computer. Shows, vol. 2 , and also Flajolet &. Sedgwick Analytic Combinatorics all. review these troubles and also might have. the specific asymptotics of the. circulation you are seeking.

III.10 in Flajolet and also Sedgewick offers. the Poisson solution $1−\exp(−t/n)$ when. the proportion is held constant, yet various other. asymptotic regimens are additionally of. passion specifically in hashing. troubles. Birthday celebration trouble is when. $t=O(n^{1/2})$ and also one obtains data. of the variety of crashes. For t = n ^ k. with 1/2.

2019-05-08 08:16:52