Question

. Suppose each person gets a random hash value from the range [1...n]. (For the case of birthdays, n would be 365.) Show that for some constant c1, when there are at least c1 √ n people in a room, the probability that no two have the same hash value is at most 1/e. Similarly, show that for some constant c2 (and sufficiently large n), when there are at most c2 √ n people in the room, the probability that no two have the same hash value is at least 1/2. Make these constants as close to optimal as possible. Hint: you may use the fact that e −x ≥ 1−x and e −x−x 2 ≤ 1−x for x ≤ 1 2 . You may feel free to find and use better bou

Answer 1

Answer:

The birthday paradox :

How many people must there be in a room  before there is a 50% chance that two of them  were born on the same day of the year?

The answer is surprisingly few

The paradox is that it is in fact far fewer  than the number of days in a year, or  even half the number of days in a year

Explanation:

An analysis using indicator  random variables

We use indicator random variables to provide a  simple but approximate analysis of the birthday  paradox

For each pair  ( i, j )  of the ݇k people in the room,  define the indicator random variable  X ij, for

            1 ≤ i ∠ j ≤ k ,       by

X ij  =   I  {i and j have the same birthday}

       =   {1    i and j have the same birthday

             0   otherwise

Once birthday bi for i is chosen, the probability  that  bj is chosen to be the same day is     1/n,

                               where  n = 365

                    E [ Xij ]  =  Pr { i  and j have the same birthday =  1/n

Let  X  be a random variable counting the number  of pairs of individuals having the same birthday

                     k               k

              X = ∑               ∑            Xij

                    i = 1          j =  i + 1

Taking expectations of both sides and applying  linearity of expectation, we obtain:

Е [ X ] = Е  [  k              k                        ]            k           k

                     ∑             ∑               Xij         =       ∑           ∑          Е [Xij ]

                 i = 1           j =  i + 1                              i = 1      j =  i

           =  ( k )  1 = k ( k - 1 )

                 2   n        2n

When       k ( k - 1 ) ≥ 2 ,       the expected number of pairs of people with the same birthday is at least  1

Thus, if we have at least    √ 2n + 1     individuals in a  room, we can expect at least two to have the  same birthday.

For   n = 365,     if     k = 28,       the expected number of  pairs with the same birthday is

                       (28 · 27) / (2 · 365) ≈ 1.0356

With at least 28 people, we expect to find at  least one matching pair of birthdays

Analysis done using only probabilities gives a different  exact number of people, but same  asymptotically:

                                    Θ ( √n )