Suppose we hash the elements of a set S having 20 members to

Suppose we hash the elements of a set S having 20 members, to a bit array of length 99. The array is initially all-0\'s, and we set a bit to 1 whenever a member of S hashes to it. The hash function is random and uniform in its distribution. You may assume that 99 is large.
1a. What is the expected fraction of 1\'s in the array after hashing? Give your answer to three decimal places.
1b. What is the expected fraction of 0\'s in the array after hashing? Give your answer to three decimal places.

Solution

To derive the correct formula, start by observing that the probability of any one element not hashing to a particular bit is 1-1/99, so the probability that no element hashes to a particular bit is p= (1-1/99)²⁰. Since 99 is large so.

The fraction of 0\'s is e^-20/99   using lim n??(1+1/n)ⁿ=e

and the fraction of 1\'s is 1-e^-20/99