# Randomly selecting from an infinite number of choices

Discussion in 'Physics & Math' started by Nasor, Jan 20, 2009.

1. ### rpennerFully WiredRegistered Senior Member

Messages:
4,833

to hide all adverts.
3. ### zanketHumanValued Senior Member

Messages:
3,777
Censorship: because the censors are always right, silly.

to hide all adverts.
5. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
No. I've chosen not to represent those other numbers. The only requirement is that I can, the fact that representing 1 is inanely complex is irrelevant, because I haven't chosen to represent 1. If I had wanted to choose 1, I would have chosen a set of rules and symbols that make representing 1 simplistic. And as for this infinite zeros thing, that essentially amounts to quibbling over semantics. I had mentioned the 'rule' in a previous post (I think it was addressed to Zanket), and "When you're finished add infinitely many zeros to the left of the number" simply becomes another rule for dealing with the number, so it's covered in that regard as well.

I should also hasten to point out that the set of all natural numbers does not form a continuous set. There is no natural nummber between 1 and 2, there is only 1, and 2.

Only true if you restrict yourself to a single rule at all times.

See above.
And I only need 1 ten sided dice to determine a number between 1 and 10.

Right. And what was I saying about 'scale dependent rules'? And what was the purpose of the K-40 atom in my machine?

Pay attention.

Show me where I was assuming this again?

Explain to me how $3^{3^{3^{3^{3^{3^{3^{3{.{.{.}}}}}}}}}}$ gives rise to a simple number with a long string of zeros in it?

No. I only need the possibility of the representing the number given sufficient time to exist. If I want to choose that number, but it's going to take too long to write it in the current set of rules, then I choose a different set of rules that makes it easier.

Explain to me how $3^{3^{3^{3^{3^{3^{3^{3{.{.{.}}}}}}}}}}$ gives rise to a simple number with a long string of zeros in it?

You're aware that the last 100 digits of grahams number are:
9404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387

Right? oops. No string of zeros there either.

Because any natural number I can select is finitely complex, and can therefore be represented in a lesser form with rules of finite complexity.

Last edited: Jan 30, 2009

to hide all adverts.
7. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
Seems like everybody was wrong.
This is 400 level stats.
Infinite Discrete Random Variables

Although I didn't specifiy which δ I was referring to but then again - nobody asked.
And before anybody says anything, Kronecker delta is not the same as zero, so if you said zero you were wrong.

8. ### quadraphonicsBloodthirsty BarbarianValued Senior Member

Messages:
9,391

??? That page deals with Poisson processes. Nobody has disputed that you can draw from an infinite set provided you use a non-uniform distribution (which the Poisson distribution is). Perhaps you meant to link to something else?

9. ### PeteIt's not rocket surgeryRegistered Senior Member

Messages:
10,166
I was considering something similar last night, while pondering what superprocess could be used to complete the supertask of choosing from a uniform infinite distribution.
What you said is the same as something I considered - flipping infinite coins to get a binary value. Or, spinning infinite ten-sided dice to get a decimal value.

The problem with those methods is that they don't produce finite numbers. I don't think that they are part of the naturals. Consider: the cardinality of the pool of possibilities is to be greater than the cardinality of the naturals - this is easy to see when you consider that exactly the same method can be used to a generate random real, by putting the digits after the decimal point instead of before.

So, I suspect that this method is yet another superprocess for the supertask of selecting randomly from a uniform distribution on the continuum.

But!
Since in completing a supertask we can complete infinite finite tasks, it's not much of a stretch to consider a task that involves completing infinite supertasks. A supersupertask, if you want to classify it separately.
Edit - Actually, no. It's already been labeled a hypertask by Clarke and Read.

So, let the demon spin its infinite dice to get an infinite random string of digits.
And let it spin them again, and again, and again, in fact let it spin them and infinite number of times, until it spins a number that begins with an infinite string of zeros.

Or, let the demon throw an infinite number of infinitely precise darts at an infinitely precise strip representing the number line from zero to one, randomly choosing reals until it precisely chooses the reciprocal of a natural (considering the distribution of natural number reciprocals on the line segment, this method would intuitively appear to select from a non-uniform distribution... but appearances are deceptive in this case).

Note that these processes are even more involved than they might appear. If the demon generates countably infinite random strings of infinite digits, zero of those strings will end with infinite zeros. The demon must be able to spin its infinite dice uncountably infinite times. When it spins its first natural, it will have already completed uncountably infinite spins which were rejected.

It would be interesting if this is a general result.
It seems clear that selecting a random element from a uniform distribution on an uncountably infinite set is a supertask.
Is selecting a random element from a uniform distribution on a countably infinite set a hypertask?

10. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
Actually, it describes how to deal an infinite discrete random variable, the POisonn distribution falls out of that dealing.

Did it occur to you that your question might be meaningless?

