Randomly selecting from an infinite number of choices

Also, Pete, Nasor's #23 post presumes that the selection is possible. I feel we have proven that it is not possible, but if it were (with Angels and Devils capable of supertasks) then the answer is ZERO probability. Do you agree?

 

Log in or Sign up to hide all adverts.

Sure, just like the odds of flipping a head on any coin flip is constant... but the odds of when the first flip will occur is not.

Ah... that's the key!

That's the heart of the problem - the atom can only decay once. It will only last until the first time heads comes up.

 

Log in or Sign up to hide all adverts.

No. I think the question is meaningless.

 

Log in or Sign up to hide all adverts.

Or, equally likely, 5 Trillion years or 5 quadrillion years or 5 megistron years, and so on. If each of these is equally likely, it follows that the expected time till decay is greater than any finite number, since there is always an unbounded set of equally-probable greater numbers. Whether you call this "infinite" or "undefined" is just semantics: if the distribution is truly uniform over all time, then you will sit there waiting for the particle to decay for ever. It is easy to show that the probability of it occurring before the earth crashes into the sun is dwarfed by the probability of it occurring in the unbounded length of time that follows that event.

I suspect that you have misread what I wrote, and also mistyped here.

The set of natural numbers is infinite. The required length of a codeword to describe a particular element of a set depends on the size of the set and the probability of the element in question, not the size of the element itself. In order to uniquely specify an infinite number of possible outcomes (i.e., all natural numbers), you will need at least some codewords of infinite length. And if all of the elements have equal probability, then the shortest possible average-length code for describing them will consist entirely of infinite-length codewords.

Why would I want to show otherwise? Again, I think you have misread my post.

The issue is not the length of the numbers themselves, but the lengths of the codewords required to represent them. And this depends not on the size of the number, but on the size of the set of possible numbers you want to represent.

I suspect the issue may be related to the idea that it only requires a finite number of 0's and 9's to represent any finite natural number. However, this is actually a shorthand. We have an extra "blank" symbol, which we use to represent an infinite string of 0's. I.e., when you refer to the natural number "152," you're actually using an abbreviation for the natural number "....000152," where the zeros on the left go on for ever.

But most of the natural numbers do NOT have infinite runs of zeros on their left-hand-side! Using the same reasoning as above, you can easily show that the number of natural numbers that require more than D digits to represent is infinite. And so, since the set of natural number that require D or fewer digits is clearly finite, it follows that almost all natural numbers require an unbounded number of digits to describe! Said another way, if you are truly selecting from a uniform distribution on the natural numbers, the probability that you will choose one that can be described with a finite number of digits is zero!

 

Please give the definition of "Undefined" that you are using here. Perhaps not giving an answer is more comforting than giving a clearly problematic answer, but not by much :]

No, I see very clearly that you propose to generate symbols directly in the compressed domain. Use of the compression function is merely a convenience: since it's exactly specified by the expander function, we can conclude just as much from its operation as that of the expander, even if you don't propose to actually operate the compressor. Indeed, none of the results concerning infinite code length depend on operation of the compressor; they apply equally well to an expander-only scenario. The whole point was that the compressed representation was going to have infinite length, after all.

Your insistence on irrelevance is both incorrect and argumentative.

Then don't be.

You need to make arguments that reflect your assumptions about how the rules are generated, one way or the other. As it is, you are sweeping everything under the rug by invoking another supertask (that of choosing the rules).

A tautology. Unless you have a method for choosing uniformly from the infinite set of possible expansions in finite time, then your entire approach is circular, as it requires you to first carry out another supertask.

To put it more simply, you will never finish selecting the rules of expansion, or if you do, they won't have been uniformly chosen from all possible expansions, and so the resulting outputs won't be uniformly chosen from an infinite set.

Again, you're going in circles by subsuming the rule selection into the random number generation, and so you shoud not do this. If you can't show how to select uniformly from an infinite set with a fixed expander, how are you then going to select uniformly from an infinite set of expanders?

 

Sure, but that's not interesting. The point is that you can't describe a uniform selection from an infinite set in a finite period of time with symbols of finite complexity. It doesn't matter that there are no infinite natural numbers; what matters is that there are infinitely many natural numbers.

If you agree with these statements, then why do you persist in claiming that you can select uniformly from the set of all natural numbers in finite time?

 

Trippy, what is your answer for #23? And why are you still defending compression/expanders if you later claimed that time limitations are irrelevant? Either you have infinite time or you do not. You mentioned expansion algorithms to deal with the infinite amount of time it would take to communicate an answer. Your expansion algorithms are interesting but moot!

 

Nah man last night I was drunk and being cheeky but I apologized (I even deleted my post!). Today I'm asking you for a straight answer when I believe that you're just being contrary and argumentative. It would've been quicker to reiterate your answer to #23 than to start quoting other posts and tell me to get over myself.

Please Register or Log in to view the hidden image!

 

There is no controversy over the idea that any finite number can be represented (in fact, infinite ones can also be represented). But you haven't addressed how that relates to "choosing" a number. Indeed, you have it backwards: you need to choose a number before you can even talk about representing it. Even then, that says nothing at all about how big the set of possible choices was, which IS the crux of the matter.

You said yourself:

Ergo, any number that you can choose in a finite time MUST have been chosen either from a finite set, or from a non-uniform distribution on an infinite set.

 

My objection has nothing to do with the size of the numbers that get picked (although I can't speak for anyone else), but rather the size of the set of numbers that you pick from. The argument is that you cannot choose uniformly from an infinite pool because you cannot represent every possible outcome of that selection in a finite period of time.

In order to guarantee a finite representation, you must first limit the pool to be finite (or at least non-uniform).

You need to be able to represent them, otherwise how can you claim to have selected from amongst them in the first place?

Indeed, but the problem is that you can only distinguish a finite number of such outcomes using finite symbols/time/rules. In order to provide unique symbols for an infinite collection of possible outcomes, you need infinite symbols/time/rules.

And that is not necessarily a problem, provided the probability of a given number eventually decreases with the length of the symbol associated with it. Then you can still get a finite expected symbol length/time/complexity. But if you have a uniform distribution on an infinite set, then the expected length/complexity of the symbol associated with the outcome of a random selection is also infinite. Note that this result does not depend on the details of how you generate symbols, only that you do so in a way capable of uniquely representing any natural number.

To put it another way: for any (arbitrarily large) finite set of symbols/rules/time you care to specify, there will still be infinitely many natural numbers that you cannot assign symbols to. Thus, the probability of (uniformly) picking a number that you can build a symbol for is equal to zero. Again, regardless of the details of the system you specify.

I suspected as much, but you should realize that you posted it, without quotes, in post #148. Hence the confusion.

Anyway, the results about stopping times are highly pertinent: they are a much more concise, rigorous proof that you cannot select from an infinite uniform distribution in finite time. Although I personally find the Information Theoretic explanation more enlightening.

An explanation based on Kolmogorov Complexity would be very interesting as well, if anyone is strong in that area...