244 OTHER ALGORITHMIC TECHNIQUES
be called a number of times, averaging the answers it returns. For our birthday
example (N = 365), this function would give us an answer of about 25.■ 9.2.2 Monte Carlo Algorithms
Monte Carlo algorithms will always give an answer, but the probability that the
answer is correct increases the longer the algorithms run. These algorithms can
occasionally return an incorrect answer. Monte Carlo algorithms are called p-
correct when they return a correct answer with probability of p (1/2 < p < 1).
If there is more than one correct answer for a given input, a Monte Carlo algo-
rithm is called consistent if it returns the same correct answer each time.
There are two ways to improve the results of a Monte Carlo algorithm. The
first is to increase the amount of time it runs, and the second is to call it multi-
ple times. The second option can only be used if the Monte Carlo algorithm is
consistent. In this case, we would make several calls to it and choose the answer
that appears most frequently. An algorithm to do this would be something like
the following:
Monte3( x )one = Monte(x)
two = Monte(x)
three = Monte(x)
if one = two or one = three then
return one
else
return two
end if
In this algorithm, the first solution will be returned if it appears at least twice.
If, however, it doesn’t, we can just return the second answer because it either
matches the third answer, or all three are different and so it doesn’t matter.
Because Monte Carlo algorithms have a greater than 50% chance of returning
the correct answer, it is unlikely that all three will be different. The process in
Monte3 will improve a consistent 80% Monte Carlo algorithm to about 90%.
This is not always the best way to approach the problem of improving prob-
ability. Consider a Monte Carlo decision algorithm that is biased in that it is
100% correct if it returns the answer false, and it only makes mistakes if it
returns true. In other words, if the algorithm returns false, the answer is always
correct, but if it returns true, the answer may be true or false. This means that
any answer of false should be returned immediately, and repeated calls to the