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