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

Reply via email to