# Reference request for examples of probabilistic heuristics, help put some examples in a broader context.

I was thinking about how probability is used in heuristic arguments, an example being the argument that there are an infinite number of twin primes: the probability that $n$ is the first of two twin primes is about $\frac{1}{(\log n)^2}$, and $\prod{(1-\frac{1}{(\log n)^2}}) \rightarrow 0$, so the probability that there are an infinite number of twin primes is $1$. (Another example provided by @joriki is the heuristic for the Collatz conjecture.) I then wondered if there are any heuristic arguments yielding probabilities strictly between $0$ and $1$ and I considered this example predicate:

$A(x,n)$ := "the $n^{th}$ bit of the binary expansion of $x$ is $1$".

Given certain assumptions there is a sense in which $A(\pi, n)$ is "true with probability $\frac{1}{2}$". Now this isn't a very useful notion, since it is either true or not, and we can find out by computing the $n^{th}$ bit of $\pi$, although perhaps there is some utility if $n$ is very large. However it is a second-class sort of heuristic because it only gives a hint to an answer we could find definitively with more work. But next I thought of this example:

$B(x,n)$ := "the binary expansion of $x$ starting from offset $n$, when interpreted as an Iota program, halts".

In a similar way we can lazily argue that $B(\pi, n)$ is "true with probability $\Omega_{\mathrm{Iota}}$". But in this case, under similar assumptions, there are values of $n$ for which $B(\pi, n)$ is not even decidable: we can construct a Gödel-sentence in our working theory, write an Iota program which searches for its proof, find that program in the binary expansion of $\pi$, and then construct $B(\pi, n)$ using its offset $n$. For that reason, it seems to be a first-class sort of heuristic (despite giving us a probability strictly between $0$ and $1$), in the same league as those that give us almost-certain conclusions to open problems.

One of the unstated assumptions (along with the 2-normality of $\pi$ and such) is that there is no "conspiracy" between the bits of $\pi$ and the semantics of Iota. It is equally believable that no such conspiracy exists between $\pi$ and $e$, or between $e$ and Iota, or amongst all three. And since the probability of the conjunction of independent events is equal to the product of their respective probabilities, it is just as reasonable to say that $B(\pi,n) \wedge B(e,n)$ is "true with probability $\Omega_{\mathrm{Iota}}^2$". On the other hand, the same doesn't apply to $B(\pi,n) \wedge B(\pi,n+1)$: since the programs substantially overlap we should expect some correlation in their halting status and therefore a different "truth probability" for the conjunction.

So here are my questions: Are there other (hopefully more natural) examples of problems (open or not) with simple heuristic arguments suggesting a particular probability of truth (other than $0$ or $1$)? Are my (admittedly vague) arguments above at least vaguely correct or are there major mistakes and conceptual problems? What is a good way of describing the dependencies between different heuristics? Can the idea of quantum probability amplitude be applied here? What are some other examples of heuristics that are not independent (e.g. two statements that are both heuristically true but contradict each other)? Any references to related topics that might help me further develop or discard this idea? I have read overviews of fuzzy logic and probabilistic logic but I don't know how to apply either here.

