17
$\begingroup$

This question is a bit less than rigorous, but it's only because I don't know how to formulate it rigorously.

Suppose there was some machine, or function, or whatever that could output a random positive whole number. Let's say that it has done its job and I have a number n.

Here's what seems like a paradox to me: if n really was randomly generated, I shouldn't be surprised by its value, no matter how big or small. After all, there is no number that I should have expected more than any other.

On the other hand, if I asked the question of whether I expected the number to be bigger or smaller than the one that I got, the answer would always be bigger. In fact, it was infinitely more likely that I would have gotten a number bigger than what I got. If I got a digit with one billion digits, there are still infinitely more numbers above n than there are below it. No matter the number, it is infinitely improbable that it could have been that small.

Is it just that the idea of picking randomly from an infinite set doesn't make any sense? Or is this a problem that one also runs in to when trying to pick a random element of a finite set?

$\endgroup$
  • 1
    $\begingroup$ Related: Probability of picking a random natural number $\endgroup$ – Rahul Jul 14 '14 at 4:57
  • $\begingroup$ And what if there is no truly random machine? $\endgroup$ – user21820 Jul 14 '14 at 6:05
  • 3
    $\begingroup$ @user21820 This is an altogether different can of worms, better not open it in the present context. $\endgroup$ – Did Jul 14 '14 at 9:21
  • 1
    $\begingroup$ @Did: Heheh alright. $\endgroup$ – user21820 Jul 14 '14 at 9:48
  • 1
    $\begingroup$ @EricTowers - to understand your question is to know the answer to the OP. $\endgroup$ – jwg Jul 14 '14 at 14:42
13
$\begingroup$

Picking a number at random from an infinite set makes perfect sense. It just can't be done uniformly over all points. You would have to specify the probability of (in your case, the natural numbers) choosing each and every natural number. That is, for every $n\ge 1$ you must specify a probability $p_n\ge 0$. The only requirement is that $\sum_np_n=1$. Now, your paradox arises from the hidden supposition that the distribution is uniform, i.e., that $p_n=p_m$ for all $n,m$. This is of course inconsistent, so no such probability distribution exists.

Now that you know that, you must revise your question and see if the paradox survives. So, if you are now given a machine that generates a random natural number according to some distribution (which may or may not be known to you), are you surprised at the outcome? if you see the number $1005$, do you expect the next number to be larger or smaller?

$\endgroup$
  • $\begingroup$ Shouldn't we consider finite-addictive probability instead, through some ultrafilter on $\mathbb{N}$ or something? The main gist of the question still survive even in finite-addictive probability world. $\endgroup$ – Gina Jul 14 '14 at 5:15
  • $\begingroup$ the paradox relies on a uniform distribution (uniform on all points that is). No such thing exists on a an infinite set except for the uniformly $0$ distribution. According to that distribution (however you wish to relate it to probability) any outcome should surprise you immensely. The paradox is dead. $\endgroup$ – Ittay Weiss Jul 14 '14 at 5:18
  • $\begingroup$ On the standard probability on $[0,1]$, probability on each number is $0$, so should you be surprised on any number you get, or not at all? I think this is still the same type of paradox as that, except that for it to make sense you need to cast it in finitely addictive probability, which allow you to also have infinite set with positive probability even if each number is probability 0. And yes, finitely addictive probability, while not as mainstream, is still quite a valid form of statistics, so please don't make it sounds like it does not exist. $\endgroup$ – Gina Jul 14 '14 at 5:38
  • 1
    $\begingroup$ @julian, what the the Axiom of Choice have to do with it? $\endgroup$ – Gerry Myerson Jul 14 '14 at 6:43
  • 1
    $\begingroup$ I can certainly imagine a situation where I don't have all the information yet some oracle does (at least have more information than I do) and that asking the oracles has a cost which may be factored in to an algorithm. But I can't possibly imagine an oracle choosing integers uniformly at random. $\endgroup$ – Ittay Weiss Jul 14 '14 at 7:34
1
$\begingroup$

Is it just that the idea of picking randomly from an infinite set doesn't make any sense? Or is this a problem that one also runs in to when trying to pick a random element of a finite set?

Yes, although what you mean by infinite is important, and there's an issue with your premise - it's (almost certainly) impossible.*

Yes, this is a problem when trying to pick a random element of a (large) finite set.**

Here's a link for more information: https://en.wikipedia.org/wiki/Probability_density_function.

*However, your premise is missing something - you should expect to die before you hear the number. That is to say, if we could create a device (or oracle) such as you describe, a 'stop' button would be essential, else it would be useless after we asked it what number it picked. This also holds true for any finite but sufficiently large set. For similar reasons, there are algorithms which are which work better than any other for 'sufficiently large inputs' whose critics claim would require a computer the size of a galaxy to be useful. They might be exaggerating, but they might not be.

**Let there be a set of integers from 1 to N. If we pick a number at random (each choice as likely as any other) the probability of picking a given number is 1/100 or 1%. The probability of not picking it is 99%, but you have to pick one of the numbers, so it happens. 100*1%=100%

Intuitively, you might expect to get a number close to 50. The expected value is 50.5 after all, as (1+100)/2=50.5.

However, an infinite set (such as you described) has no (finite) average, because it has no greatest element, nor is there a number greater than all elements in it. But, for any sufficiently large set and thus, for any such infinitely large set, the average is a number so long it cannot be heard. So you should be very surprised indeed, if you hear an end to the number the machine says. (Consider returning it for a refund, because it does not perform as advertised, making sure it doesn't rely on a 'perpetual motion machine' to function, or leaving an appropriate review on amazon, so no one else gets swindled.)

In order to construct such a set, merely give a formula for a number N so large you cannot hear it, then specify that the max element of the set is at least twice that (Max>=2N). (This might, unfortunately, depend on how the machine says numbers. If it reads everything like phone numbers, this is kind of easy. 10^10^10^10 or such might do it. If you live for a 100 years, and a number is read aloud at a rate of 1 digit per second then you do not live long enough to hear a 3.2 billion digit number.)

TL:DR; above in bold.

$\endgroup$
-3
$\begingroup$

I'm very rusty, but I'd say if you want the probability that a number is lower than your current pick, you'd use the following formula, where A = the maximum number in the set and B is the number you picked:

P(lower) = 1 - (A-(B-1))/A

So if you were picking from 1 to 10 and picked 9, the probability of picking a lower number would be 1 - (10-(9-1))/10, or 0.8.

How this works when A is infinite is a bit beyond me, but intuitively I'd agree with you: dividing infinity by infinity is 1 (except it isn't, but it feels right!), and then 1-1 is zero, so P(lower) will be 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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