Randomly selecting from an infinite number of choices

Log in or Sign up to hide all adverts.

Log in or Sign up to hide all adverts.

Trippy: I'm going to choose a number between 1 and 10...call it 4. Does that number belong to the set of naturals less than 1 million? Then were the odds of me picking "4" 1 in 10 or 1 in 1,000,000?

The point that people are trying to relay is that ANY number you choose was not picked by the TRUE and FULL set of naturals. Just because you "say" that your mind was open to the possibility of some integer with an infinite number of digits in it does not make it so. The fact that you guys refer to Megistron numbers is proof that humans CANNOT conceive of infinity, therefore we substitute the concept with Megistron, or Googolplex, or Avogadro, or some other "really, really, really big number" which has absolutely no meaning in the context of true infinity.

 

Log in or Sign up to hide all adverts.

Sure you can. You just did.

Only with one of:
- infinite different symbols, or
- an infinite typing rate, of
- infinite available time.

If you have 100 available symbols (keys on your keyboard), and you mash 100 keys every second for some finite time with an upper bound (say 100 years), then you are choosing from a finite pool.

Are you suggesting that there is no upper bound on the time that you could spend mashing your keyboard?

 

Even if he is, there is most definitely an upper bound on the time that the rest of us will sit here waiting for a random number :]

 

No, that's a method for generating the number.

 

Interesting... your statement is related to mine, in that both claim that it is possible to know the existence of something (eg a finite upper bound, or a problem with a statement), without necessarily knowing anything else about it.

Another form of my statement is to suggest an existence proof of an upper bound. And I gave you such an existence proof - mashing a keyboard with finite keys at a finite rate for a finite time gives a finite pool of possible posts.

I'm concluding a finite pool of numbers you could choose by keyboard mashing, based on the parameters of a method that you described for choosing a number, assuming that there is some upper bound on your keyboard mashing time.
The statement you replied to was referring to the set of numbers that you can possibly select by keyboard mashing, not the set of natural numbers.

So to repeat - you can generate a megistron by keyboard mashing (eg by typing "megistron"), but there are many numbers less than a megistron that you can not. (I just noticed another premise - I'm assuming some defined method of interpretation. I.e. a given set of characters must refer to a specific number.)

The potassium-40 decay method selects from a non-uniform infinite distribution of the naturals.
The coin-flip method selects from a non-uniform infinite distribution of the naturals.
You seem to be implying that the potassium-40 decay method selects from a a uniform distribution. Is that what you meant?

My mistake. I misread, and thought you were pointing at a random location on a finite line segment. I thought you were rehashing Nasor's coin-on-a-ruler method. I apologise for the confusion.

Pointing to a number line is an interesting method... What's the setup?
You have an straight number line stretching off to infinity, you're standing near zero, and you point to the line?

And your pointing precision is not infinite, so there is some lower bound on the margin of error in your pointing angle?

 

Like quadraphonic said, I'm focusing on your description of keyboard mashing as a method of choosing a random number.

We're not not talking about typing a pre-chosen number, we're talking about randomly mashing keys to choose a previously undefined number.

Look, this is silly... take a step back, take a few deep breaths, and think about whether you really want to maintain that you were choosing from a truly infinite pool of numbers by mashing a keyboard in post 60. Or, perhaps we could let it go, and focus on more interesting methods of choosing numbers, or on methods in general?

 

RJBerry noted that the full set of natural numbers contains numbers of infinite length. To randomly select from the set, each number needs to have an equal chance of being selected. But here you say that "selecting ... the number proves ... that the number is finite". Doesn't that prove that your selection doesn't give an equal chance to every number in the full set? You gave the infinite-length numbers no chance of being selected.

 

Short version:
An algorithm that chooses from an infinite uniform distribution has zero probability of halting in finite time.
Or equivalently, if an algorithm selects a random number from an infinite distribution in finite time, then the distribution is not uniform.

---------------------------------------------------

Long version:
OK, I'm trying to think about algorithms for choosing a random item from an infinite distribution.

Consider a algorithm implemented on a probabilistic turing machine with alphabet size k (including a blank), an infinite blank tape, and a source of random noise availabe for input.

In each step, the machine can add or change at the letter at its current position on its tape, and move along the tape to at most p positions (including staying still).
After n steps, there are \((pk)^n\) different combinations of steps that the machine might have done, so there are at most \((pk)^n\) different possible outputs on the tape.

Now, let's say that the algorithm is to generate a random selection from a pool of P different possibilities. How many steps (run-time) might the algorithm take to complete this task?
Well, the maximum run-time must be at least \(n_{max} = \frac{\log {P}}{\log {pk}}\), because it is at least that long before the machine might have done P different things.

But... it doesn't have to take that long every time.
Consider the case where the algorithm finishes in some fraction of its ideal maximum run-time, say \(n = r.n_{max}\).
In that case, the machine can only have done at most \(P^r\) different sets of combinations... so we'd only expect an efficient algorithm (one that minimises run-time) to stop within half its maximum time in about \(P^r/P\) of its runs (if choosing from a uniform distribution).

So, we can now construct a relationship between the size of the pool of possibilities, the distribution of the pool of possibilities, and the distribution of the algorithm's expected run time.

In particular, we can figure out what happens to the probability that the algorithm will finish within a particular number of steps for a uniform distribution as the size of the distribution goes to infinity:

Now, if I haven't made a mistake in some awkward algebra (BIG if!), the probability that the machine will halt within some number of steps t is \(\frac {(pk)^t}{P}\).
Remembering that p and k are constant and finite characteristics of the machine, then we see that as P approaches infinity, the probability that the algorithm finishes in any given finite time approaches zero.


It could also be interesting to take a converse approach, and investigate what we can determine about the random distribution from the distribution of times taken for the algorithm to halt... but that's fun for another day!

 

You seem to be avoiding the question of time. Once again, a little more bluntly:

If there is an upper limit on the time taken to select symbols (or mash keyboard), then you are choosing from a finite pool.

Yes, the coin flip model is "a method of generating a random number of potentially infinite length", just as you described for your potassium decay model.

Does the potassium decay model choose from a uniform distribution, or is it more likely to some numbers than others?

No, it's not. As distance from you to the number line increases, the angular separation between numbers decreases, and you need finer and finer precision to distinguish between numbers. And increasing the distance between numbers or bending the number line isn't going to get around the problem.

 

Trippy, you have a valid point that you can represent some arbitarily large numbers with symbols that we understand. But you cannot represent ALL of them. You think that isn't the point BUT IT IS the point. You simply cannot generate, select from, nor communicate most infinite length integers. This means they cannot be included in the pool from which you claim your ultimate selection was made. If the pool you chose from is finite, which I'm claiming it is, any number you DO come up with had a larger than 1/(infinity) chance of being selected.

P.S. with that name and tag don't go gettin' all indignant about a presumption that you hit the bong

Please Register or Log in to view the hidden image!

 

Trippy and Pete, sorry if my drug reference degraded the debate. It's funnier when you've been drinking

Please Register or Log in to view the hidden image!