Role of statistical estimation in formal proof

Question

Consider the following scenario: There is some mathematical constant $c$ that you want to compute. You don't have a formal proof for any particular value of $c$, but you have some sound statistical procedure that will determine $c$ (up to a certain error, perhaps) with high probability. For example, $c$ is the value of some integral and you estimate it with Monte-Carlo sampling.

Now, this is not as rigorous as a Hilbertian proof of the value of $c$. But it is also much more rigorous than a heuristic. One can say confidently, for instance, that your statistical procedure determines the correct value with an exponentially high probability.

(I think you need to be careful of Bayesian reasoning; you should not conclude that the value of $c$ is any particular value with high probability, as usually in the Bayesian paradigm we assume that the subject is capable of perfect reason in the presence of data, and a perfectly rational reasoner would probably deduce $c$ from a Hilbertian proof)

Could, or should, use of statistical procedures be considered valid rigorous reasoning? This scenario is not at all far-fetched.

Answer 1

It's not clear to me what you mean by "valid rigorous reasoning". A statistical argument is certainly worse than a rigorous proof, and there are big philosophical differences between them. For example, a statistical argument depends on having a good source of randomness, and the quality of that source is difficult to verify after the fact, so independent replication becomes important. One might in principle be able to convert a statistical argument into a rigorous proof using a high-quality pseudorandom generator, but that's a different question. (Of course the generator would have to satisfy strong restrictions, and we generally don't yet know enough about complexity theory to make this kind of argument work.)

On the other hand, principled statistical arguments are certainly convincing, and they are the next best thing to rigorous proofs. People use them all the time, for example with probabilistic primality tests. In theoretical computer science, there's a theory of probabilistic proof systems, which explores what can or can't be demonstrated efficiently using this kind of statistical reasoning. (This only really makes sense in a computationally-bounded framework, since if you have unlimited time you can simply check all the possible random choices by brute force and thereby remove randomness from the picture.) See http://www.wisdom.weizmann.ac.il/~oded/pps.html for some surveys and references.