Like trying to find the solution to a set of mutually exclusive simultaneous equations.

The K-40 machine and the button mashing (without variable rules) follow a Poisson distribution (actually, I think the K-40 might better be described as an exponential distribution) in number length, but once number length has been determined, the probability of generating a 9 digit 1 is the same as generating any other nine digit number - hence the probability of choosing any number is uniform (once the number length has been chosen) - as I said to Pete yesterday.

More to the point, it has been insisted multiple times that the probability is zero. Period (therefore the task must be impossible in some way).

11. ### quadraphonicsBloodthirsty BarbarianValued Senior Member

Messages:
9,391
That's fine, but the fact remains that communicating which set of natural numbers you're going to be representing is almost always at least as complex as simply communicating the natural numbers directly.

And what makes you think that you could communicate any such set of rules for any given natural number, in less time than it takes to just communicate the number?

Which begs the question of when, exactly, you "finish." Since there are infinitely many natural numbers, the probability that a uniform draw from them will have less than any finite number of non-trivial digits is exactly zero. You will never finish. No matter how long you are willing to wait, you never reach the end.

So what? The topological structure of the natural numbers plays no role here. For example, you could apply a permutation to them, and the exact same issues would remain.

Which I've already shown that you must do, or else the overhead of transmitting the rule will be equivalent to (or even worse than) that of transmitting a natural number. You can either stick to a single set of fixed rules, or you can forward a circular argument. Neither approach will give the end result you want.

Indeed, but you need to determine a countable number of numbers between 1 and 10, not just "a number."

You didn't say much of anything about them. In particular you have failed to notice that the complexity of the rules will increase with scale, since the dynamic range required is also increasing. What you need is not the ability to handle large numbers, per se, but the ability to handle numbers with lots of non-zero digits that are not related to one another in any structured way.

To generate the range, of course. The problem is that the K-40 atom must decay according to a uniform distribution over all time, if the resulting output is to be uniform over the set of all natural numbers. And you just said that you don't assert that this is the case. Moreover, if it IS the case, it follows that the probability of observing a decay of the K-40 atom in any finite time is exactly zero, so your machine will never produce an output.

Again, we have the stopping time result: if the algorithm stops, it wasn't drawing uniformly from an infinite set.

Every number you've cited, including the supposed counterexamples, have some strong structure to them. In some cases it's a string of zeros, in others its the ability to be concisely expressed via nested exponents, or whatever other operation.

The point is you are assuming that you can come up with some concise representation for ANY natural number, but almost all of them do not admit any such reduction.

By all means, try to prove me wrong if you disagree. But the fact that you can think of ways to compress a few particular (strongly structured) examples doesn't get you anywhere: you need to be able to do this for ANY natural number.

Please substantiate the assumption that any such set of 'easy' rules exists, for every natural number.

Again, substantiate this statement. I contend that it is false, in that almost all natural numbers do not admit any more concise description than a list of their non-trivial digits.

Note that no finite number of counterexamples will prove you right. You need to show that some such a description must always exist, for any natural number.

12. ### PeteIt's not rocket surgeryRegistered Senior Member

Messages:
10,166
Yes, Trippy.

So you do realise that your device is biased to produce numbers with fewer digits, right?

No, I think you have a misunderstanding about that fact. You don't seem to understand how to consider the distribution of all numbers the device can produce.

13. ### PeteIt's not rocket surgeryRegistered Senior Member

Messages:
10,166
It doesn't describe discrete random variables of uniform distribution, Trippy.
Do you not understand the importance of this?

14. ### quadraphonicsBloodthirsty BarbarianValued Senior Member

Messages:
9,391
We're not talking about any discrete infinite random variable, but with one that is uniformly distributed. I, and others, have repeatedly made it explicit that there is no problem whatsoever with non-uniform distributions like Poisson. Well-defined sitributions like that readily admit selection algorithms with finite expected stopping time. The objections apply ONLY to uniformly-distributed infinite sets.

I have known from the outset that the concept of a uniformly-distributed random variable with infinite support is meaningless. That is exactly what everyone has been trying to convince you of this whole time.

The problem is not to choose uniformly amongst a finite set of naturals with fixed lengths. The problem is to choose uniformly from ALL of the natural numbers. If you choose the length from a non-uniform distribution (like the Poisson or exponential), then the resulting outcome is guaranteed NOT to be uniformly distributed over the naturals: the probability of choosing a particular number will depend on its length, and so not be a constant.

That you choose the digits uniformly after that point is not relevant. By selecting the range with a non-uniform distribution, you've already guaranteed that, no matter how you proceed, the final result is NOT uniformly drawn from the set of natural numbers.

The probability of what, exactly? Nothing having to do with a Poisson distribution, that I know of.

15. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
The evidence would appear to suggest otherwise.

16. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
Show me, again, where I said it did, Pete.

17. ### PeteIt's not rocket surgeryRegistered Senior Member

