9.2 PROBABILISTIC ALGORITHMS 243hits = 0
for i=1 to dartCount do
x = uniform(0, 1)
y = uniform(0, 1)
if y ≤ f(x) then
hits = hits + 1
end if
end for
return hits/dartCount
Probabilistic Counting
A classic problem is to bet that in a room of 25 randomly chosen people at least
two of them will have the same birthday. Although this would seem a foolish
bet, in reality the odds are greater than 56% that this will happen. In general,
there are N! / (Nk)! ways to choose k distinct objects from a set of N
objects if order matters. There are Nk different ways of choosing k objects if
repetitions are allowed. Putting all of this together means that the chance of
winning the bet is 1 365! / (340! * 36525 ). In reality, the chances are even
better because this equation does not account for the fact that births are not
uniformly distributed through the year. This number is not easy to calculate,
nor it is easy for us to figure out the reverse problem: Given a set of N ele-
ments, how many choices must you make before you will pick an element for
the second time? In other words, given 365 days in the year, how many differ-
ent people must you have for there to be a good chance that at least two people
have the same birthday. Because it's difficult to calculate, the following algo-
rithm will approximate the number:
ProbabilityCount( N )
k = 0
s = {}
a = uniform( 1, N )
repeat
k = k + 1
s = s ∪ {a}
a = uniform( 1, N )
until a ∈ s
return k
The function will randomly generate numbers from 1 to N until it generates
a number for the second time. To get more accurate results, this function could