Juergen Schmidhuber writes: > What is the probability of an integer being, say, > a square? This question does not make sense without > a prior probability distribution on the integers. > > This prior cannot be uniform. Try to find one! > Under _any_ distribution some integers must be > more likely than others. > > Which prior is good? Is there a `best' or > `universal' prior? Yes, there is. It assigns to > each integer n as much probability as any other > computable prior, save for a constant factor that > does not depend on n. (A computable prior can be > encoded as a program that takes n as input and > outputs n's probability, e.g., a program that > implements Bernoulli's formula, etc.)
What is the probability that an integer is even? Suppose we use a distribution where integer n has probability 1/2^n. As is appropriate for a probability distribution, this has the property that it sums to 1 as n goes from 1 to infinity. The even integers would then have probability 1/2^2 + 1/2^4 + 1/2^6 ... which works out to 1/3. So under this distribution, the probability that an integer is even is 1/3, and odd is 2/3. Do you think it would come out differently with a universal distribution? The more conventional interpretation would use the probability computed over all numbers less than n, and take the limit as n approaches infinity. This would say that the probability of being even is 1/2. I think this is how such results are derived as the one mentioned earlier by Bruno, that the probability of two random integers being coprime is 6/pi^2. I'd imagine that this result would not hold using a universal distribution. Are these mathematical results fundamentally misguided, or is this an example where the UD is not the best tool for the job? Hal Finney
