Re: probabilities & measures & computable universes

From: Hal Finney <hal.domain.name.hidden>
Date: Fri, 23 Jan 2004 21:04:20 -0800

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
Received on Sat Jan 24 2004 - 00:06:03 PST