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.

Choose any natural number.

For example I would choose:

3852011231231280130218920382342312420234801232321241231212131234 (and so for for another few bilions of digits)

What's the probability that somebody can guess it ?

Since there are infinite natural numbers I saw that the answer is 0. (this is from a book from gregory chaitin)

is that correct ?

or is it more correct to say that it's very very very.... unlikely but still possible.

share|improve this question

closed as not a real question by hardmath, rschwieb, N. S., Stefan Hansen, Arkamis Apr 29 '13 at 17:26

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
To determine a probability, one needs a probability distribution. For example one distribution would be to assign probability one to the very billions-of-digits long number you are thinking of, and zero to every other natural number. What often happens is that readers/listeners assume you mean a uniform probability distribution (all outcomes equally likely) when asking such questions without defining your distribution. But there is no uniform probability distribution on the natural numbers. –  hardmath Apr 29 '13 at 16:36
    
@hardmath thanks but I'd say that any number has the same probability distribution. –  lorenzo Apr 29 '13 at 16:38
1  
Hm, let me guess ... 3852011231231280130218920382342312420234801232321241231212131235. Darn, so close ... –  Hagen von Eitzen Apr 29 '13 at 16:39
    
You seem to misunderstand. A probability distribution is a function that assigns a probability to each element, subject to the requirement that all the probabilities are nonnegative and add up to one. It just isn't possible to have a uniform probability distribution on the natural numbers. A non-uniform distribution is possible, such as the case I described (pick one number and give it probability one, zero for all others). –  hardmath Apr 29 '13 at 16:40
    
@hardmath okay you may be right, so there is no probability distribution. or some how the probability distribution is an infinite sum which adds up to 1 (like in a series) –  lorenzo Apr 29 '13 at 16:43

4 Answers 4

To be able to answer your question, you'd have to specify how someone would guess an arbitrary natural number. Since $\mathbb{N}$ is coutable infinite, there's no such thing as a uniform probability distribution over $\mathbb{N}$. Such a distribution would have to assign the same probability to each natural number (to be uniform), but that'd make the sum of all probabilities $+\infty$, not $1$ as you'd want for a probability distribution.

There are non-uniform distributions over $\mathbb{N}$ though, but to compute what the probability of 3852011231231280130218920382342312420234801232321241231212131234 under such a distribution would be, you first have to decide which distribution to use.

share|improve this answer

This is neither correct nor incorrect until you specify how the number is chosen. Since choosing a natural number uniformly at random is impossible, you must provide the distribution $(p_n)$ on $\mathbb N$ you are using.

On the other hand, if the guesser guesses $n$ with probability $q_n$ and there is no transmission of information between the guesser and you, the guesser is succesful with probability $$ \sum_np_nq_n. $$ If the guesser knows the distribution $(p_n)$ you are using, their best choice is $(q_n)=(p_n)$, which yields a chance of success $$ \sum_np_n^2. $$ For example, if you choose a number uniformly randomly between $1$ and $N$, the chances of a successful guess are at most $\frac1N$ and they are less as soon as the guesser uses another distribution to determine their pick.

share|improve this answer
    
specify how the number is chosen: Okay easy. I say choose the most unlikely natural number for me to guess. –  lorenzo Apr 29 '13 at 16:40
    
Any string of words put together, even if the result is grammatically correct, does not describe a mathematical object. Your "the most unlikely natural number for me to guess" seems to fall in the category of those that don't. –  Did Apr 29 '13 at 16:44

I believe that the answer is not zero. Any number you choose would have to be written down or recorded in some way, so there is a maximum number possible for you (or anyone) to choose. The reciprocal of this maximum is the chance someone can guess it.

share|improve this answer
    
yes you are right any number would have to be written down but in principle there are infinite numbers to write. so you can say 1/[maximum possible numbers] –  lorenzo Apr 29 '13 at 16:39
    
No, you can pick random elements from $\mathbb{N}$ without imposing an upper bound. You could, for example, pick random digits uniformly from ${0,\ldots,9}$ one after the other, and after each one stop with probability $p$ and continue with probability $1-p$. That'll produce arbitrarily large numbers, but of course smaller number will have higher probabilities. –  fgp Apr 29 '13 at 16:42
    
This is getting complicated, since then there is the issue of what it means to represent numbers and how to determine if two representations of numbers in fact represent the same number. So I think for the purpose of this question it's best to keep it an idealized situation where you could potentially represent any number. –  user64480 Apr 29 '13 at 16:44
    
I disagree. There are less than $10^{80}$ atoms in the universe. I challenge anyone to write down a number with more than $10^{80}$ digits. –  vadim123 Apr 29 '13 at 16:47
    
There are various ways of representing numbers. What about $10^{10^{80}}$? I just wrote it down. –  user64480 Apr 29 '13 at 17:25

You are correct. The answer is zero.

share|improve this answer
    
should it not be something near zero but not exactly zero ? –  lorenzo Apr 29 '13 at 16:36
    
No, it's not zero. If the probability of every natural number is zero, then the sum of all probabilities would be zero also. But for a probability distribution, that sums needs to be one, not zero. –  fgp Apr 29 '13 at 16:37

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