-
You may be interested in the book, Alon and Spencer, The Probabilistic Method (although it's more Graph Theory than Number Theory). Or just type "Probabilistic Method" into the web and see what comes up. –  Gerry Myerson Aug 8 '12 at 1:46

I don't think a heuristic argument suggests a particular probability of truth for a conjecture. I'd view it in a Bayesian light – it suggests a particular probability of truth under the assumption that there is no systematic reason for the result to hold or not to hold, and you should use that to update your a priori assessment of the conjecture. (Of course often you won't have any strong beliefs about the conjecture independent of the numerical data, and in that case the a posteriori probability will be very close to the heuristically determined one.)

For the Goldbach conjecture, the heuristic probability is very close to $1$, but it's still strictly between $0$ and $1$. The same is true for other problems for which extensive numerical searches have been done. In such cases, it's typically not the total heuristic probability for the existence of counterexamples that's very close to $0$, only the part that's left after the extensive search.

For an example of a search that only leads to a moderate update of the belief in a conjecture, see Irregular Primes to 163 million by Buhler and Harvey, in which the expected number of counterexamples to the Kummer–Vandiver conjecture in the searched range was increased from $0.674$ to $0.748$.

[Edit:]

Your comments made me realize that we should actually make further distinctions among the cases where it's possible to gather evidence and give definite answers (i.e. neither your $A$ nor $B$).

The twin-prime conjecture can't be decided numerically; no amount of twin primes following the expected distribution can prove it and no gap or deviation from the distribution can disprove it. All we can do numerically is gather more data and reason about how this should quantitatively affect our belief in the conjecture. This reasoning requires more sophisticated hypothesis testing than just calculating probabilities for counterexamples and then going to look for them; it requires a measure for how unlikely the encountered empirical twin prime distribution would be under the conjectured distribution.

On the other hand, the Goldbach conjecture and the Kummer-Vandiver conjecture can be disproved by a single counterexample, and indeed their numerical investigation proceeds through a search for counterexamples. But the heuristic probability for counterexamples to exist may either be $1$ or less. (Perhaps in some weird continuous cases it might even be zero without this constituting a proof of non-existence.)

In the case of the Goldbach conjecture, it is less than $1$, so at any point in the search for a counterexample there is a certain nonzero probability left that one might be found. Not only is the heuristic probability nonzero, but if you happen to believe that there's no systematic reason for the Goldbach conjecture to hold, then your actual assessment of the probability is close to the small nonzero heuristic probability.

In the case of the Kummer-Vandiver conjecture, there is disagreement on the heuristic arguments. The arguments proposed by Williams and cited by Buhler and Harvey suggest an expected number $\frac12\log\log x$ of counterexamples up to $x$. This would correspond to a probability of $(2x\log x)^{-1}$ for $x$ to be a counterexample, and the probability for there not to be any counterexamples would thus be $\prod_x(1-(2x\log x)^{-1})$, which converges to zero. Thus, no matter how far we search for counterexamples and don't find any, the heuristics would still predict that there are an infinite number of counterexamples yet to come and that the probability of finding at least one is $1$. In this case it's not the heuristical probability for a counterexample that decreases with the search, but our belief in the heuristics, since the lack of counterexamples in the searched range makes it seem more likely that there's a systematic reason for it. Stated differently, in the Goldbach case it's the prospects for the search yet to come that make us believe that we won't find any counterexamples, whereas in the Kummer-Vandiver case (following Williams) it's the results of the search already carried out that make us doubt that we'll find counterexamples, even though the heuristic prospects for the search yet to come haven't actually changed.

Mihăilescu (in the paper I linked to in a comment), on the other hand, offers different arguments and claims that they might imply that there are $O(1)$ counterexamples, which would make this similar to the Goldbach case.

The Collatz case, contrary to what I wrote in a comment, is actually an interesting mixture in that there are two possible types of counterexamples, ascending chains and cycles, and the heuristic probability for ascending chains is zero whereas I don't know of any heuristics for cycles and would expect them to heuristically occur with non-zero probability. Certain kinds of cycles have been proved not to exist, so if the heuristic probability for the existence of cycles is strictly between $0$ and $1$, it's conceivable that a proof might, by eliminating the possibility of cycles altogether, convert the Collatz case from the Goldbach category to the twin-prime category, since the existence of ascending chains can't be numerically decided either way.

I'm really just thinking out loud here; as I wrote in a comment, I had been meaning to ask a similar question; so I hope others will chime in and throw some more light on this surprisingly diverse heuristic zoo.

-
+1, I dismissed the Goldbach heuristic I guess because I don't understand it well enough to see that is strengthened towards $1$ by small examples. Excited to check out your other references. –  Dan Brumleve Aug 6 '12 at 6:23
@Dan: Also check out this paper linked to in the Wikipedia article, which shows that independence assumptions can be tricky. The expected number of counterexamples I cited was based on the heuristics that this paper reassesses. –  joriki Aug 6 '12 at 6:37
@Dan: I agree. [That agreement was to a now-deleted comment about the heuristics on the twin-prime conjecture really being $0$/$1$.] In fact I've been meaning for a while now to ask a question about the distinction between these sorts of heuristics, ones that lead to finite, if often large, updates, and ones for which the heuristic probability is exactly $0$ or $1$. The Collatz conjecture is another example of the latter type. –  joriki Aug 6 '12 at 6:57
It seems to me that we are talking about four different kinds of "heuristics": those that immediately yield certain probabilities (twin-primes, Collatz), those that yield ever-more-certain probabilities with the almost-continuous accumulation of evidence (Goldbach), those which yield uncertain probabilities but for which there is no apparent way to gather evidence short of a definite answer (my example $A(\pi, n)$), and those yielding uncertain probabilities for which a definite answer is not even possible (my example $B(\pi, n)$ where $n$ encodes an undecidable statement). –  Dan Brumleve Aug 7 '12 at 8:22
@Dan: Your comments prompted me to think about this some more; I updated the post with some of my ruminations :-) –  joriki Aug 7 '12 at 17:51