Welcome to NRICH.

 
Probability of randomly choosing a mulitiple of 4 from the Natural Numbers
To be archived: Probability paradox
By Gerald Kennally on Thursday, November 01, 2001 - 08:13 pm:

I've come to this site, although much too old, because I simply can't find anywhere to ask this question: Consider the positive integers:
1,2,3,4,5,6,...
If you pick one at random the probability that it is a multiple of 4 is clearly(!!!) 1/4.
Now rewrite them as
1,2,4,3,5,8,6,7,12,9,10,16,...
putting multiples of 4 at every third position.
Now the probability of a multiple of 4 is equally clearly 1/3. So how come it matters what ordering you put on it?
Sorry to use up the space for kids but it really has been getting to me.
It arose because on the radio someone described a new number (omega?) as:
" Roughly the probability of picking out an unprovable proposition if you put all the propositions of arithmetic in a bag and shook them up.."
Since both sets are countably infinite, I don't see how this probability can be defined like this if probabilities depend on ordering.

By Dave Sheridan on Monday, November 12, 2001 - 11:39 am:

Firstly, it is possible to define a uniform distribution on many infinite sets, but it must be a strictly continuous distribution. The easiest example is choosing a number uniformly from [0,1]. In general, you can choose "uniform numbers" from any compact group, since such a group automatically has a finite Haar measure. However, I won't go further into this unless asked, since it's probably way too high level for the question asked!

Why can't we define the probability above properly? What you've defined is not a probability distribution. For you to specify the distribution, give a general formula for P(X < n) for each integer n; you'll find that it's impossible to consistently do this keeping P(X=n) positive and equal for all n (ie "uniform" but with positive probability of choosing any particular number).

What can you do to choose a random integer then? If you forget the possibility of a "uniform" number, you have many options. For example, the Poisson distribution with parameter z satisfies
P(X=n)=e^(-z) z^n / n!
for each n>=0.

Probability theory can be used in number theory roughly using the argument presented, although you need a different distribution. The Riemann zeta function is defined by
zeta(s)=sum n^(-s)
where the sum is over integers n>0. If you conside r the probability distribution
P(X=n)= n^(-s) / zeta(s)
(clearly this sums to 1)
then you can use heuristics like "the probability of choosing a multiple of 4 is 1/4" to prove nice properties of the zeta function.

As for proving propositions, any proof is a list of statements each of which are either axioms or derived from previous statements. If the set of axioms is Z, there are N^Z proveable theorems which may be fewer than the total number of theorems constructable from Z (depending on its cardinality and which model of logic you study).

Generally, if you hear someone talking about probability on the radio take it with a pinch of salt...

-Dave