In a comment to my previous post, Anthony Widjaja To points out an ambiguity in the term “probabilistic proof”. There are three senses I can think of:
Erdös’ “Probabilistic Method” in Graph Theory
This method is not related to what I was talking about before, because it gives a deductively valid proof of the result, though it uses facts about probabilities in intermediate stages. An example is the following proof of a bound for Ramsey numbers. (Recall that the Ramsey number R(k) is defined as the least n such that among any n people, there is a group of k such that every member of the group knows every other, or no member of the group knows any other. R(2)=2,R(3)=6,R(4)=18 and other Ramsey numbers are unknown.)
Represent the people as a set of vertices, with a red edge between them if they know each other, and a blue edge if they don’t. We want to find n such that for any coloring of such a graph, there is either a set of k vertices all of whose edges are blue, or such a set all of whose edges are red. So color such a graph randomly, with each edge having probability 1/2 of being blue, and 1/2 of being red. For any given set of k vertices, there are k(k-1)/2 edges between them, so it has probability 21-k(k-1)/2 of being monochromatic. If n=R(k), then the probability of there being such a monochromatic subgraph must be 1. Therefore, the number of such subgraphs must certainly be at least 2k(k-1)/2-1, so that the probability of at least one of them being monochromatic can be 1. So if R(k)=n, then n must be such that n choose k≥2k(k-1)/2-1.
More complicated applications of this method start with probabilities other than 1/2, and often make use of more advanced concepts in probability, like variance, Chebyshev’s Inequality, and the like. But they all end up giving deductive proofs of the result.
Probabilistic Proofs of Primality
The methods that Don Fallis was talking about, which I discussed in my previous post, are proofs that don’t give a guarantee that the result holds. For instance, Michael Rabin proved in 1980 that for any n, if it is not prime, then at least half the numbers less than it have a certain property that is easy to check. Therefore, if we check 20 of these numbers (say, chosen by some pseudo-random number generator, seeded by the nanoseconds reading on the computer clock when the user hits a key 20 separate times), then if n is composite, we only have about a 1 in a million chance of getting a false positive for being prime. On the other hand, if it’s prime, then we are guaranteed to get a positive result.
Note that many deductive proofs that mathematicians accept are so complicated that there’s far more than a 1 in a million chance that the proof went wrong somewhere, even if the result is true.
Inductive Generalizations from Instances
The Goldbach Conjecture, stating that every even number (except 2) is the sum of two primes, is widely believed to be true. However, the best evidence that I know of in favor of it is the fact that people have searched for counterexamples and shown that there are none less than 1011. (There are other related results, like the fact that every even number is the sum of no more than 300,000 prime numbers, and that every even number is the sum of a prime and a product of at most two primes, according to this site.)
Both of these last two methods may be useful for raising one’s subjective credence in some result on a Bayesian account of mathematics (suitably modified to avoid the fact that standard Bayesian epistemology implies logical omniscience). After all, for any n I should assign some probability to there being a counterexample below n if the theorem is false. As n goes to infinity, it seems that this probability should go to zero. So for any epsilon, there is some finite number of cases to check that would reduce my subjective probability in the theorem below epsilon. Similarly, for the primality result, if I assign some probability p to n being composite, and I check k numbers and find no witnesses, then I should assign probability p2-k to the number being composite. Choosing k appropriately lets me make this posterior probability as small as I like.
The difference between these two cases is that the method is purely subjective for the verification of Goldbach’s Conjecture, while there are some relatively objective bounds one can give in the case of primality. By choosing the potential witnesses to check using the nanoseconds reading on the computer clock, we can reasonably suggest that the chosen numbers won’t follow any pattern related to n. There is probably some complex relationship between n and the precise distribution of Rabin witnesses for compositeness, and if we used some mathematical formula to choose the potential witnesses, then we might be unlucky and use a formula that just so happens to always give witnesses, so the probability of not being a witness wouldn’t be 1/2 each time. By choosing the numbers using independent readings of the nanoseconds reading, we can be justified in regarding each of these events as independent, giving us a conditional probability of a false positive given that n is compositen of 1/2k. So in some relatively objective sense, we can measure the likelihood, and see that we have very good evidence of primality.
We can also get a decently objective value for the prior probability that n is prime, using the Prime Number Theorem. This theorem states that there are approximately n/log n primes less than n, and we can use this to estimate that n has a probability approximately 1/log n of being prime. This is more questionable than the previous calculation, because, for instance, we know that no even number (other than 2), and no number that ends with 5 or 0 (except 5) is prime, so if n is not of this form, then it is more likely to be prime. So we don’t have a very good methodology for establishing a prior probability that n is prime.
But we can estimate the likelihoods in some fairly objective way using this method, which is why it’s much better than the method of verification for the Goldbach Conjecture. After all, someone might provide a relatively straightforward proof that if there is a counterexample to the Goldbach Conjecture, then it is at least 10100, and then the empirical evidence that we have already would be of no use. But it’s unlikely that someone will demonstrate a correlation between the timing of my keystrokes and the witnesshood of numbers less than n, so we can at least get a likelihood there.
There’s a sense in which a deductive proof only gives a likelihood as well, since there is a certain chance of it being wrong. However, again we have no good means of estimating the likelihood of producing such a seemingly correct (but actually incorrect) proof given that the theorem is true, or given that it’s false. Of course, the same worry arises with the probabilistic proof of primality, so the difference between the two is only in this extra possibility of error, which can be bounded in a rational way. But it’s interesting to note the advantages that this type of proof has over other non-deductive means of verification.