Probabilistic algorithm
A separate article deals with the probabilistic method, which should not be confused with the topic of this article.
In mathematics, a probabalistic algorithm is an algorithm that with very high probability gives a correct answer, but not with certainty. Such an algorithm may run much faster than one that is sure to give the right answer in every case, but it may also take longer than such an algorithm.
One such algorithm, created by Michael Rabin, relies on a binary relation between two positive integers k and n that can be expressed by saying that k "is a witness to the compositeness of" n. It can be shown that
- If there is a witness to the compositeness of n, then n is composite
(i.e., n is not prime), and
- If n is composite then at least three-fourths of the natural numbers less than n are witnesses to its compositeness, and
- There is a fast algorithm that, given k and n, ascertains whether k is a witness to the compositeness of n.
If one randomly chooses 100 numbers less than a composite number n, then the probability of failing to find such a "witness" is 1 - (3/4)100, so that for most practical purposes, this is a good primality test. If n is big, there may be no other test that is practical. The probability of error can be reduced to an arbitrary degree by performing enough independent tests.
If, using such a method, the probability of error is 2-1000, the philosophical question arises: is this a proof? After all the probability of error is distinctly smaller than the probability of an error in the reader's computer, or the reader themselves making an error in reading a proof - what does it mean in real terms to consider this small a probability?
If that does not seem extreme enough to be perplexing, consider a proof with an error probability of 2-1000000: the user only has to leave the computer running the probabilistic algorithm running a little longer. At this level, the odds against error are not only astronomically, but also cosmologically vast.
The term probabilistic method refers to a method of proof that uses probability to show the existence of something with certain properties. Although the proof uses probability, the final conclusion is determined for certain, without any possible error.
One way of doing this is by considering a randomly selected thing from a finite sized universe. If the probability that the random thing satifies the properties is greater than zero, then this proves the existence of a thing that satisfies the properties. It doesn't matter if the probability is astronomically small; any probability strictly greater than zero will do. (Also, showing that the probability is zero can be used to prove the non-existence of such an object).
Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value.