8
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ There is a fundamental link between this problem and Poisson point processes. More details to come. $\endgroup$
    – vanna
    Aug 3, 2012 at 14:12
  • $\begingroup$ 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? $\endgroup$
    – Dejan Govc
    Aug 3, 2012 at 14:20

4 Answers 4

Reset to default
6
$\begingroup$

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} \,.$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Joe Tait
    Aug 3, 2012 at 14:22
2
$\begingroup$

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!!

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Joe Tait
    Aug 3, 2012 at 14:27
  • 2
    $\begingroup$ @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. $\endgroup$
    – Nate Eldredge
    Aug 3, 2012 at 14:31
  • 1
    $\begingroup$ 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? $\endgroup$
    – J. Loreaux
    Aug 3, 2012 at 19:19
  • $\begingroup$ 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! $\endgroup$
    – James Fennell
    Aug 3, 2012 at 20:58
  • 2
    $\begingroup$ @James: Thanks for the response. In the future, please use the @ symbol to notify the person to whom you are responding. :-) $\endgroup$
    – J. Loreaux
    Aug 6, 2012 at 12:26
0
$\begingroup$

By partitioning the real numbers using non-measurable sets, it is possible to relate a real selected uniformly at random from an interval like [0, 1) to a natural number using a method by which all natural numbers have an "equal" chance of being mapped to (here, equal simply means that no natural is given any sort of preference as to being selected over any other natural), however, the probability of picking any given natural number is undefined as a result of having to partition the reals into non-measurable sets in order to create the mapping. As a result, we are not able to create a cumulative distribution function that is meaningful. To see an example of this, see the following question:

Is this fraction undefined? Infinite Probability Question.

$\endgroup$
-1
$\begingroup$

There is no uniform distribution on the natural numbers.

$\endgroup$
1
  • 3
    $\begingroup$ 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... $\endgroup$
    – Joe Tait
    Aug 3, 2012 at 14:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .