numbers, and in particular randomized, or probabilistic algorithms.
These are problem-solving methods that are not guaranteed to give you
the right answer, but have a very high probablility of giving you the
right one. At first you might think it's dangerous to rely on such
things, but by running repeated trials of a random algorithm, we can
make the odds astronomical against being wrong.
The reason this happens is due to a basic law of probability: to
find the chance of multiple independent events occurring, multiply the
probability of each of them. So, let's assume we have a randomized
algorithm that has a 1 in 4 chance of getting the wrong answer. It
doesn't sound so good at first. But if we run it twice, the chance of
being wrong is 1/4 times 1/4, or 1/16, a much smaller number. If we
run it <n> times, the chance of being wrong is 1 over 4 to the nth
power. And as we have seen in previous discussions about
exponentials, this number can get very large very quickly.
As an example of such an algorithm, think about trying to figure
out if some large number is prime, having no factors other than itself
and 1. This sounds abstract, but actually plays an important role in
modern encryption technology. It's a lot easier to prove that a
number is composite, or non-prime. The Miller-Rabin primality
algorithm takes advantage of noticing that for sufficiently large
numbers, 3/4 of the numbers below them are 'witnesses' to their
compositeness: choose one of these numbers, plug it into a special
equation, and if your starting number was composite, you will find
out.
So suppose you choose 100 random numbers, and none of those 100
are able to prove the compositeness of your input. We can safely
conclude that the number is prime, even though we have just thrown a
bunch of random darts rather than thoroughly testing it. The
chance that the number really is composite and none of the random
numbers were a witness is only 1/4 to the 100th power, an
astronomically small chance, equal to around 6 * 10 to the negative 61st
power.
You may start whining at this point: "But I'm not *sure* that we
got the right answer!" But think about the probabilities of other
events in your life. This probability of getting a wrong answer from
the algorithm is infinitesmal compared to the probability of getting
into a bus crash on your way to work to check the answer. Not only does
it dwarf your odds of a bus accident, which is about 2 * 10 to the
negative 9th power; there is virtually guaranteed to be a meteor
crashing into your house, probability 5 * 10 to the negative 15th
power, long before you get a wrong primality answer
from this algorithm. Not to mention the fact that you are way more
likely to mess it up by entering wrong data or having faulty computer
hardware than by a failure of the algorithm. So, if you are willing
to choose your actions in life based on the reasonable assumption that
you probably won't be killed by a bus or a meteor tonight, you should
be much more willing to rely on this algorithm as a primality test.
In fact, there are efficient fully deterministic tests known for
primality-- but the randomized ones work so well that most authors of
encryption software prefer them anyway. So, we can see that solving
problems with a roll of the dice can sometimes be just as good, for
all practical purposes, as methods that get a so-called "guaranteed"
answer.
And this has been your math mutation for today.
No comments:
Post a Comment