Approximating Streaming Data with Sketching - Real-Time Analytics - page 415

Finally, the probability that at least two people share a birthday is
simply 1-P(nobody shares):
The final equation contains factorial functions that are expensive to
compute. To make the calculation easier, an approximation is often
used. The equation (365-n-1)/365 can be rewritten as (1 - (n-1)/365)
and the fact that ex is approximately 1+x when x is much smaller than 1
(via the first order Taylor expansion of e x ). Combining the two you see
that e -(n-1/365) is approximately equal to (1-(n-1)/365). You can then
rewrite the probability as:
Knowing that the sum of integers between 1 and n-1 is n×(n-1)/2
further simplifies the formula to:
If n is large enough, n*(n-1) can be replaced with the further
approximation n 2 because the relative difference between n and n-1 will
be very small. Setting this equation to be 0.5 and solving for n yields the
famous result of 23 people needed to have a better than 50 percent
chance of sharing a birthday.
Working with Sets
Sketch algorithms fundamentally deal with sets, particularly approximating
the size of a set, which is called cardinality estimation. This section reviews
some aspects of “naïve set theory” that is useful when using or analyzing the
algorithms discussed in the next several sections.
A set is simply a collection of distinct elements. A set can be empty, which
is called the empty or null set. Uppercase letters such as A or B are usually
used to denote sets. The null symbol (Ø) is used to denote the empty set.