Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the answer to these questions:

it is stated that one cannot pick a natural number randomly.

However, in this question:

it is assumed that we can pick $n$ natural numbers randomly. A description is given in the last question as to how these numbers are randomly selected, to which there seems to be no objection (although the accepted answer is given by one of the people explaining that one cannot pick a random number in the first question).

I know one can't pick a natural number randomly, so how come there doesn't seem to be a problem with randomly picking a number in the last question?

NB: I am happy with some sort of measure-theoretic answer, hence the probability-theory tag, but I think for accessibility to other people a more basic description would be preferable.

share|improve this question
2  
There is a fundamental link between this problem and Poisson point processes. More details to come. –  vanna Aug 3 '12 at 14:12
    
As I see it, the main problem is that because of countable additivity of measure, we would have $P(\{x\})=0$ for each $x\in\Bbb N$. (Assuming all points are equally probable.) Perhaps we should instead consider measures on $\Bbb N$ that are only finitely additive? –  Dejan Govc Aug 3 '12 at 14:20

3 Answers 3

up vote 4 down vote accepted

It really depends on what you mean by the "probability of randomly selecting n natural numbers with property $P$". While you cannot pick random natural number, you can speak of uniform distribution.

For the last problem, the probability is calculated, and is to be understood as the limit when $N \to \infty$ from the "probability of randomly selecting n natural numbers from $1$ to $N$, all pairwise coprime".

Note that in this sense, the second problem also has an answer. And some of this type of probabilities can be connected via dynamical systems to an ergodic measure and an ergodic theorem.


Added The example provided by James Fennell is good to understand the last paragraph above.

Consider ${\mathbb Z}_2 = {\mathbb Z}/2{\mathbb Z}$, and the action of ${\mathbb Z}$ on ${\mathbb Z}_2$ defined by

$$m+ ( n \mod 2)=(n+m) \mod 2$$

Then, there exists an unique ergodic measure on ${\mathbb Z}_2$, namely $P(0 \mod 2)= P(1 \mod 2)= \frac{1}{2}$.

This is really what we intuitively understand by "half of the integers are even".

Now, the ergodic theory yields (and is something which can be easily proven directly in this case)

$$\lim_{N} \frac{\text{amount of even natural numbers} \leq N}{N} = P( 0 \mod 2) =\frac{1}{2} \,.$$

share|improve this answer
    
Ah, okay, thank you. I was misreading the question in that. I understood it to say, first pick n natural numbers randomly, then check to see if we have property $P$. It makes sense now, thanks. –  Joe Tait Aug 3 '12 at 14:22

Perhaps a justification is this. In the first question it is (correctly) claimed that it is impossible to have a uniform distribution on the natural numbers. Thus we can't develop a sensible way of choosing particular numbers at random, when each supposedly has the same probability. The last question though is dealing with the probability of picking a certain class of numbers. In that case the approach is to pick $N$ large, impose a uniform distribution on $[1,N]$ (which we can always do), work out the probability as a function of $N$, and then take the limit $N \rightarrow \infty.$

Example: what's the probability of randomly picking an even number?

Fix $N$. If $N$ is even then the probability of picking an even number in the uniform distribution on $[1,N]$ is exactly $1/2$. If $N$ is odd then the probability is $$ \frac{\text{amount of even numbers}}{\text{total amount}} = \frac{ (N-1)/2 }{N} = \frac{1}{2} - \frac{1}{2N} $$ And so, as we take the limit $N \rightarrow \infty$, we say that the probability of choosing an even number is 1/2.


This approach is really a "natural density" approach; see http://en.wikipedia.org/wiki/Natural_density.

The natural density features in, for instance, the Green-Tao theorem. Green and Tao showed that the primes have positive natural density, and thus that they must contain arbitrarily long arithmetic sequences. <- incorrect!!

share|improve this answer
    
Thank you for the explanation, it is very clear. As in my comment in the answer above, I had read to question to be first pick $n$ natural numbers randomly, and then see if property $P$ holds, so the confusion was really caused by my misreading. Thank you. –  Joe Tait Aug 3 '12 at 14:27
2  
@JoeTait: It should be noted that you give up something when you consider density: namely, not all subsets of the natural numbers have a well-defined density, because the limit discussed above may not converge. –  Nate Eldredge Aug 3 '12 at 14:31
1  
Perhaps I've got something confused here, but the natural density wikipedia article to which you linked claims that the primes have natural (asymptotic) density zero, due to the prime number theorem. Given the definition there, I agree with that statement. Are you talking about a different definition? –  J. Loreaux Aug 3 '12 at 19:19
    
You're definitely right. I misread the Green-Tao result. They say that any subset of the primes with relative positive density (roughly, positive density wrt to the primes as a whole) has arbitrarily long arithmetic sequences. Thanks for the heads up! –  James Fennell Aug 3 '12 at 20:58
1  
@James: Thanks for the response. In the future, please use the @ symbol to notify the person to whom you are responding. :-) –  J. Loreaux Aug 6 '12 at 12:26

There is no uniform distribution on the natural numbers.

share|improve this answer
3  
I am aware of that, my issue was how they "got round this" in the last linked question. Perhaps they haven't but I suspect someone answering would have picked up on it... –  Joe Tait Aug 3 '12 at 14:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.