2110712 Problems
1 cardinality of very large sets
X is a finite set with size n. n is very large that it is
impossible to count each element in X. To find the cardinality of
X we use uniform random sampling of elements in X with the following
algorithm:
card
x
k = 0
S = empty
a = uniform x
repeat
k = k + 1
S = S union {a}
a = uniform x
until a is-in S
return k^2/2
Prove that card x is an unbiased estimator of n. The expected
running time of card x is big-theta( sqrt(n)) if uniform x runs
at constant time.
Hint: n = sqrt m where m is the number of elements
sampled from X before there is a repeat.
It will help if you solve the following two related questions first:
1.1 if the size of a hash table N = m^2. where m is the
number of element in the table. Show that there is significant
collision when assume hash by uniform random.
1.2 There are 25 persons in a room. What is the chance that
two persons have the same birthday?