4 ms·

My favorite thought experiment that I think is relevant here is to try to pick a truly random number. If you think about it, this is impossible, because the ac

by drblast 14y ago

My favorite thought experiment that I think is relevant here is to try to pick a truly random number. If you think about it, this is impossible, because the act of picking a number limits you to a finite set of numbers that you have considered. Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space. This has all sorts of odd implications, like the two envelope paradox: http://en.wikipedia.org/wiki/Two_envelopes_problem http://en.wikipedia.org/wiki/Two_envelopes_problem Enjoy!

raverbashing 14y ago
Interesting The two envelopes problem look like a "hard" Monty Hall problem, in the MH problem it's easy to see how swapping improves chances, since you're removing one bad option
davmre 14y ago
Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space. That's not true; there's nothing wrong with infinite sample spaces. It's just that there's just no such thing as a uniform distribution over an infinite space. For example, suppose you flip a fair coin repeatedly until the first time it comes up Heads. The number of flips you end up making could be any positive integer, so this procedure samples from an infinite space. But not all integers are equally likely. (in fact, each integer is half as likely as the one before, following a geometric distribution).
- alok-g 14y ago
  How about generating an infinite sequence of bits to generate any positive integer (in binary) with uniform probability? Sure it will take infinite time, but so may the method in your note. As another comment here points out, it would take infinite time to write down a purely random number anyways.
  - Evbn 14y ago
    Parents method produces a result in finite time with probability infinitesimally close to 1. Yours produces a result in finite with probability infinitesimally close to 0. That is the greatest measurable difference in all of mathematics. In other words, on method basically always succeeds, the other never succeeds (not "fails", but "never succeeds")
  - davmre 14y ago
    The method I described gives nonzero probability to every positive integer. The method you describe a) will never terminate and thus b) gives zero probability to every positive integer (since there's no stopping condition, even if you ever get to a particular integer you're always going to generate another digit and move on past it). The essential issue is that probabilities have to sum to 1, but you can't just give the same probability to an infinite number of things because there's no number for which p*infinity = 1. So the only way to get an infinite sum to equal 1 is if the probabilities are unequal, and in particular the probabilities have to go to zero in the limit (e.g. 1/2 + 1/4 + 1/8 + 1/16 + ... = 1).
bmm6o 14y ago
Well, the real problem is that there is no uniform distribution on the integers.
Dove 14y ago
The ability to pick a truly random integer from a uniform distribution is just a practical one. Consider: How many digits does a "typical" integer have? The answer is that it is unbounded. For any value you choose, it is easy to show that there are far more integers with more digits than with less. So indeed, even writing down your choice of a random integer would take a long time. But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling.
- quacker 14y ago
  But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling. Exactly this. The two envelopes paradox is a paradox only because using a fallacious argument leads to the wrong result, and the Wiki page proposes numerous resolutions to the problem as well. I like this way of stating it (from http://en.wikipedia.org/wiki/Two_envelopes_problem#Non-probabilistic_variant http://en.wikipedia.org/wiki/Two_envelopes_problem#Non-proba...): 1. Let the amount in the envelope chosen by the player be A. By swapping, the player may gain A or lose A/2. So the potential gain is strictly greater than the potential loss. 2. Let the amounts in the envelopes be X and 2X. Now by swapping, the player may gain X or lose X. So the potential gain is equal to the potential loss. In the first case, A and A/2 are actually referring to the same amount of money. You have to condition on what A is: If A is the larger value, the second envelope cannot contain 2A; A/2 is equal to the smaller amount. If A is the smaller amount, then the second envelope cannot contain A/2; A is equal to the smaller amount. So your potential gain and loss are both equal to the smaller amount of money, and you have no logical reason to swap.

by drblast 14y ago

raverbashing 14y ago

Interesting The two envelopes problem look like a "hard" Monty Hall problem, in the MH problem it's easy to see how swapping improves chances, since you're removing one bad option

davmre 14y ago

Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space. That's not true; there's nothing wrong with infinite sample spaces. It's just that there's just no such thing as a uniform distribution over an infinite space. For example, suppose you flip a fair coin repeatedly until the first time it comes up Heads. The number of flips you end up making could be any positive integer, so this procedure samples from an infinite space. But not all integers are equally likely. (in fact, each integer is half as likely as the one before, following a geometric distribution).

alok-g 14y ago
How about generating an infinite sequence of bits to generate any positive integer (in binary) with uniform probability? Sure it will take infinite time, but so may the method in your note. As another comment here points out, it would take infinite time to write down a purely random number anyways.
- Evbn 14y ago
  Parents method produces a result in finite time with probability infinitesimally close to 1. Yours produces a result in finite with probability infinitesimally close to 0. That is the greatest measurable difference in all of mathematics. In other words, on method basically always succeeds, the other never succeeds (not "fails", but "never succeeds")
- davmre 14y ago
  The method I described gives nonzero probability to every positive integer. The method you describe a) will never terminate and thus b) gives zero probability to every positive integer (since there's no stopping condition, even if you ever get to a particular integer you're always going to generate another digit and move on past it). The essential issue is that probabilities have to sum to 1, but you can't just give the same probability to an infinite number of things because there's no number for which p*infinity = 1. So the only way to get an infinite sum to equal 1 is if the probabilities are unequal, and in particular the probabilities have to go to zero in the limit (e.g. 1/2 + 1/4 + 1/8 + 1/16 + ... = 1).

bmm6o 14y ago

Well, the real problem is that there is no uniform distribution on the integers.

Dove 14y ago

The ability to pick a truly random integer from a uniform distribution is just a practical one. Consider: How many digits does a "typical" integer have? The answer is that it is unbounded. For any value you choose, it is easy to show that there are far more integers with more digits than with less. So indeed, even writing down your choice of a random integer would take a long time. But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling.

quacker 14y ago
But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling. Exactly this. The two envelopes paradox is a paradox only because using a fallacious argument leads to the wrong result, and the Wiki page proposes numerous resolutions to the problem as well. I like this way of stating it (from http://en.wikipedia.org/wiki/Two_envelopes_problem#Non-probabilistic_variant http://en.wikipedia.org/wiki/Two_envelopes_problem#Non-proba...): 1. Let the amount in the envelope chosen by the player be A. By swapping, the player may gain A or lose A/2. So the potential gain is strictly greater than the potential loss. 2. Let the amounts in the envelopes be X and 2X. Now by swapping, the player may gain X or lose X. So the potential gain is equal to the potential loss. In the first case, A and A/2 are actually referring to the same amount of money. You have to condition on what A is: If A is the larger value, the second envelope cannot contain 2A; A/2 is equal to the smaller amount. If A is the smaller amount, then the second envelope cannot contain A/2; A is equal to the smaller amount. So your potential gain and loss are both equal to the smaller amount of money, and you have no logical reason to swap.