Messages:
10,166
Firstly, that's not complete - there are more terms to add to get the complete probability of a 1.

But the main problem is in your apparent understanding. You seem to think that the individual terms in the calculation are more important than the total. Why?

18. ### PeteIt's not rocket surgeryRegistered Senior Member

Messages:
10,166
Show me where I said you said it did.

Please Register or Log in to view the hidden image!

Do you understand that no one has a problem with non-uniform infinite discrete distributions?
Do you understand that infinite discrete random variables of non-uniform distribution are irrelevant to the question posed?

If so, then why do you think that page answers the question?

19. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
First off, it is complete, because it represents the probability of generating 1 after 6 lifetimes, not n lifetimes.

The equation, as defined by the problem is complete.

Unless you're suggesting it's possible to generate a seven digit number after 6 half lives?

Because by the definition of how the original machine worked, and how I described it A K-40 atom that decays after 6 half lives isn't going to produce a three digit number.

It might have, but it didn't.

20. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890

This is the post (post number 24) that I have been objecting to (or I suppose i've been specifically addressing).

The insistence in this post, is that the answer in theory is Zero. It isn't.
The insistence in this post, is that it is not possible to choose randomly from an infinite pool. It is, and both you and Pete have explicitly agreed to that.
There is no insistence in this post that the distribution must be uniform.

There is also no insistence in the original post that the distribution must be uniform, only the (potentially) fallicous assumption that it is.

The point then being that the original post breaks down not because it isn't possible to select a finite member from an infinite pool, as has been asserted more than once, but because the post makes the potentially erroneous assumption that doing so results in a uniform distribution.

If the pair of you agree that the assertion in this post - that the probability is zero, and there is no ability to make a random selection, then may I kindly request that the PAIR of you quit riding my ******* *** over a genuine misunderstanding that neither of you have, until now, even attempted to clarify.

21. ### PeteIt's not rocket surgeryRegistered Senior Member

Messages:
10,166
And... we're done. It's been a worthwhile discussion. Thanks to everyone involved.

Although for the record, Trippy, I will point out that I explicitly said to you in post 79 that the problem of interest was regarding a uniform distribution, and you explicitly acknowledged this fact in your reply:
...and that you have repeatedly stated both explicitly and implicitly the thread that selecting randomly from a uniform distribution of the naturals was indeed possible.

Last edited: Jan 30, 2009
22. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
Do you then aknowledge that if my K-40 machine triggers after n halflives, then the probability distribution of the results is uniform?

In otherwords, that the probability of it having generated a 0 (or more correctly 00000...0) is the same as generated 99999...9 and that when considering the probability of a specific integer having been generated that it profoundly matters if we're talking about before the machine generates the number as opposed to after (I think this may have been the source of our misunderstanding).

The machine is biased towards small numbers before it starts, but only because it is biased towards 'short' numbers. Once it has operated, there is no bias towards short numbers, because if it operates after n half lives then this excludes the possibility of it generating an n-1 digit number, but not a multiple of $10^{n-1}$

And yes, this is important, because this is the context that I meant the comments about evenness in, even if I did a **** poor job of explaining it.

And I'm considering calling misunderstanding on the uniformity thing, but I don't care to go into the details of why, because in essence it comes down to semantics.

23. ### TrippyALEA IACTA ESTStaff Member

Messages:
10,890
For the record:

I am willing to cede that simply button mashing will probably produce a binomial distribution, that is biased towards 'shorter' numbers (saying smaller numbers implies P(x=0) > P(x=9) which is trivially wrong).

I am willing to cede that if I use a single rule, and a finite symbol pool, then I can only represent a finite set of numbers (and the corrollary of "If I can represent it, I can choose it" is that "If I can't represent it I can't choose it") in a finite period of time.

I am, however, not yet willing to cede that given inifinitely many possible rules to choose from, each rule of finite length, and finite complexity, that I can not, by choosing the appropriate combination of rules and symbols, represent any finite natural number (...000001 is still finite, I can build to it in a finite number of steps, as I can any other natural number, trivial zero's or not, given sufficient time (which neccessarily implie that lifespan isn't a consideration)).

I accept that if this is the case, then I should be able to prove it by induction, however, at this point you must accept that as a Chemist who implicitely has at best dabbled in pure Maths (i've studied Calculas to First year level at University), perhaps I lack the tools to explore a proof by induction, or, alternatively I lack the 'imagination' to see how the tools I do have can be used to solve the problem. The corrolary of this is that surely if an idea is wrong, then should not those who have the ability to do so consider this a teaching exercise and attempt to do so? After all - Have I not proven that I am not a crank (If you still have doubts, poke your head into the chemistry forum), and that I have the capacity to learn (or at least try to). And if the idea is as 'obviously wrong' as it is claimed, then should it not be relatively trivial to offer a proof by contradiction that I'm wrong?