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.)

##
Advertising

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