View Full Version : Randomly selecting from an infinite number of choices
A while ago a math teacher of mine told a little story about a demon that's being chased by an angel. The demon goes into a hotel with an infinite number of rooms, and randomly picks a room to hide in. The point of the story was that if the angel only gets to look behind one door, there is no possible way that he could ever find the demon. Since the odds of the demon being in the room that the angel randomly selected are 1 over infinity, the chances of the angel finding the demon on the first try are exactly zero.
I thought about this for a while, and it seems like there's a problem with the concept of the scenario. Specifically, it seems like this argument could also be used to prove that the angel couldn't look behind any door, since before the angel selects a door you could prove that the odds of any given door being selected are zero - and how could the angel ever pick a door if every potential door that might be picked has zero chance of being selected? But on the other hand, there are an infinite number of doors to choose from, so it seems like the angel should be able to pick one.
So is the concept of randomly picking one choice from an infinite set of choices even mathematically meaningful? Does the very statement of the scenario violate the rules of math by assuming that the angel can randomly pick one room to look in from the infinitely many rooms available?
Steve100
01-20-09, 10:04 AM
What if the demon goes into the first door and the angel does the same?
The thing is, it is meaningless. A hotel with infinitely many rooms is impossible anyway.
I think you're confusing practicality with mathematical concepts. If we assume that the demon can pick from an infinite number of doors, then in a practical world these doors would each take up a finite space. To allow him equal probability of choosing any door at random, he needs to be given infinite time to choose his door. However, this isn't very practical due to the fact that the angle is chasing him and could possibility use some logic to deduce where he is most likely to be.
Is it meaningful mathematically?
Is there any meaning in a random variable with a flat probability density function over all the naturals?
Isn't the probability that such a variable is less than any finite number exactly zero?
Is it meaningful mathematically?
Is there any meaning in a random variable with a flat probability density function over all the naturals?
I don't know. Perhaps you could enlighten me?
RJBeery
01-20-09, 03:57 PM
Nasor: your paradox arises because the story applies physicality to the abstract math concept of infinity. Infinity does not exist in reality, it is simply a useful tool in mathematics. Think of it like this: what are the odds of you and I picking the same truly random rational number between 0 and 1? The mathematical answer is ZERO, however in reality the answer is non-zero because any method that we employ (using a computer, picking one out of thin air, etc) necessarily reduces the target set to a finite number.
I don't know. Perhaps you could enlighten me?
No, I can't. That's why I'm asking. Specifically, I'm reiterating part of your original question in response to Absane.
No, I can't. That's why I'm asking. Specifically, I'm reiterating part of your original question in response to Absane.
Sorry, I thought it was rhetorical.
mathman
01-20-09, 06:24 PM
Is it meaningful mathematically?
Is there any meaning in a random variable with a flat probability density function over all the naturals?
Isn't the probability that such a variable is less than any finite number exactly zero?
In probability theory, there is no way to have a countably infinite set of possibilities where the probabilities are all the same. As it has been noted, that to be all the same they have to be all 0, which when added up contradicts the requirement that the total probability be 1.
Is it meaningful mathematically?
Is there any meaning in a random variable with a flat probability density function over all the naturals?
Isn't the probability that such a variable is less than any finite number exactly zero?
Could you elaborate a bit more, please? What is "it?"
And if you're dealing with a probability density function, then the random variable must be an interval in the reals. So, you cannot talk about just the naturals.
The third postulate of probabilities is:
If A_1, A_2, A_3, ..., is a finite or infinite sequence of mutually exclusive events of sample space S, then
P(A_1 \cup A_2 \cup A_3 \cup ...) = P(A_1) + P(A_2) + P(A_3) + ....
If we consider the finite sequence A_1 = 1. A_2 = 2, ..., A_n = n, then P(A_k) = \frac{1}{k} for 1 \leq k \leq n.
As n \rightarrow \infty, P(A_k) \rightarrow 0.
So in dealing with a sample with and infinite number of members the calculated probability is, indeed, zero.
This does not imply that event A_k cannot happen. I honestly do not know how to explain this. Some handwaving could suffice but I won't do that.
quadraphonics
01-20-09, 07:30 PM
As others have noted, the idea of random selection amongst a (countably) infinite number of choices is ill-posed, at least in terms of classical probability. This same issue underlies the two envelopes problem, btw.
But just saying that classical probability doesn't handle this case is not very satisfying. We'd like to know why not, since the idea of randomly selecting from an infinite number of choices seems intuitively okay, at least at first glance. But perhaps it is not so simple. How would you go about choosing a door at random?
Nevertheless, improper distributions like this are used in statistics, specifically in forming uninformative prior in the context of Bayesian estimation.
BenTheMan
01-21-09, 12:54 AM
Didn't you already post a thread on this (http://www.sciforums.com/showthread.php?t=88921)?
Hi Absane,
Could you elaborate a bit more, please? What is "it?"
And if you're dealing with a probability density function, then the random variable must be an interval in the reals. So, you cannot talk about just the naturals.
"It" was supposed to be clarified in the second sentence, but I screwed up the terminology.
What I meant to ask was whether the idea of a uniform distribution over the integers is meaningful... I notice that in the other thread, DH calls this a "nonsense concept".
The third postulate of probabilities is:
If A_1, A_2, A_3, ..., is a finite or infinite sequence of mutually exclusive events of sample space S, then
P(A_1 \cup A_2 \cup A_3 \cup ...) = P(A_1) + P(A_2) + P(A_3) + ....
If we consider the finite sequence A_1 = 1. A_2 = 2, ..., A_n = n, then P(A_k) = \frac{1}{k} for 1 \leq k \leq n.
As n \rightarrow \infty, P(A_k) \rightarrow 0.
Right with you.
So in dealing with a sample with and infinite number of members the calculated probability is, indeed, zero.
This does not imply that event A_k cannot happen. I honestly do not know how to explain this. Some handwaving could suffice but I won't do that.
Surely you jest?
P=0 doesn't just imply "cannot happen"... isn't that precisely what P=0 means?
I suggest that if some event happens, then its probability was not zero. But, perhaps I'm wrong... can you think of a counterexample?
Hi Absane,
"It" was supposed to be clarified in the second sentence, but I screwed up the terminology.
What I meant to ask was whether the idea of a uniform distribution over the integers is meaningful... I notice that in the other thread, DH calls this a "nonsense concept".
Now that I fully understand what you meant, DH is correct.
Surely you jest?
P=0 doesn't just imply "cannot happen"... isn't that precisely what P=0 means?
I suggest that if some event happens, then its probability was not zero. But, perhaps I'm wrong... can you think of a counterexample?
While I won't construct the actual equations (because I am comfortable in my underwear right now) I will provide a counterexample. On a stretch of road 1 meter long you know there was a car accident. You discover that it crashed at exactly 91.1212... centimeters. What were the odds that it could have crashed elsewhere on the meter stick? Calculated probability is 1 (or 100%) according to integration over the density function from [0, 91.1212...) \cup (91.1212..., 100]. Surely, this is in contradiction.
i don't care how anyone looks at it. It is still statistically speaking 1 in an infinite amount.
John Connellan
01-22-09, 05:41 AM
Looks like infinity and probability don't go very well together ;)
John Connellan
01-22-09, 05:46 AM
I think the best way of explaining this one is tha there are 2 types of infinity. Countable and uncountable (http://www.sciforums.com/encyclopedia/Countable_infinity
As we are dealing with a countable infinity (i.e. number of doors) the probability would not be zero but infinitely small.
BenTheMan
01-22-09, 11:55 AM
I think the best way of explaining this one is tha there are 2 types of infinity. Countable and uncountable (http://www.sciforums.com/encyclopedia/Countable_infinity
As we are dealing with a countable infinity (i.e. number of doors) the probability would not be zero but infinitely small.
Does it matter?
Consider the set of integers, which is a countable infinity. Pick on. What is the probability that you picked Avagadro's number?
Didn't you already post a thread on this (http://www.sciforums.com/showthread.php?t=88921)?
No, although some of the things that were said in that thread prompted me to post this one. In that thread I was asking about how to mathematically describe the odds of selecting a certain element from an infinite set given an infinite number of guesses, and whether the odds of a specific element being picked trended toward zero or 1 as the number of guesses went to infinity (as well as some other things). Someone in that thread said that the very concept of being able to randomly pick from an infinite set was flawed, and it reminded me of the whole angel/demon scenario. Since it wasn't directly related to the topic of that thread I decided to start a new one, rather than resurrecting a thread that was over a month old.
Someone in that thread said that the very concept of being able to randomly pick from an infinite set was flawed, and it reminded me of the whole angel/demon scenario.
That would be me. Specifically, the concept of uniform distribution over the integers is a flawed concept. OTOH, suppose the demon runs by each door in sequence, each time flipping a coin to determine whether this is the room he enters. This has a well-defined mass distribution function. The angel should either choose the first door (mode) or the second (mean).
Since it wasn't directly related to the topic of that thread I decided to start a new one, rather than resurrecting a thread that was over a month old.
That's mighty decent of you. Some of the members here have no qualms in necromancing a five year old thread, let alone a one month old thread.
That would be me. Specifically, the concept of uniform distribution over the integers is a flawed concept. OTOH, suppose the demon runs by each door in sequence, each time flipping a coin to determine whether this is the room he enters. This has a well-defined mass distribution function. The angel should either choose the first door (mode) or the second (mean).
Suppose I simply tell you "There is some integer, i" and don't give you any more information than that. Aren't you now faced with an infinite number of possible values for i, all equally likely? I mean, it might lead to apparent mathematical contradiction, but it seems like that would definitely put you in a situation were 1) i could be infinitely many integers and 2) you don't have any reason to suspect any given integer over any other integer.
In the OP it's implied that the demon can move to any room by the moment the angel looks in a room. But then if it takes the demon any time at all to move between rooms, the angel has to wait forever before looking (i.e. the angel can't look), and the story contradicts itself. If we assume instead that the demon takes no time to move between rooms, then the demon can be everywhere in the hotel at once, with a 100% probability of being in every room. In that case I think it's contradictory to say the demon can hide in a particular room. The story seems to be self-inconsistent no matter how it's interpreted.
In the OP it's implied that the demon can move to any room by the moment the angel looks in a room. But then if it takes the demon any time at all to move between rooms, the angel has to wait forever before looking (i.e. the angel can't look), and the story contradicts itself. If we assume instead that the demon takes no time to move between rooms, then the demon can be everywhere in the hotel at once, with a 100% probability of being in every room. In that case I think it's contradictory to say the demon can hide in a particular room. The story seems to be self-inconsistent no matter how it's interpreted.
If you're going to get so caught up on the fluff backstory, you can simplify the scenario down to "If I randomly pick an integer, what are the odds that you will be able to guess my integer on the first try?"
RJBeery
01-23-09, 06:11 PM
Nasor, and again the answer in theory is ZERO but in reality it is greater than that because our ability truly choose a RANDOM number from an infinite set is not possible. As was mentioned, it is the same problem that arises when you consider things like the size of the hotel the Angel is in, the time it takes to visit each door, etc. The mind experiment breaks from theory when brought into "reality".
On a stretch of road 1 meter long you know there was a car accident. You discover that it crashed at exactly 91.1212... centimeters.
Wait... can the position of an event be specified to infinite precision?
If you're going to get so caught up on the fluff backstory, you can simplify the scenario down to "If I randomly pick an integer, what are the odds that you will be able to guess my integer on the first try?"
I tend to agree with RJBerry. To let you randomly pick any of an infinite number of integers requires that I wait forever, if it takes you any time at all to build the number (like "555" takes longer than "55"), in which case I never get to guess, and the question is self-inconsistent (unworthy of a solution). In reality it will always take some time to build the number.
There may well be an infinite number of galaxies. But if a criminal with a spaceship tries to use that fact to have the perfect hideout, it won't work perfectly because it takes time to move between galaxies, so the search space will always be finite.
Just a thought but surely
infinity x the infinitismal = 1
I would say the probability of choosing a door is infinitismal but certainly not zero
iceaura
01-24-09, 11:50 AM
There are a lot of things one assumes to have done in math that cannot actually be "accomplished", in some sense, in the physical world.
"Take the square root of 2 - - - - "
The question of meaningfulness does not rest on the physical accomplishment, or even the theoretical possibility of the physical accomplishment.
Suppose the countably infinite set of doors were mapped into the infinity of points on the unit circle. That is a small thing, right in front of us. Now is it possible to select one of the doors "at random" ?
Suppose the countably infinite set of doors were mapped into the infinity of points on the unit circle. That is a small thing, right in front of us. Now is it possible to select one of the doors "at random" ?
How could it ever fit ?
Wait... can the position of an event be specified to infinite precision?
Well, you treat the car as point just like you do with bodies of mass. Choose the very tip of the bumper, for example.
John Connellan
01-24-09, 07:46 PM
Does it matter?
Yep.
Consider the set of integers, which is a countable infinity. Pick on. What is the probability that you picked Avagadro's number?
Infinitely small. Not zero.
John Connellan
01-24-09, 07:52 PM
Nasor, and again the answer in theory is ZERO but in reality it is greater than that because our ability truly choose a RANDOM number from an infinite set is not possible. As was mentioned, it is the same problem that arises when you consider things like the size of the hotel the Angel is in, the time it takes to visit each door, etc. The mind experiment breaks from theory when brought into "reality".
First of all, integers are a countable infinity so probability will never be zero. Infinitely small.
Secondly, I don't understand how we are unable to choose a random number from an infinite set :shrug:
Human001
01-24-09, 09:10 PM
A while ago a math teacher of mine told a little story about a demon that's being chased by an angel. The demon goes into a hotel with an infinite number of rooms, and randomly picks a room to hide in. The point of the story was that if the angel only gets to look behind one door, there is no possible way that he could ever find the demon. Since the odds of the demon being in the room that the angel randomly selected are 1 over infinity, the chances of the angel finding the demon on the first try are exactly zero.
The problem is, you are implicitly assuming a uniform distribution. ie the probability of the angel being behind any given room is the same as any other. Of course since we have an infinite number of rooms (1,2,3,...), the probability of the angel being behind a room will be 1/k for some k. But k must approach infinity. So the probability is zero.
Assuming a different distribution, where the probability of the angel being in room n is given by 2^{-n+1}. The sum of the probabilities from n=1 to n=infinity is 1, and this is a more realistic model in the sense that the angel is more likely to be in a door near the entrance to the hotel than one infinitely far away.
This is just one model, you could come up with a zillion others, the important point being a uniform distribution is the worst of all, as it effectively forces every probability to zero.
If everyone’s really going to get so whiney about the feasibility of actually picking a number etc, imagine two people both throw a coin so that it lands randomly on a ruler. What are the odds that the exact center of the coin will land on the same point each time? How would you describe the probability distribution for where the coin will land? It would seem that you have infinitely many possible points along the ruler where the coin might land, and all are equally likely. For every single point along the ruler where the coin might potentially land you can easily prove that the odds of it landing there are zero, yet it definitely lands on one of them...
I realize that this is more like randomly picking and guessing real numbers than integers, but my point is it seems like a “real life” example of a situation where you have infinitely many equally-likely possibilites. So do we just have to accept that something can happen even though it has a probability of zero?
iceaura
01-25-09, 01:56 AM
How could it ever fit ? It's a smaller infinity, so no problem.
Think of relabeling every one of those hotel doors with the multiplicative reciprocal of its room number. Every one of those door label numbers is in the interval [0 -> 1], and so the angel can make its selection of the room to visit from that interval.
Anyway, the answer to any such questions about choosing out of an infinite set is that the chance is approaching zero, it's not actually zero.
Blue_UK
01-25-09, 08:58 AM
Infinity is not 'a large number' or 'approaching the very largest number', it's 'endless'.
1 over an ever increasing number approaches zero. 1 over infinity equals zero!
I know that in mathematics, we use infinitesimals and integrate them to get areas and that infitesimal areas can have different area ratios (and still have zero areas: 1x0 = πr2x0), but in these cases the conceptual infinities 'cancel out' when you integrate and you get your ratios back.
Well, you treat the car as point just like you do with bodies of mass. Choose the very tip of the bumper, for example.
If everyone’s really going to get so whiney about the feasibility of actually picking a number etc, imagine two people both throw a coin so that it lands randomly on a ruler. What are the odds that the exact center of the coin will land on the same point each time? How would you describe the probability distribution for where the coin will land? It would seem that you have infinitely many possible points along the ruler where the coin might land, and all are equally likely. For every single point along the ruler where the coin might potentially land you can easily prove that the odds of it landing there are zero, yet it definitely lands on one of them...
I realize that this is more like randomly picking and guessing real numbers than integers, but my point is it seems like a “real life” example of a situation where you have infinitely many equally-likely possibilites. So do we just have to accept that something can happen even though it has a probability of zero?
You can't put this into the real world - no position can ever be specified to infinite precision. The leading edge of the electron cloud of the leading atom of the car's bumper doesn't have a precise position. The position of the coins relative to the ruler is always fuzzy, and always changing.
But...
The question of meaningfulness does not rest on the physical accomplishment, or even the theoretical possibility of the physical accomplishment.
Suppose the countably infinite set of doors were mapped into the infinity of points on the unit circle. That is a small thing, right in front of us. Now is it possible to select one of the doors "at random" ?
we do have the interesting mathematical exercise of selecting a random point from a line segment, an area, or any other finite space, which would (in abstract) seem to produce a value which had zero probability of occurring.
There are a couple of points of interest in this exercise for me...
Firstly, note that (as Nasor pointed out) this is selecting from a continuum, an uncountable set. Is there any way that a continuum can be uniformly mapped onto the naturals? I.e. can a random selection from a continuum be used to generate a uniform random selection from the naturals?
Secondly (least importantly) I keep getting a "so what" feeling about the idea...
You can say "choose a random point in the unit circle", but can you actually do it... even in the abstract you can't ever specify or use that point in any meaningful way... can you?
Thirdly (most interestingly) note that there are countable computable numbers (http://en.wikipedia.org/wiki/Computable_number#Properties). This seems to mean that a random selection from a continuum must be uncomputable.
This in turn means that every possible statement of the form:
"The number selected is [insert expression here]"
...is false (except the tautological case where [insert expression here] is "the number selected").
So where does that leave us?
We can describe in the abstract an event which apparently had P=0, and yet subsequently occurred, but...
There is no true statement for which P=0.
:bugeye:
You can't put this into the real world - no position can ever be specified to infinite precision. The leading edge of the electron cloud of the leading atom of the car's bumper doesn't have a precise position. The position of the coins relative to the ruler is always fuzzy, and always changing.
Okay, so use the coin's center of gravity - that should be an exact point, regardless of any difficulties related to deciding where the edge of the coin begins. Also, it's not clear to me what you mean by "no point can ever be specified to infinite precision." I agree that I probably can't look at the coin and actually measure where its exact center of mass is with infinite precision, but that doesn't change the fact that the point should indeed exist somewhere on the coin, regardless of my ability to measure it.
I tend to agree with RJBerry. To let you randomly pick any of an infinite number of integers requires that I wait forever, if it takes you any time at all to build the number (like "555" takes longer than "55"), in which case I never get to guess, and the question is self-inconsistent (unworthy of a solution). In reality it will always take some time to build the number.
Irrelevant, all that does is prove that the number chosen is finite, it does nothing to address the finiteness of choice.
I have come to the conclusion that this question amounts to "What is the smallest rational number between 0 and 1"
The answer of course, is that there isn't one.
What i'm about to say may send some of the mathematicians on this board into paroxysms of apoplexy (or laughter) but I have also come to the conclusion that the answer to this question is as follows:
P(X=x) = δ
And I have an inkling that I can prove it as well.
Irrelevant, all that does is prove that the number chosen is finite, it does nothing to address the finiteness of choice.
It does address the "finiteness of choice", by limiting the number of choices to a finite number.
It does address the "finiteness of choice", by limiting the number of choices to a finite number.
No, it doesn't. All it does is demonstrate the tautology that a finite number is finite in length.
If I have a choice of any number, of any length, I have a choice from an infinite number of possibilities, but it doesn't matter what possibility you choose, that possibility will still be a finite number.
Your objection is meaningless.
If I have a choice of any number, of any length, ...
But you don't have such choice. If you did, and it took you longer to choose "555" than "55", I'd have to wait forever for you to choose (I never get to guess your number), in which case the problem contradicts itself.
But you don't have such choice. If you did, and it took you longer to choose "555" than "55", I'd have to wait forever for you to choose (I never get to guess your number), in which case the problem contradicts itself.
No you wouldn't.
Choice of a finite number is not the same thing as a finite number of choices.
In order to choose 555 I fon't have to count 555.
A number is a point, not a process.
Try choosing a number with 100 digits, and see if it takes you longer than choosing a number with 3 digits. Choosing a number is a process.
Okay, so use the coin's center of gravity - that should be an exact point, regardless of any difficulties related to deciding where the edge of the coin begins. Also, it's not clear to me what you mean by "no point can ever be specified to infinite precision." I agree that I probably can't look at the coin and actually measure where its exact center of mass is with infinite precision, but that doesn't change the fact that the point should indeed exist somewhere on the coin, regardless of my ability to measure it.
No, not so. the uncertainty principle tells us that there is no such point... at some scale, the coin's centre of mass is ill-defined. A fuzzy region, rather than a point.
John Connellan
01-26-09, 05:00 PM
No, not so. the uncertainty principle tells us that there is no such point... at some scale, the coin's centre of mass is ill-defined. A fuzzy region, rather than a point.
This is true actually. A lot of people mistake heisenbergs uncertainty principle to mean simply that we can't measure with infinite precision, the position of things. What it really means is that there is no definite position at all
quadraphonics
01-26-09, 05:23 PM
Wait... can the position of an event be specified to infinite precision?
Sure, supposing you accept zero precision on the velocity of said event. Which would seem to pose a problem for the car crash, which we would presume has a velocity of exactly zero...
No, not so. the uncertainty principle tells us that there is no such point... at some scale, the coin's centre of mass is ill-defined. A fuzzy region, rather than a point.Oh, for crying out loud. There will still be a point at the exact of the region of uncertainty. The center of mass might not actually be at that particular point, but it's still a defined point that will fall randomly onto one of the infinitely many points along the ruler.
Or like quadraphonics said, do a measurement that give you zero information about the velocity.
Sure, supposing you accept zero precision on the velocity of said event. Which would seem to pose a problem for the car crash, which we would presume has a velocity of exactly zero...Presumably the crash happened before you arrived to take the measurement.
Oh, for crying out loud. There will still be a point at the exact of the region of uncertainty. The center of mass might not actually be at that particular point, but it's still a defined point that will fall randomly onto one of the infinitely many points along the ruler.
No, I really don't think it works that way. But go further, down to the planck scale, and you'll run into more difficulties. There idea of infinite precision just doesn't seem to be built into the universe.
Try choosing a number with 100 digits, and see if it takes you longer than choosing a number with 3 digits. Choosing a number is a process.
It's sill totally irrelevant. The only thing you have proven is still that choosing a finite number from an infinite number of potential choices may take a finite amount of time.
This does nothing to make the qiuestion meaningless of contradictory.
The only thing it does do is potentially provide me with a piece of information that, if I know how to interprate it might provide me with information that allows me to establish an upper limit on the number you've chosen, however, that's outside the parameters of the original question.
You're assuming that you're guessing after i've guessed, but it is possible to set the experiment up so that you don't know whether or not i've guessed until after you've guessed (effectively, we're guessing at the same time).
Your objection is completely meaningless.
John Connellan
01-26-09, 06:28 PM
Oh, for crying out loud. There will still be a point at the exact of the region of uncertainty. The center of mass might not actually be at that particular point, but it's still a defined point that will fall randomly onto one of the infinitely many points along the ruler.
Or like quadraphonics said, do a measurement that give you zero information about the velocity.
.
I think that mathematically what you have said is a paradox and still needs to be explained properly (although i thought I had by saying it was a countable infinity problem). However, trying to explain infinities using real life examples will always result in arguments which do not address the pure mathematical problem which you are trying to confront.
For example, you said above there will still be a point at the center of the uncertanty, but even this can be disputed. There are no real points in this universe. Particles are limited by uncertainty but even space itself is limited by Planck volume ect!
You're assuming that you're guessing after i've guessed, but it is possible to set the experiment up so that you don't know whether or not i've guessed until after you've guessed (effectively, we're guessing at the same time).
Regardless who goes first, any number you choose will have been selected from a finite number of choices, which doesn't adhere to the problem definition.
quadraphonics
01-26-09, 06:49 PM
No, I really don't think it works that way. But go further, down to the planck scale, and you'll run into more difficulties. There idea of infinite precision just doesn't seem to be built into the universe.
Just because particles don't have well-defined positions does not imply that a continuum of possible positions does not exist, nor that some such unique position could not be specified exactly.
To even express the idea that a particle has a finite precision in its position requires you to first assume that it is possible, in principle, to distinguish between arbitrarily-closely spaced points in space (i.e., the domain of the wave function is typically the real line).
There is a world of difference between what can be measured (definitely finite precision) and what can be specified (infinite precision).
Regardless who goes first, any number you choose will have been selected from a finite number of choices, which doesn't adhere to the problem definition.
No, it wouldn't. Choosing a finite number is not the same as having a finite number of choices.
No, it wouldn't. Choosing a finite number is not the same as having a finite number of choices.
That's not the reason it would. What guarantees that the number of choices is finite is that the time you took to choose the number was finite. The mere fact that you chose the number in a finite time means that your number of choices was limited to a finite number. Any choice is made in a finite time. Thus by making a choice you didn't adhere to the problem definition.
Just because particles don't have well-defined positions does not imply that a continuum of possible positions does not exist, nor that some such unique position could not be specified exactly.
To even express the idea that a particle has a finite precision in its position requires you to first assume that it is possible, in principle, to distinguish between arbitrarily-closely spaced points in space (i.e., the domain of the wave function is typically the real line).
Right... but we're entering the realm of models of the world, the realm of abstract mathematics... which was the main thrust of my earlier post, and is what I'd actually like to be discussing.
That's not the reason it would. What guarantees that the number of choices is finite is that the time you took to choose the number was finite.
No it doesn't - choosing one number from many does not require considering all numbers.
The mere fact that you chose the number in a finite time means that your number of choices was limited to a finite number.
No it doesn't, it only proves that I chose a finite number.
Any choice is made in a finite time.
At least, something that makes sense.
Thus by making a choice you didn't adhere to the problem definition.
No, because in choosing one number from infinitiely many, I only need to consider one number - the one which I am choosing.
I do not have to count to it.
I do not have to perform a process on it besides communicating it.
I could have chosen any number higher than it.
for example, if I chose.
32465435165725132357461351324568735123213246573213 13568721324657431135431574643131324634321246543132 4643032743465321643165431354631321
A number I chose simply by mashing my numeric keypad
I could just have easily chosen
32465435165725132357461351324568735123213246573213 13568721324657431135431574643131324634321246543132 4643032743465321643165431354631322
32465435165725132357461351324568735123213246573213 13568721324657431135431574643131324634321246543132 4643032743465321643165431354631323
32465435165725132357461351324568735123213246573213 13568721324657431135431574643131324634321246543132 4643032743465321643165431354631324
Or:
32465435165725132357461351324568735123213246573213 13568721324657411354315746431313246343212465431324 64303274346532164316543135463132154754516534321324 53543216545315372456374874547316468732413535674373 46874645751643418673515486768767637435133676346876 46468761357685748967454687434683435687454167355374 31687646468586457986743484354897464654321654679678 46343134657489745643167986431165465346543416548678 64345674786413545674324687654132458674564687435456 78654687664984654896576451979456346435737684657643 54697644753768796464897465498766498674897634169744 15646498673468764564967468776874687648679678464687 89764165764354687685748964867465576546546876546546 51654654
also a finite number, but one that is many times larger (also produced by mashing my keypad).
The only thing that the fact that you're not still waiting for this post proves is that all of these numbers are finite.
Id doesn't change the fact that they were selected randomly from a countably infinite pool of numbers (IE the set of all natural numbers).
The mere fact that you chose the number in a finite time means that your number of choices was limited to a finite number. Any choice is made in a finite time. Thus by making a choice you didn't adhere to the problem definition.
We're talking about demons and angels, zanket. Supernatural beings such as this are certainly capable of performing a supertask (http://en.wikipedia.org/wiki/Supertask).
Id doesn't change the fact that they were selected randomly from a countably infinite pool of numbers (IE the set of all natural numbers).
Ummm, no. You chose from a finite pool. There was a 100% certainty that the numbers chosen by your method would be less then a megistron, for example.
Ummm, no. You chose from a finite pool. There was a 100% certainty that the numbers chosen by your method would be less then a megistron, for example.
I beg to differ.
Megistron is simply 10^{10^{10^{10^{10^{10....}}}}} some insanely large number of times
In terms of practicallity, then yes, I limit myself by simply button mashing, because i'm limited by how time and character rates (as well as server space).
However I could just have easily chosen
http://mathworld.wolfram.com/images/eps-gif/megistron_1000.gif+1
Or even
http://mathworld.wolfram.com/images/eps-gif/ncirc_1000.gif
Where n>10
Or for that matter "10 in a megagon"
They'd still be numbers chosen at random, from an infinite pool, and they're still larger then Megistron.
I could just have easily chosen
...
32465435165725132357461351324568735123213246573213 13568721324657411354315746431313246343212465431324 64303274346532164316543135463132154754516534321324 53543216545315372456374874547316468732413535674373 46874645751643418673515486768767637435133676346876 46468761357685748967454687434683435687454167355374 31687646468586457986743484354897464654321654679678 46343134657489745643167986431165465346543416548678 64345674786413545674324687654132458674564687435456 78654687664984654896576451979456346435737684657643 54697644753768796464897465498766498674897634169744 15646498673468764564967468776874687648679678464687 89764165764354687685748964867465576546546876546546 51654654
No, not just as easily, which proves my point. Took you longer to choose this one.
The only thing that the fact that you're not still waiting for this post proves is that all of these numbers are finite.
It also proves that you didn't select from an infinite number of choices.
We're talking about demons and angels, zanket. Supernatural beings such as this are certainly capable of performing a supertask (http://en.wikipedia.org/wiki/Supertask).
:) Good to know about a supertask. Wikipedia rocks!
They'd still be numbers chosen at random, from an infinite pool, and they're still larger then Megistron.
To be random you'd have to have equal odds of choosing any of those in the pool. Doesn't look like that was the case in your example.
No, not just as easily, which proves my point. Took you longer to choose this one.
Not neccessarily, the only thing you can say with certainty is that it took me longer to type it.
It also proves that you didn't select from an infinite number of choices.
No it doesn't, the only thing it proves is that the number I have chosen is a finite number.
More to the point, if I selected it from a finite number of choices, then you should be able to tell me how many other choices I had.
So go on then.
To be random you'd have to have equal odds of choosing any of those in the pool. Doesn't look like that was the case in your example.
Based on what evidence?
Hmmm?
More to the point, if I selected it from a finite number of choices, then you should be able to tell me how many other choices I had.
No, it's enough to know that it takes more time for you to randomly select a number, the more digits it can have. That's all I need to know, to know that any number you choose was not chosen from an infinite pool.
Based on what evidence?
You're being argumentative now.
No, it's enough to know that it takes more time for you to randomly select a number, the more digits it can have. That's all I need to know, to know that any number you choose was not chosen from an infinite pool.
No. If I selected from a finite pool, with the information you have, and the claims you're making, you should be able to tell me the size of the pool I was selecting from, so, come on, what was it?
You're being argumentative now.
Oh, right. So asking you to prove your assertions in the maths section of a science forum is being argumentative?:confused:
No. If I selected from a finite pool, with the information you have, and the claims you're making, you should be able to tell me the size of the pool I was selecting from, so, come on, what was it?
No, I shouldn't be able to tell that.
Oh, right. So asking you to prove your assertions in the maths section of a science forum is being argumentative?:confused:
When you're being argumentative, sure. It's not up to me to prove that your megistron number wasn't chosen at random. It's enough for me to know that any algorithm that randomly chooses from an infinite pool will never return a number. For a pseudo-random number generator on a computer, for example, you'd need an infinite-bit computer, or an emulator of that. There'd be an infinite loop or process somewhere.
BenTheMan
01-27-09, 12:16 PM
Yeah zanket, but as DH pointed out, you're counting angels on pinheads now. The question is clearly answered, and you're quibbling over the implementation of the algorithm.
Sub-topics were introduced. I'm talking about randomly selecting from an infinite number of integers. No angels or supertasks. When an angel or demon can do a supertask, the problem isn't very interesting; probably all sorts of contradictions can be shown then.
No, I shouldn't be able to tell that.
Oh right.
So you 'know' that it wasn't randomly selected from an infinite pool, but you can't tell me what the pool size was.
When you're being argumentative, sure. It's not up to me to prove that your megistron number wasn't chosen at random. It's enough for me to know that any algorithm that randomly chooses from an infinite pool will never return a number. For a pseudo-random number generator on a computer, for example, you'd need an infinite-bit computer, or an emulator of that. There'd be an infinite loop or process somewhere.
I disagree.
The only thing that's required is the potential to generate an 'infinite number'.
If the program actually generates an infinite number (or, if you prefer, and infinite loop) then you've done something wrong.
I'll give you an example.
I have a single atom of Potassium-40.
I know that an Ensemble of Potassium-40 atoms will undergo all three types of Beta decay with a half life of 1.28x10^9 years, but, I can not know how long that individual atom is going to last. It might decay 1 second from now, 100 years from now, or it might 'never' decay.
That Potassium-40 atom is in a chamber that measures when that Potassium 40 decays to Argon or Calcium (depending on the decay method). This chamber is connected to a software switch.
The software switch controls a program that checks on it's state once every loop, and generates a random number between 0 and 9 every loop.
When (and if) the atom decays, the program stops, and outputs the string as a random number.
Or, if you want to get into supertasks, I sit in front of the number line, close my eyes, spin around three times, and point at a location on it at random.
Yeah zanket, but as DH pointed out, you're counting angels on pinheads now. The question is clearly answered, and you're quibbling over the implementation of the algorithm.
Yes.
RJBeery
01-27-09, 04:23 PM
Zanket is correct. Truly choosing a random number from an infinite list is not possible. There is no way in reality to represent the infinite choices from which to choose. Trippy's example of pointing to a point on a circle (or any other example) does not work because it involves measuring a point to infinite precision - as in INFINITELY "smaller" than the Planck length.
The only place this is possible is in our heads because we can think in abstract terms such as infinity. We cannot truly comprehend infinity, though, and any number that Trippy comes up with may in fact belong to the set of infinite integers however it also belongs to the SUBSET of those numbers that humans are able to conceive of, which necessarily excludes most integers with an infinite number of digits.
Zanket is correct. Truly choosing a random number from an infinite list is not possible. There is no way in reality to represent the infinite choices from which to choose. Trippy's example of pointing to a point on a circle (or any other example) does not work because it involves measuring a point to infinite precision - as in INFINITELY "smaller" than the Planck length.
The only place this is possible is in our heads because we can think in abstract terms such as infinity. We cannot truly comprehend infinity, though, and any number that Trippy comes up with may in fact belong to the set of infinite integers however it also belongs to the SUBSET of those numbers that humans are able to conceive of, which necessarily excludes most integers with an infinite number of digits.
You're falling into the same trap as Zanket - you're assuming we have to represent the entire list - we don't, nor do we have to assess the existence of the list, we simply have to have a way to represent a member of the set represented by that list.
And no, my example of pointing to a location on a number line does not rely on measuring a point to infinite precision.
Also note that I have (in general) confined my part of the discussion to one particular infinite list of numbers - the natural numbers, the fact that i'm excluding possibilities is wholly irrelevant, the set of natural numbers is still an infinite set.
Or would you care to name the highest natural number?
RJBeery
01-27-09, 05:53 PM
Trippy, you only need to be able to represent the entire list IF you are requiring that the number be chosen at random from that entire list. In this case RANDOM means that each choice has an equally likely chance of being chosen. You could say "prove that the number 3 was not chosen randomly from an infinite list", and the fact that you cannot possibly think of, write down, or even fathom in your head ONE of the infinite choices of integers which have an infinite number of digits in them means that the number 3 was in fact chosen from a SUBSET of that infinite list. Yes, 3 belongs to the infinite list of integers set but no, it was not chosen randomly from that set. It was chosen "randomly" from a subset consisting of those numbers which we are capable of comprehending.
Also, how does pointing to a location on a number line representing an infinite number of points not require infinite measuring precision? Not possible as far as I know!
So you 'know' that it wasn't randomly selected from an infinite pool, but you can't tell me what the pool size was.
You don't need to know the precise size of something to know it's not infinite.
But, I gave you an upper bound earlier, and I'll give it to you again - there are fewer than a megistron numbers in the pool of numbers that are possible for you to select. Yes, there are numbers that are larger than a megistron in that pool, but there are many(!) more numbers less than a megistron that are not.
I have a single atom of Potassium-40.
I know that an Ensemble of Potassium-40 atoms will undergo all three types of Beta decay with a half life of 1.28x10^9 years, but, I can not know how long that individual atom is going to last. It might decay 1 second from now, 100 years from now, or it might 'never' decay.
That Potassium-40 atom is in a chamber that measures when that Potassium 40 decays to Argon or Calcium (depending on the decay method). This chamber is connected to a software switch.
The software switch controls a program that checks on it's state once every loop, and generates a random number between 0 and 9 every loop.
When (and if) the atom decays, the program stops, and outputs the string as a random number.
That's a different question. A random selection from a non-uniform infinite distribution is easy. As stated earlier in the thread, just flip a coin, and count the number of flips it takes until heads comes up.
The problem at hand is taking a random selection from a uniform distribution of the naturals.
Or, if you want to get into supertasks, I sit in front of the number line, close my eyes, spin around three times, and point at a location on it at random.
And how does that specify a location to infinite precision? Just how large are the error bars on a pointing finger?
And even if you do have an infinitely precise pointer, how does that help you select a random natural number? This is not irrelevant - as I pointed out earlier, I suspect choosing randomly from a continuum is a fundamentally different problem to choosing from a discrete distribution. At least, I can't find a way of getting from one to the other... but if anyone else can find a way, I'd be grateful.
So you 'know' that it wasn't randomly selected from an infinite pool, but you can't tell me what the pool size was.
Or, try this:
Let's say that you have a keyboard with k keys, that you strike r keys per second while composing a post, which takes t seconds.
There are k^{rt} possible posts that could result.
We know that k, r, and t are finite, therefore k^{rt} is finite.
Or more specifically:
For a 100 key keyboard and a keyboard-mashing rate of 100 keys per second, then a post 100 years in the making gives you an upper bound of only 10^{10^{12}} or so for the size of the pool of numbers that you could possibly choose using that method.
In my next post, I'll extend this idea to the more abstract realm of random-number-generating algorithms.
You don't need to know the precise size of something to know it's not infinite.
There's something wrong with this statement, but I can't quite put my finger on it, and at this point I lack the motivation (or incentive) to try.
But, I gave you an upper bound earlier, and I'll give it to you again - there are fewer than a megistron numbers in the pool of numbers that are possible for you to select.
You're defining a finite pool.
Yes, there are numbers that are larger than a megistron in that pool, but there are many(!) more numbers less than a megistron that are not.
No there aren't.
In an infinite pool, there are infinite numbers greater than a megistron, but there are only a megistron of numbers less than the megistron (assuming, once again, we're talking about the set of natural numbers).
That's a different question. A random selection from a non-uniform infinite distribution is easy.
No it isn't. It's a method of generating a random number of potentially infinite length.
As stated earlier in the thread, just flip a coin, and count the number of flips it takes until heads comes up.
Completely different situation.
The problem at hand is taking a random selection from a uniform distribution of the naturals.
Right.
And how does that specify a location to infinite precision?
It doesn't have to have infinite precision, a 1 is a 1 until you reach 2.
Just how large are the error bars on a pointing finger?
Only relevant if the above irrelevant conjecture is accepted.
And even if you do have an infinitely precise pointer, how does that help you select a random natural number?
I don't need an infinitely precise pointer. This is a wholly irrelevant, and, in my opinion, completely ridiculous objection, and if you've read through my posts, you might actually understand why I say this.
And it helps select a random natural number because each location corresponds to a natural number on the line of natural numbers.
This is not irrelevant - as I pointed out earlier, I suspect choosing randomly from a continuum is a fundamentally different problem to choosing from a discrete distribution.
And there in lies the point that you've been missing (funnily enough) this is why i've mentioned the natural numbers repeatedly 1.5 isn't a natural number. 1.5 and Pi are irrelevant (at this level).
At least, I can't find a way of getting from one to the other... but if anyone else can find a way, I'd be grateful.
Go back and re-read some of my earlier posts, and you might begin to understand.
Here's a couple of clues.
It has to do with me continually saying that i'm talking about the set of natural numbers, and I forget what the other clue was meant to be - something to do with the phrase 'Vanishingly small, but non zero'.
Or, try this:
Let's say that you have a keyboard with k keys, that you strike r keys per second while composing a post, which takes t seconds.
There are k^{rt} possible posts that could result.
We know that k, r, and t are finite, therefore k^{rt} is finite.
Or more specifically:
For a 100 key keyboard and a keyboard-mashing rate of 100 keys per second, then a post 100 years in the making gives you an upper bound of only 10^{10^{12}} or so for the size of the pool of numbers that you could possibly choose using that method.
In my next post, I'll extend this idea to the more abstract realm of random-number-generating algorithms.
I've already addressed this, multiple times.
This comes back to the point that i've made several times about the difference between choosing teh number and communicating the number. You're falling into the same trap that Zanket is.
By your logic, I could never write the number Megistron, or Grahams number, however, if I have the appropriate symbols, and we all understand what the symbols mean, then there is no limit.
RJBeery
01-27-09, 06:54 PM
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.
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?
1 in 10, because you defined it as being between 1 and ten. The fact that '4' also happens to be part of a larger sample set is wholy irrelevant, because when you laid out the problem you defined your sample size as being 10.
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.
I understand fully what other people are saying, I simply disagree with them based primarily on my understanding of statistics. What's being done here is, in essence quibbling over algorithms and notation, nothing more.
This has nothing to do with 'openess of minds' has nothing to do with it.
When talking about Megistron, you're talking about a specific number.
The simple fact of the matter is that I can select and communicate Megistron as easily as I can select and communicate one hundred. Megistron is simply a name like 'Ten' or 'Two'
The point you're missing is that what you, pete, and Zanket are obsessing over are limitations of communnicating a number, not limitations on the choice of the number.
I'll say it once again. I can select any natural number between 0 and infinity. The only thing that selecting and communicating the number proves is that the number is finite, and that I have the appropriate symbology to communicate the number.
And before ya'all start frothing at the mouth.
Bare in mind the lessons you learned in your primary school mathematics classes.
The name of every number is also the description of how to make it.
745352 Really means "7 lots of 10 raised to the fifth power and 4 lots of 10 raised to the fourth power and 5 lots of ten raised to the third power and 3 lots of 10 raised to the second power and 5 lots of 10 raised to the first power and 2 lots of 10 raised to the zeroth power".
Talking about Megistron or '10 in a megagon' is no different, it's naming the number and describing how to calculate it.
By your logic, I could never write the number Megistron, or Grahams number
Sure you can. You just did.
...however, if I have the appropriate symbols, and we all understand what the symbols mean, then there is no limit.
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?
quadraphonics
01-27-09, 07:32 PM
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 :]
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?
Wholly irrelevant.
I've already addressed this point, and you're focussing only on one method of communicating the number.
quadraphonics
01-27-09, 07:54 PM
I've already addressed this point, and you're focussing only on one method of communicating the number.
No, that's a method for generating the number.
There's something wrong with this statement, but I can't quite put my finger on it, and at this point I lack the motivation (or incentive) to try.
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 (http://en.wikipedia.org/wiki/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.
You're defining a finite pool.
...
In an infinite pool, there are infinite numbers greater than a megistron, but there are only a megistron of numbers less than the megistron (assuming, once again, we're talking about the set of natural numbers).
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.)
No it isn't. It's a method of generating a random number of potentially infinite length.
...
Completely different situation.
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?
It doesn't have to have infinite precision, a 1 is a 1 until you reach 2.
...
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?
I've already addressed this point, and you're focussing only on one method of communicating the number.
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 (http://www.sciforums.com/showpost.php?p=2151095&postcount=60). Or, perhaps we could let it go, and focus on more interesting methods of choosing numbers, or on methods in general?
I'll say it once again. I can select any natural number between 0 and infinity. The only thing that selecting and communicating the number proves is that the number is finite, and that I have the appropriate symbology to communicate the number.
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.
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 [url=http://www.sciforums.com/showpost.php?p=2151095&postcount=60]post 60[/post]. Or, perhaps we could let it go, and focus on more interesting methods of choosing numbers, or on methods in general?
Again, you're quibbling over algorythms.
And you're still rehasing stuff that i've already addressed - namely the availability of symbols and such.
Once again, Yes, I maintain that with the appropriate usage and combinations of symbols, I can, as long as we understand what those symbols mean, and understand them to be the same thing, then there is no limit on my range of numbers I can choose.
I can choose an arbitrarily large natural number between zero and infinity, and that number has the same probability of being chosen as any other.
Even if you think of it as a process of elimination of ranges of unwanted numbers, then i'm still selecting from an initially infinite set.
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.
Last time I checked Infinite and Transfinite cardinal numbers weren't actually part of the set of Natural numbers, so unless you have some proof otherwise you're wrong about this (and therefore so was RJBeery).
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 (http://en.wikipedia.org/wiki/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.)
I've already addressed both of these points, multiple times, and I am disinclined to go over them again.
Once again, it comes down to, as Ben put it, you quibbling over Algorithms.
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?
No.
The coin flip model, is, in essence a binomial distribution. The equivalent would be generating a string of random numbers between 0 and 9 until you hit your first 6, then calling that your number.
That, however, is not the process I'm describing.
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.
Not that it matters, but I did state that the line was infinite in length.
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?
Something like that, although I didn't specify where you were standing (and have no intention of specifiing that.
And your pointing precision is not infinite, so there is some lower bound on the margin of error in your pointing angle?
Pointing precision is irrelevant.
Let's assume that i'm talking about a massless version of one of Einsteins 'rigid rods' that happens to be infinite in length.
The important part, and the assumption that has been widely missed being that each number has some finite 'width' on the number line (think of a histogram - hence my continual insistence that i'm talking about natural numbers), and by agreement my pointing rod is either pointing at one number or another number (we might consider it as if we were generating a natural number by truncating a rational number - for example, so that if the pointing rod should point at 3/2, then this becomes 1).
Wait I know the solution! Maybe if Trippy the Hippy shared some of his, uh, 'mind-expansion methods' then we could ALL generate, select and communicate infinite length integers...:m::m::m:
I strongly resent the implication that I participate in illegal activities.
The solution simply requires some forethought.
I could choose (for example):
"Grahams number in an N-gon where N is equal to Grahams number"
It's an arbitraily large number, one that's so big that it can't be written in the sense that 123 can, nor can it be written as a power stack - i'm not even sure if Knupfs arrow notation would be helpful here. Certainly i'd never get there by Button mashing (unless we agreed the characters on my keyboard were some very very large numbers indeed).
I could just have easily typed:
"Grahams number in N nested N-gons where N is equal to grahams number".
Sadly, I trust that my point will be missed entirely.
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!
Once again, Yes, I maintain that with the appropriate usage and combinations of symbols, I can, as long as we understand what those symbols mean, and understand them to be the same thing, then there is no limit on my range of numbers I can choose.
...
I can choose an arbitrarily large natural number between zero and infinity, and that number has the same probability of being chosen as any other.
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.
The coin flip model, is, in essence a binomial distribution. The equivalent would be generating a string of random numbers between 0 and 9 until you hit your first 6, then calling that your number.
That, however, is not the process I'm describing.
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?
Pointing precision is irrelevant.
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.
RJBeery
01-27-09, 10:30 PM
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 ;)
RJBeery
01-27-09, 10:35 PM
Trippy and Pete, sorry if my drug reference degraded the debate. It's funnier when you've been drinking ;)
Last time I checked Infinite and Transfinite cardinal numbers weren't actually part of the set of Natural numbers, so unless you have some proof otherwise you're wrong about this (and therefore so was RJBeery).
OK, I buy that. Let's go back to the atom decay method you proposed. Like you say, the atom could decay in 1 second, 1 year, 100 years, etc., or 'never', which is an indefinite wait, still waiting for decay. I accept that your method, when it returns, will have randomly selected from the full set of naturals (equal chance of choosing any number in the set). So you are right that the selection process can be finitely long; it need not be infinitely long like I claimed before.
Getting back to the original problem posed by Nasor (#23), we ask: when you randomly select from the full set of natural numbers, what are my odds of guessing your number on the first try? Are the odds zero or not?
For my guess of your number, I could use the same method to select a number as you used. We could select in parallel; we need not make our selections in any particular order. We just can't compare our selections until we have both made them. Either one or both of us could wait indefinitely to make a selection, in which case the problem hasn't contradicted itself (unlike what I claimed before), it's just that all the data (our selections) hasn't come in yet--we won't necessarily wait forever. Let us both have made our selections. We know we've both made them in a finite time, hence our selections are finite numbers. Then the odds that I selected the same number as you did (guessed your number on the first try) are not zero.
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.
I've already discussed this, not doing it again.
You're also assuming that my ability to mash the keyboard or select the symbols is limited in time, or that there's some upper limit on the 'value' of the symbols I can use.
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?
Apparently you're reading a post that isn't mine.
The potassium decay model chooses from a uniform distribution.
It's just as likely to produce
1 as it is 8765237658476592465347652947568023478029182074367
Remember that in my post the potassium atom decay isn't actually what dictates the number generated.
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.
Yes it's wholly irrelevant - you're assuming that I have to know what the number is in order to point to it.
But that's not what I said was it.
I didn't say "Choose a number and point to it" I said "Point to a location (with your eyes closed) and that's the number you've chosen".
It's a subtle, but very important difference.
P.S. with that name and tag don't go gettin' all indignant about a presumption that you hit the bong ;)
The term "Hippy Chemist" relates to my area of knowledge, and my job (in this case environmental chemistry).
In this case, Trippy was an adult nickname given to me by friends because of some of the areas of physics I like talking about, and some of the places I take it in fligvhts of fancy.
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.
See, that's the thing, you don't (neccessarily) have to represent all of them, just enough of them.
You simply cannot generate, select from, nor communicate most infinite length integers.
But isn't that a red herring, if Trippy is right that the full set of natural numbers contains no numbers of infinite length? And if Trippy is right...
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.
... then it seems his atom decay method would properly make a random selection from an infinite pool.
OK, I buy that. Let's go back to the atom decay method you proposed. Like you say, the atom could decay in 1 second, 1 year, 100 years, etc., or 'never', which is an indefinite wait, still waiting for decay. I accept that your method, when it returns, will have randomly selected from the full set of naturals (equal chance of choosing any number in the set). So you are right that the selection process can be finitely long; it need not be infinitely long like I claimed before.
Great. Progress.
Getting back to the original problem posed by Nasor (#23), we ask: when you randomly select from the full set of natural numbers, what are my odds of guessing your number on the first try? Are the odds zero or not?
They're small, but non-zero.
I believe I described them earlier in this thread as P(X=x) = δ
As I said. The question is exactly the same as asking "What is the smallest rational number greater than zero"
For my guess of your number, I could use the same method to select a number as you used.
Correct.
We could select in parallel; we need not make our selections in any particular order. We just can't compare our selections until we have both made them.
I believe I suggested this at one point.
Either one or both of us could wait indefinitely to make a selection, in which case the problem hasn't contradicted itself (unlike what I claimed before), it's just that all the data (our selections) hasn't come in yet--we won't necessarily wait forever.
Correct - err, I think.
Let us both have made our selections. We know we've both made them in a finite time, hence our selections are finite numbers. Then the odds that I selected the same number as you did (guessed your number on the first try) are not zero.
Which is precisely what i've argued right from the start.
There's something that I haven't mentioned thus far in this thread, because I haven't been able to explain it well (per se).
Essentially (this will probably set Pete swearing, because it's close to what he was saying, but not the same).
Disagreements to one side for a moment, over our ability to represent the number. And, for simplicities sake, i'm going to work with small numbers, because it's easier to explain with them.
This is something of an intuitive approach, and at this point I have no idea how to formalize it mathmatically.
We all agree that, when dealing with natural numbers, we disregard the initial zero's correct?
So when we say 1 what we're really describing is ...000000001 with an infinite number of zeros before hand.
If we're choosing a number between 1 and 10, what we're really choosing is a number between ...0000000001 and ...0000000010
PLease excuse my rambling, i'm not even sure if this is entirely relevant, my thought processes are occasionally chaotic, great for lateral thinking, but a pain in the arse at times.
If I ask Zanket to choose a number between 1 and infinity, and I do likewise, we could probably, somewhat arbitrarily make an argument that the probability of the two numbers N and M being identical is 1/N where N>M, because intuitively, although the range of possibile values for N and M are infinite, as long as the are Natural numbers, they are neccessarily finite.
I'm not sure i've done a good job of explaining it.
Essentially, I guess what I'm saying is that if two people select numbers at random, where the only restriction on those numbers is that they are both Elements of the set of Natural numbers that lie between 1 and infinity, then asking "What is the probability that the two numbers are the same" then neccessarily this is the same as selecting the same number twice between 1 and the upper limit.
I suppose what i'm approaching here may be one of the limiting theorems, but i'm not sure.
I believe I suggested this at one point.
You did. My post is just a stream of consciousness, potentially repeating stuff said before by others.
Correct - err, I think.
I'm saying, for example, after waiting a billion years for the atom to decay, it could decay in the next moment--or not. The random selection method waits indefinitely for the atom to decay, but--subtle difference--it's not waiting forever (there's no infinite wait loop), like I claimed before.
Essentially, I guess what I'm saying is that if two people select numbers at random, where the only restriction on those numbers is that they are both Elements of the set of Natural numbers that lie between 1 and infinity, then asking "What is the probability that the two numbers are the same" then neccessarily this is the same as selecting the same number twice between 1 and the upper limit.
Where the "upper limit" is the highest of the original two numbers. That could be right; I'd have to think about it more.
I think it's interesting that it's possible to randomly select from an infinite number of (finite) numbers. Thanks for teaching!
I'm saying, for example, after waiting a billion years for the atom to decay, it could decay in the next moment--or not. The random selection method waits indefinitely for the atom to decay, but--subtle difference--it's not waiting forever (there's no infinite wait loop), like I claimed before.
Right, this is what I guessed you meant - waiting for an undefined, unpredictable period of time.
I've already discussed this, not doing it again.
You're also assuming that my ability to mash the keyboard or select the symbols is limited in time, or that there's some upper limit on the 'value' of the symbols I can use.
No, I don't think you've discussed it. I think you've skimmed some parts of my posts that you find difficult to follow, and jumped to what you [think I'm saying, without really attempting to consider what I am saying.
Yes, I am assuming that your ability to mash the keyboard is limited in time. That is the heart of the objection, and I have said it several times.
No, I'm making no assumptions about the value of the symbols, only that the rules of interpretation are predefined.
But whatever. You clearly don't want to discuss the keyboard-mashing exercise any more.
Apparently you're reading a post that isn't mine.
The potassium decay model chooses from a uniform distribution.
Not true. You're not thinking it through properly. Perhaps you could run a simulation?
There are two serious issues that prevent this being a uniform distribution.
Firstly:
If the program loops once every t half lives, the the chance that it decays in any given loop is 1 - 0.5^t... but only if the atom has not already decayed in an earlier loop.
So, the probability that the model produces a 1 digit number is 1 - 0.5^t
The probability that it produces a 2 digit number is 0.5^t(1 - 0.5^t), which is the probability that it doesn't decay in the first loop times the probability that it decays in the second given it survived the first.
Similarly, the probability that it produces a 3 digit number is 0.5^{2t}(1 - 0.5^t)
Generalising, the probability that it produces an n-digit number is 0.5^{(n-1)t}(1 - 0.5^t)
You can see that the probability slowly but surely gets smaller as the number of digits climbs.
If you add these probabilities up, you'll reach 50% for digits up to 1/t, 90% for digits up to about 7/t, 99% for digits up to 69/t, 99.9% for digits up to 693/t...
So to put some numbers in, if the program performs a billion loops per second, there is a 99.9% that the number produced will have fewer than 3x10^27 digits.
Now, the second serious issue:
The chance of producing a specific number is further reduced because of the way the numbers are generated.
If the program produces a one digit number, then there is one chance in ten that it will be a 1.
But if the program produces a 6 digit number, then the is only one chance in a million that it will be 347692.
So to sum up:
It's just as likely to produce
1 as it is 8765237658476592465347652947568023478029182074367
If the program loops a billion times a second, then:
P(1) = \frac {1 - 0.5^{(4 \times 10^{-25})}}{10}
P(876523765847659246534765294756802347802918207436 7) = 0.5^{(192 \times 10^{-25})} \frac {1 - 0.5^{(4 \times 10^{-25})}}{10^{48}}
So, it has almost the same (very slightly less) chance of producing a 49 digit number as producing a 1 digit number, but it is about 10^47 times less likely to produce a specific 49 digit number (eg 8765237658476592465347652947568023478029182074367) than it is to produce a specific 1 digit number (eg 1).
...and there is less than 0.1% chance that it will run long enough to produce a number greater than a googolplex.
Yes it's wholly irrelevant - you're assuming that I have to know what the number is in order to point to it.
No, I'm assuming no such thing.
When your pointer comes to rest, you need to identify the number at which it is pointing. If the precision of your pointer is limited, then you won't always be able to tell what number has been chosen.
Also, you again have a non-uniform distribution, since numbers close to you will have a greater angular separation than numbers further away.
RJBeery
01-28-09, 10:11 AM
Does a hotel with infinite rooms include room numbers with infinite digits? I think Trippy would say no but I'm not so sure. What if you labeled the rooms in base 1, so they are 1, 11, 111, 1111, 11111...then, by definition, infinite rooms = infinite digits. You (Tripster) are making the distinction that the naturals are countable, but we are debating the problem posed in the OP and maybe that's the source of our disagreement.
There are two serious issues that prevent this being a uniform distribution.
Firstly:
If the program loops once every t half lives, the the chance that it decays in any given loop is 1 - 0.5^t... but only if the atom has not already decayed in an earlier loop.
...
Trippy's method depends on the decay of a single atom. Then you can ignore the half life of the element, because any single radioactive atom decays at any moment between now and eternity, with an equal chance of decaying at any of those moments. I'm not sure about the need to generate a random number 0-9 at each step. I think it's enough to initialize a variable at zero, check atom, stop if decayed, otherwise increment variable and go to step 2. Wikipedia notes that radioactive decay provides the gold standard for random number generation.
Does a hotel with infinite rooms include room numbers with infinite digits?
I say no. I say every room has a finite room number.
Not true. You're not thinking it through properly. Perhaps you could run a simulation?
There are two serious issues that prevent this being a uniform distribution.
Firstly:
If the program loops once every t half lives, the the chance that it decays in any given loop is 1 - 0.5^t... but only if the atom has not already decayed in an earlier loop.
So, the probability that the model produces a 1 digit number is 1 - 0.5^t
The probability that it produces a 2 digit number is 0.5^t(1 - 0.5^t), which is the probability that it doesn't decay in the first loop times the probability that it decays in the second given it survived the first.
Similarly, the probability that it produces a 3 digit number is 0.5^{2t}(1 - 0.5^t)
Generalising, the probability that it produces an n-digit number is 0.5^{(n-1)t}(1 - 0.5^t)
You can see that the probability slowly but surely gets smaller as the number of digits climbs.
If you add these probabilities up, you'll reach 50% for digits up to 1/t, 90% for digits up to about 7/t, 99% for digits up to 69/t, 99.9% for digits up to 693/t...
So to put some numbers in, if the program performs a billion loops per second, there is a 99.9% that the number produced will have fewer than 3x10^27 digits.
It is my understanding that half-life is a property of many atoms, and that any specific atom has a constant probability of decaying at any moment (which is why the property of half life emerges in the first place).
Now, the second serious issue:
The chance of producing a specific number is further reduced because of the way the numbers are generated.
If the program produces a one digit number, then there is one chance in ten that it will be a 1.
But if the program produces a 6 digit number, then the is only one chance in a million that it will be 347692.
Right.
And if I button-mash a 1 digit number, it has a 1 in 10 chance of being a 1, but if I button-mash a 6 digit number it has a 1 in a million chance of being 347692. But, it ALSO has a 1 in a million chance of being 000001 - exactly the same as the program i've described (actually, echnically because i'm human i'm less likely to 'randomly select' a sequence that repeats like that because of the way our brains are wired, but that's quibbling).
No, I'm assuming no such thing.
When your pointer comes to rest, you need to identify the number at which it is pointing. If the precision of your pointer is limited, then you won't always be able to tell what number has been chosen.
No, Somebody does, but that somebody wasn't neccessarily specified as being me now was it? and before you tell me to stop being ridiculous, think about it for a minute, and think about why I might have described it as being a 'super task' to begin with.
Also, you again have a non-uniform distribution, since numbers close to you will have a greater angular separation than numbers further away.
I had considered angular resolution - for lack of a better way of describing it, and I was almost certain you would bring it up, but i'm not convinced of it's relevance, and if the number line happens to loop around in a very large circle, or a very long helix (well, I suppose I should say infinite in both cases) then it doesn't matter.
Does a hotel with infinite rooms include room numbers with infinite digits? I think Trippy would say no but I'm not so sure. What if you labeled the rooms in base 1, so they are 1, 11, 111, 1111, 11111...then, by definition, infinite rooms = infinite digits. You (Tripster) are making the distinction that the naturals are countable, but we are debating the problem posed in the OP and maybe that's the source of our disagreement.
You're right, i'm going to say no, because having infinite labels is not the same as having labels of infinite length.
Every room label will be of finite length.
Pete:
As far as Button mashing goes, let us make this clear.
I understand exactly what you're saying, i'll pm you about it later.
There is a point that I am trying to make, and it was mis-interpreted by RJBeery at one point. The problem with the point I am trying to make is that when you consider specific examples by themselves it kinda doesn't quite make sense (I know you're probably thinking "woo-woo" about now, but that is one thing i'm not, and I would hope my posting history would attend to that).
I'm willing to concede that I might have over looked something, however...
If I randomly button mash the 6 digit number:
123456
Then convention would have you interpret that a specific way, and it's just a 6 digit number.
One of the things that I was trying to get to, and this is the point that RJBeery misinterpreted (mostly because I did a poor job of communicating it) is that I can add a rule.
Conventionally, this rule is "These digits are multiples of powers of ten, and are to be read sequentially to determine the final number, with the right most number being the multiple of 10 raised to the power of zero, and then increasing by one for each position to the left moved".
However, if I redefine the rule as: "These digits are multiples of Grahams number, to determine the specific number I am referring to calculate Grahams number, multiple it by the number I have stated, and then read it sequentially with the next number".
A compression algorithm, so to speak.
So, in otherwords, as a demonstration, if I were to mash:
1111
And then use 256 as my expansion number, then the number I have chosen becomes:
256256256256
Or, if I had mashed:
1234
It would become:
2565127681024
So, ultimately, there is no limits on what I can button mash (I could, for example, declare that my expansion is Grahams number in a Megagon) as long as we have some formalism in place that gives us a symbolism or language to describe how to derive the expansion.
RJBeery
01-28-09, 03:00 PM
Trippy, there is a fundamental problem with your last post and it has to do with compression algorithms. Compression can only take out useless (i.e. redundant) information. In order to represent 100 states (or integers) you need to have 100 unique representations, period. You might as well say that you could represent infinite numbers with a single digit by using a base of infinity - that would solve the "communication" problem we're discussing wouldn't it?
Also, I don't agree that "infinite rooms" would not include infinite length room numbers but let me move beyond the point anyway. Why does it matter? My point in regards to the OP was that this "paradox" arises because we are trying to apply the fantasy world of Mathematics to Reality and there is a distinction between the two. In Reality, infinity does not exist, it cannot be represented, and certainly cannot be chosen from randomly in a uniform distribution, PERIOD.
Trippy, there is a fundamental problem with your last post and it has to do with compression algorithms. Compression can only take out useless (i.e. redundant) information. In order to represent 100 states (or integers) you need to have 100 unique representations, period. You might as well say that you could represent infinite numbers with a single digit by using a base of infinity - that would solve the "communication" problem we're discussing wouldn't it?
No, because the argument against button mashing is the time taken to mash out a random arbitrarily large number, and my point is that generating a random arbitrarily large number by button mashing doesn't have to be difficult, or time consuming as long as the apporpriate rules and symbols are in place.
Another way of considering it is if I were to say "Each number represents a multiple of Grahams number raised to a power, starting with zero at the right most digit, and increasing as you move left, with each number to be added to the last."
Effectively this means where operating in 'Base-Grahams number" with the obvious drawback that we don't really have a Grahams number of symblols to represent all the posibilities.
There in lies the difference of what we're saying to some extent I suppose - you keep talking about representing 'all' symbols, where as I'm talking about representing enough of them.
The 'unrepresented' numbers still exist, and I could have chosen them just as easily by choosing a different set of symbols and rules.
Also, I don't agree that "infinite rooms" would not include infinite length room numbers but let me move beyond the point anyway. Why does it matter? My point in regards to the OP was that this "paradox" arises because we are trying to apply the fantasy world of Mathematics to Reality and there is a distinction between the two. In Reality, infinity does not exist, it cannot be represented, and certainly cannot be chosen from randomly in a uniform distribution, PERIOD.
But we don't have to represent or choose infinity, because infinity itself is not one of our choices. We only have to be able to represent something that is arbitrarily large, but still finite (so the probability becomes arbitraily small, but not zero hence P(X=x) = δ - or possibly more correctly P(X=x) = 0+δ).
quadraphonics
01-28-09, 03:34 PM
Trippy's method depends on the decay of a single atom. Then you can ignore the half life of the element, because any single radioactive atom decays at any moment between now and eternity, with an equal chance of decaying at any of those moments.
That doesn't actually solve your objection about requiring infinite time, however. The single-particle decay method doesn't always take infinite time to produce an output, but the expected time to get an output is still infinite. Hardware random number generators use large collections of decaying particles, which then obey an exponential law.
Likewise, RJBeery's point that no matter how complex a compression scheme you use, a finite alphabet of possible symbols still amounts to a finite set of possible numbers. In other words, if the set really is infinite, there will necessarily be some codewords of infinite length (if you use a variable-length code; otherwise ALL of the codewords are infinite). And if the probability of choosing an infinite-length codeword is positive (which it is held to be in the uniform distribution), then the expected length of the code is again infinite.
The only way you can get a finite expected code length for an infinite set is if the probabilities of elements in the set decays sufficiently quickly. It cannot be done in the (ill-posed) case of a uniform distribution. Which is to say that even if you could uniformly select from a countable set in a finite time, it would still take you forever (on average) to write down the outcome.
quadraphonics
01-28-09, 03:49 PM
No, because the argument against button mashing is the time taken to mash out a random arbitrarily large number
No, the objection is not about the size of the outcome per se, but about the size of the set of possible outcomes. If you only mash a finite number of symbols, then you have only selected from among a finite set of possible outcomes. If you mash buttons for some random, uniformly-distributed amount of time (until a single potassium nucleus decays, for example), then you are selecting from an infinite set, but the expected time you spend mashing buttons is infinite.
There in lies the difference of what we're saying to some extent I suppose - you keep talking about representing 'all' symbols, where as I'm talking about representing enough of them.
The 'unrepresented' numbers still exist, and I could have chosen them just as easily by choosing a different set of symbols and rules.
But you did not, and so the method you used is not selecting from an infinite pool. You could consider the choice of symbols and rules as part of the random number selection process, but that would leave you right where you started: having to select uniformly from an infinite possible universe of symbols and rules, in a finite time.
But we don't have to represent or choose infinity, because infinity itself is not one of our choices. We only have to be able to represent something that is arbitrarily large, but still finite (so the probability becomes arbitraily small, but not zero hence P(X=x) = δ - or possibly more correctly P(X=x) = 0+δ).
And the minimum expected code length for such a descriptrion is itself arbitrarily large. I.e., you will never finish typing out the representation, on average.
RJBeery
01-28-09, 03:57 PM
The 'unrepresented' numbers still exist, and I could have chosen them just as easily by choosing a different set of symbols and rules.
Ah! Then compression you're talking about is not relevant because you might be able to represent an arbitrarily large number "very quickly" with x^(x^(x^(x^(x^...)))) or some other algorithm but I could (as the Angel) hide in a room number that is so large you would be PRACTICALLY unable to represent, choose, or communicate such a number with your algorithm within a mortal's lifetime. Either time and practicality are a factor, or they are to be ignored. I believe there are two answers here:
1) Practically, the Angel/Devil question is irrelevent because it can only be carried out in the head. TRULY picking a uniformly random number from infinity is impossible; it's nonsensical like asking what the color of 7 is.
2) Theoretically, as an Angel and Devil, presuming they are capable of the supertask that we have established is impossible, then the answer is that the probability of the Devil catching the Angel is ZERO. It does not "approach zero", it is not "infinitely small", it is zero. If you try to counter this by saying something like "what if they both picked the first door?" then you are having conceptual problems with RANDOM and INFINITY. If we eliminate the RANDOM choosing of the door and claimed that both entities just "picked a door" then I believe the answer would be non-zero because the Angel might pick the heavenly number 7, or the beastly number 666, or the first door, or some other door based on a reason that the Devil may be able to deduce.
There! All questions have been answered and the entire debate has officially ended. haha :)
That doesn't actually solve your objection about requiring infinite time, however. The single-particle decay method doesn't always take infinite time to produce an output, but the expected time to get an output is still infinite. Hardware random number generators use large collections of decaying particles, which then obey an exponential law.
It doesn't have to be infinite, it only has to be finite, by definition, it just has to be undefined.
Likewise, RJBeery's point that no matter how complex a compression scheme you use, a finite alphabet of possible symbols still amounts to a finite set of possible numbers. In other words, if the set really is infinite, there will necessarily be some codewords of infinite length (if you use a variable-length code; otherwise ALL of the codewords are infinite). And if the probability of choosing an infinite-length codeword is positive (which it is held to be in the uniform distribution), then the expected length of the code is again infinite.
The only way you can get a finite expected code length for an infinite set is if the probabilities of elements in the set decays sufficiently quickly. It cannot be done in the (ill-posed) case of a uniform distribution. Which is to say that even if you could uniformly select from a countable set in a finite time, it would still take you forever (on average) to write down the outcome.
Go back and reread what I actually said, and bear in mind that what i'm talking about is an expansion, not a compression, and also bear in mind that the number i'm talking about, if I define the rule before hand, can be 'nested expansions'.
For example, I could say that my mashed number is '1234' and that "each of those numbers represents a multiple of Grahams number, and they are to be read sequentially, but each of the numbers from this expansion is also a multiple of grahams numbers, and this process is to be repeared a grahams number of times"
It's still a finite number, it is arbitrarily large, and selected at random, and is just as likely to have been selected as '1' "But let's apply the standard rules this time".
in essence, i'm not really talking about compression algorithms, I'm talking about the rules we use to expand the numbers to interpret their meaning - for example the rules we use to expand the number 123 and interpret it's meaning as 1*10^2+2*10^1+3*10^0
Ah! Then compression you're talking about is not relevant because you might be able to represent an arbitrarily large number "very quickly" with x^(x^(x^(x^(x^...)))) or some other algorithm but I could (as the Angel) hide in a room number that is so large you would be PRACTICALLY unable to represent, choose, or communicate such a number with your algorithm within a mortal's lifetime. Either time and practicality are a factor, or they are to be ignored. I believe there are two answers here:
1) Practically, the Angel/Devil question is irrelevent because it can only be carried out in the head. TRULY picking a uniformly random number from infinity is impossible; it's nonsensical like asking what the color of 7 is.
2) Theoretically, as an Angel and Devil, presuming they are capable of the supertask that we have established is impossible, then the answer is that the probability of the Devil catching the Angel is ZERO. It does not "approach zero", it is not "infinitely small", it is zero. If you try to counter this by saying something like "what if they both picked the first door?" then you are having conceptual problems with RANDOM and INFINITY. If we eliminate the RANDOM choosing of the door and claimed that both entities just "picked a door" then I believe the answer would be non-zero because the Angel might pick the heavenly number 7, or the beastly number 666, or the first door, or some other door based on a reason that the Devil may be able to deduce.
There! All questions have been answered and the entire debate has officially ended. haha :)
And you just proved my point when I mentioned the shortcomings of any specific set of rules, but, this is actually irrelevant, because all I have to do is specify a different set of rules when I state the number that is capable of handling the number of the room you're in.
And when did the life time of a mortal become relevant?
The other thing is you could combine rules.
Trippy's method depends on the decay of a single atom. Then you can ignore the half life of the element, because any single radioactive atom decays at any moment between now and eternity, with an equal chance of decaying at any of those moments.
Only if it hasn't already decayed. Think about it - the atom has a 50% chance of decaying within any given half-life.
RJBeery
01-28-09, 04:11 PM
Trippy, if time (such as a mortal's lifetime) isn't relevant then why are we discussing compression/expansion algorithms at all?? You brought them up as a resolution to the representation/communication issue. If we're assuming that the participant is immortal and capable of supertasks then they might as well represent and communicate arbitrarily large numbers by growing that many daisies in their infinite garden.:thumbsup:
RJBeery
01-28-09, 04:28 PM
Also, the half-life suggestion is NOT uniform. Try it 1,000,000 times and graph it. Is the number of decays at each time interval the same? No it is not; they are exponential by definition. The only way it would show a uniform distribution is if the element had a half-life of infinity, in which case the graph would in fact equal everywhere (but not very useful). :D
quadraphonics
01-28-09, 04:37 PM
It doesn't have to be infinite, it only has to be finite, by definition, it just has to be undefined.
Am I supposed to be more comfortable with waiting an "undefined" amount of time than an "infinite" amount of time?
Go back and reread what I actually said, and bear in mind that what i'm talking about is an expansion, not a compression, and also bear in mind that the number i'm talking about, if I define the rule before hand, can be 'nested expansions'.
"Expansion" is just the final step in a compression algorithm, where you decode the actual result. In order to perform an expansion, you have to have first defined a compression, or there isn't anything to expand. That you generate number directly in the compressed domain is irrelevant: the compressor is specified when you specify the expander (i.e., the "rules").
Said another way, your "rules" represent an invertible mapping between an alphabet of codewords and a set of symbols. The mapping from symbols to codewords is a "compression" and the inverse is "expansion." Taken together, they represent a coder, or "compression algorithm." But the key point is that specifying just ONE of the mappings specifies the entire thing, and you can then apply results from data compression to the situation.
For example, I could say that my mashed number is '1234' and that "each of those numbers represents a multiple of Grahams number, and they are to be read sequentially, but each of the numbers from this expansion is also a multiple of grahams numbers, and this process is to be repeared a grahams number of times"
It's still a finite number, it is arbitrarily large, and selected at random, and is just as likely to have been selected as '1' "But let's apply the standard rules this time".
Only if you are also randomly selecting over the rules, as well as numbers. How long will it take you to randomly select from the infinite set of possible rules?
in essence, i'm not really talking about compression algorithms, I'm talking about the rules we use to expand the numbers to interpret their meaning - for example the rules we use to expand the number 123 and interpret it's meaning as 1*10^2+2*10^1+3*10^0
That is exactly what the decoder side of a compression algorithm is, which is turn specifies the encoder side. I.e., you are designing a compression algorithm.
That doesn't actually solve your objection about requiring infinite time, however. The single-particle decay method doesn't always take infinite time to produce an output, but the expected time to get an output is still infinite.
I agree with Trippy that a single atom never takes infinite time (forever) to decay, just an indefinite time. Those are subtly different. An indefinite time would be the expected time too. It could be 5 minutes, or 5 billion years.
Likewise, RJBeery's point that no matter how complex a compression scheme you use, a finite alphabet of possible symbols still amounts to a finite set of possible numbers.
How could the set of natural numbers, which uses only symbols 0 to 9, have a finite number of numbers in it?
In other words, if the set really is infinite, there will necessarily be some codewords of infinite length (if you use a variable-length code; otherwise ALL of the codewords are infinite).
I've been discussing Nasor's #23 post, which morphed into "If I randomly pick a natural number, what are the odds that you will be able to guess my number on the first try?" What I read (Wikipedia) shows that the set of natural numbers contains only finite numbers, and contains an infinite number of numbers. Can you show otherwise?
The only way you can get a finite expected code length for an infinite set is if the probabilities of elements in the set decays sufficiently quickly. It cannot be done in the (ill-posed) case of a uniform distribution. Which is to say that even if you could uniformly select from a countable set in a finite time, it would still take you forever (on average) to write down the outcome.
I agree that if the set of natural numbers contains numbers of infinite length, one cannot randomly select from it.
RJBeery
01-28-09, 04:50 PM
Then we are in agreement that the answer to Nasor's #23 post is zero?
And you just proved my point when I mentioned the shortcomings of any specific set of rules, but, this is actually irrelevant, because all I have to do is specify a different set of rules when I state the number that is capable of handling the number of the room you're in.
Hi Trippy,
You're not following what I'm saying at all.
When you specify a set of rules, you must do so using some notation (eg English words). These specified rules, plus the data, form a complete set of characters that uniquely specify a number.
There is a finite number of sets of rules you can describe (within any finite time), just as there is a finite number of data sets you can describe (within any finite time), simply because there is a finite number of symbols you can select (within any finite time).
In algorithm terms, you could consider a universal turing machine, that accepts a description of a turing machine (a set of rules), followed by a string of data to operate on.
Talking about algorithms isn't "quibbling", it's cutting to the absolute heart of the problem. Any method (of finite precision) that you can describe can also be described as an algorithm.
And as I showed earlier, 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.
And when did the life time of a mortal become relevant?
When you maintained that you could select randomly from an uniform infinite distribution. You're mortal, right?
The other thing is you could combine rules.
Yes, you could get surprisingly high. But not infinitely.
RJBeery
01-28-09, 04:56 PM
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.
Well said, Pete. So we're all in agreement that the answer to Nasor's #23 post is zero, then?
It is my understanding that half-life is a property of many atoms, and that any specific atom has a constant probability of decaying at any moment (which is why the property of half life emerges in the first place).
A single atom has a 50% chance of decaying in any given half life. Think about it - start with 2 billion atoms, wait one half life. If each individual atom has a probability of 50% of decaying in that time, then about 50% should have decayed... which is what a half life is!
If an atom has a half life of 1 second, then it has a 50% chance in the first second, 50% chance of decaying in the second (if it survived the first), 50% chance of decaying in the third (if it survived the previous two) and so on. The probability that it decays in any given half-life is constant - but is contingent on it having survived up to that point.
Right.
And if I button-mash a 1 digit number, it has a 1 in 10 chance of being a 1, but if I button-mash a 6 digit number it has a 1 in a million chance of being 347692. But, it ALSO has a 1 in a million chance of being 000001 - exactly the same as the program i've described
The output of your program has about the same chance of being a one button mash as a six button mash. A one might come up as 000001 (the same chance as 347692), but a one has a better chance because it could also come up as 00001, 0001, 001, 01, or just 1.
No, Somebody does, but that somebody wasn't neccessarily specified as being me now was it? and before you tell me to stop being ridiculous, think about it for a minute, and think about why I might have described it as being a 'super task' to begin with.
So whoever does it needs unlimited precision?
I had considered angular resolution - for lack of a better way of describing it, and I was almost certain you would bring it up, but i'm not convinced of it's relevance, and if the number line happens to loop around in a very large circle, or a very long helix (well, I suppose I should say infinite in both cases) then it doesn't matter.
Consider in further, and you'll find it does matter. If you are surrounded by an infinity of numbers, then how closely packed must they be?
Only if it hasn't already decayed. Think about it - the atom has a 50% chance of decaying within any given half-life.
Well, whether or not the algorithm is selecting randomly depends on the odds of the atom decaying at any moment, so "Only if it hasn't already decayed" is all that matters, right? Once it decays the algorithm is finished.
Suppose the half-life of an element is 1 day. Does that mean that there is a greater chance that the single atom the algorithm is watching will decay in the first month, than in the second month? No, the odds of that atom decaying in any month is the same. The half-life tells only when to expect that 50% of a group of like atoms will have decayed.
Flip a coin every day. Heads is survive for another day, tails is decay. On any given day you have the same odds of decaying. But there will be a half-life statistic for a group of such coin flippers.
Well said, Pete. So we're all in agreement that the answer to Nasor's #23 post is zero, then?
I don't think so, because if Nasor randomly picks an integer, he's not randomly selecting from a uniform infinite distribution. There is a non-zero chance that he chooses 1736209878016208, for example.
Well, whether or not the algorithm is selecting randomly depends on the odds of the atom decaying at any moment, so "Only if it hasn't already decayed" is all that matters, right? Once it decays the algorithm is finished.
Suppose the half-life of an element is 1 day. Does that mean that there is a greater chance that the single atom the algorithm is watching will decay in the first month, than in the second month?
Yes!
The atom's chance of decaying in the first 30 days is 99.999999907%.
The atom's chance of decaying in the second month is also 99.999999907%... if it survives the first month.
Flip a coin every day. Heads is survive for another day, tails is decay. On any given day you have the same odds of decaying. But there will be a half-life statistic for a group of such coin flippers.
Start with a zillion atoms. In the first half life, about half decay, leaving half surviving.
Start with 1000 flippers. The first day, about half flip tails, leaving half surviving. That's a half-life.
The probability that it decays in any given half-life is constant - but is contingent on it having survived up to that point.
True. You can substitute "moment" for "half-life". And it guarantees that the algorithm will randomly select; it will pick a number out of an infinity of numbers, with every number having equal odds of being picked.
Look, don't take my word for it... look it up in a chemistry of physics text, or ask Wikipedia (http://en.wikipedia.org/wiki/Half-life):
Probabilistic nature of half-life
A half-life often describes the decay of discrete entities, such as radioactive atoms. In that case, it does not work to use the definition "half-life is the time required for exactly half of the entities to decay". For example, if there is just one radioactive atom with a half-life of 1 second, there will not be "half of an atom" left after 1 second. There will be either zero atoms left or one atom left, depending on whether or not the atom happens to decay.
Instead, the half-life is defined in terms of probability. It is the time when the expected value of the number of entities that have decayed is equal to half the original number. For example, one can start with a single radioactive atom, wait its half-life, and measure whether or not it decays in that period of time. Perhaps it will and perhaps it will not. But if this experiment is repeated again and again, it will be seen that it decays within the half life 50% of the time.
Start with a zillion atoms. In the first half life, about half decay, leaving half surviving.
Start with 1000 flippers. The first day, about half flip tails, leaving half surviving. That's a half-life.
(Quickly, 'cause I gotta leave) What's your point? The algorithm employs a single atom, not a group of them, and you seem to agree that the odds of a single atom decaying at any moment are constant.
True. You can substitute "moment" for "half-life". And it guarantees that the algorithm will randomly select; it will pick a number out of an infinity of numbers, with every number having equal odds of being picked.
No, subsequent moments are less likely to be picked, because they are contingent on the survival of previous moments. Look at post 109 (http://www.sciforums.com/showpost.php?p=2152309&postcount=109), and try working the maths. It takes a little effort, but it's not that difficult. All you need are your basic probability laws (http://www.omegamath.com/Data/d2.4.html).
RJBeery
01-28-09, 05:21 PM
As I said, the half-life issue is irrelevant because it is not UNIFORM distribution. It's exponential. It might help in choosing an number that was not predetermined, but it does not help in choosing a uniformly distributed random number from infinity.
Yes!
The atom's chance of decaying in the first 30 days is 99.999999907%.
The atom's chance of decaying in the second month is also 99.999999907%... if it survives the first month.
Oh, I thought "Yes!" was excitement. I'll reply later.
RJBeery
01-28-09, 05:22 PM
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?
(Quickly, 'cause I gotta leave) What's your point? The algorithm employs a single atom, not a group of them, and you seem to agree that the odds of a single atom decaying at any moment are constant.
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.
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?
No. I think the question is meaningless.
Trippy, if time (such as a mortal's lifetime) isn't relevant then why are we discussing compression/expansion algorithms at all?? You brought them up as a resolution to the representation/communication issue. If we're assuming that the participant is immortal and capable of supertasks then they might as well represent and communicate arbitrarily large numbers by growing that many daisies in their infinite garden.:thumbsup:
IN the situation you were describing it is irrelevant.
Or are you instead suggesting that Angels and Demons are mortal, and subject to mortal limitations?
Am I supposed to be more comfortable with waiting an "undefined" amount of time than an "infinite" amount of time?
Given the definition of Undefined, yes.
"Expansion" is just the final step in a compression algorithm, where you decode the actual result.
I'm aware of that.
In order to perform an expansion, you have to have first defined a compression, or there isn't anything to expand. That you generate number directly in the compressed domain is irrelevant: the compressor is specified when you specify the expander (i.e., the "rules").
Your missing the point. The point is the compression side is irrelevant.
Said another way, your "rules" represent an invertible mapping between an alphabet of codewords and a set of symbols.
Strictly speaking, yes.
The mapping from symbols to codewords is a "compression" and the inverse is "expansion."
Strictly speaking, yes.
Taken together, they represent a coder, or "compression algorithm."
Strictly speaking, yes.
But the key point is that specifying just ONE of the mappings specifies the entire thing, and you can then apply results from data compression to the situation.
Actually completely irrelevant.
You seem to be assuming that I know the number beforehand, and then compress it first so that I can communicate it, rather then generating the 'compressed' number and telling you how to expand it.
But it's not even really that, in that sense every number is 'compressed', i'm just using different rules to interprete their meaning.
Only if you are also randomly selecting over the rules, as well as numbers. How long will it take you to randomly select from the infinite set of possible rules?
I hate to be rude, but Duh.
I thought that was implicit in the discussion, or do I really need to go back and restate it explicitly.
As for how long it will take?
It will take as long as it takes me to decide or make them up.
That is exactly what the decoder side of a compression algorithm is, which is turn specifies the encoder side. I.e., you are designing a compression algorithm.
Whatever, the compression side is COMPLETELY IRRELEVANT.
Then we are in agreement that the answer to Nasor's #23 post is zero?
No.
quadraphonics
01-28-09, 05:50 PM
I agree with Trippy that a single atom never takes infinite time (forever) to decay, just an indefinite time. Those are subtly different. An indefinite time would be the expected time too. It could be 5 minutes, or 5 billion years.
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.
How could the set of natural numbers, which uses only symbols 0 to 9, have a finite number of numbers in it?
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.
What I read (Wikipedia) shows that the set of natural numbers contains only finite numbers, and contains an infinite number of numbers. Can you show otherwise?
Why would I want to show otherwise? Again, I think you have misread my post.
I agree that if the set of natural numbers contains numbers of infinite length, one cannot randomly select from it.
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!
Hi Trippy,
You're not following what I'm saying at all.
Yes, I am.
When you specify a set of rules, you must do so using some notation (eg English words). These specified rules, plus the data, form a complete set of characters that uniquely specify a number.
Correct.
There is a finite number of sets of rules you can describe (within any finite time), just as there is a finite number of data sets you can describe (within any finite time), simply because there is a finite number of symbols you can select (within any finite time).
No. Using the simplest rule "These numbers represent multiples of N" there are as many possible rules as there are natural numbers.
As far as rules that I can type in a finite period of time, they two are potentially unlimited.
My point is that there is no Finite member of the natural numbers that is sufficiently large that I can't describe it in a finite period of time with symbols of finite complexity.
I understand fully what you're saying, however I disagree with it because of the above statement.
Any number I select from teh pool of natural numbers must be a finite number.
Therefore with a finite pool of symbols, with rules of finite complexity it can be described in a finite period of time. Shortening the finite period of time only requires that I increase the complexity of the rules.
This is the point that seems to have been missed widely, is that although there are in infinite number of natural numbers, there are no natural numbers of infinite length, therefore all I need in order to communicate any (finite) natural number in a finite period of time, I simply need rules and symbols that are sufficiently complex.
In algorithm terms, you could consider a universal turing machine, that accepts a description of a turing machine (a set of rules), followed by a string of data to operate on.
Talking about algorithms isn't "quibbling", it's cutting to the absolute heart of the problem. Any method (of finite precision) that you can describe can also be described as an algorithm.
And as I showed earlier, 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.
When you maintained that you could select randomly from an uniform infinite distribution. You're mortal, right?
Apparently you need to go back and re-read the specific post that I was referring to and understand why I said that.
I'll give you a clue - how is the lifetime of a mortal relevant to an angel or a demon?
Where in the OP does it state that there is a mortal spectator?
quadraphonics
01-28-09, 06:09 PM
Given the definition of Undefined, yes.
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 :]
You seem to be assuming that I know the number beforehand, and then compress it first so that I can communicate it, rather then generating the 'compressed' number and telling you how to expand it.
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.
I hate to be rude,
Then don't be.
I thought that was implicit in the discussion, or do I really need to go back and restate it explicitly.
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).
As for how long it will take?
It will take as long as it takes me to decide or make them up.
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?
quadraphonics
01-28-09, 06:14 PM
My point is that there is no Finite member of the natural numbers that is sufficiently large that I can't describe it in a finite period of time with symbols of finite complexity.
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.
And as I showed earlier, 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.
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?
RJBeery
01-28-09, 06:16 PM
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!
Apparently you need to go back and re-read the specific post that I was referring to and understand why I said that.
I'll give you a clue - how is the lifetime of a mortal relevant to an angel or a demon?
Where in the OP does it state that there is a mortal spectator?
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!
Get over yourself. I'm rapidly running out of civility, that's twice you've been rude.
I've already explained my comments in this regard. If you think i've misunderstood something that you've said? Then say so.
RJBeery
01-28-09, 07:45 PM
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. :(
I'm only going to say this once, because i've got too many people yapping at me about the same things, which I thought I had made abundantly clear.
The fact that I'm selecting from an infinite pool is largely irrelevant.
Any number I choose, no matter how large, is still a finite number, it just happens to be arbitrarily large.
Any finite number can be represented by the appropriate symbolism, and the appropriate rules.
I don't have to use a infinitely complex set of rules and symbols, I only have to use one that is arbitrarily complex, or, in other words, sufficiently complex.
The crux of the matter is this:
Any finite number can be represented, and therefore chosen
We're already well beyond the realm of numbers that can be written in their 'expanded' forms in a human life time.
The ONLY thing(s) that I am assuming is that if I select an arbitrarily large number from an infinite pool, then because that number is finite, I can represent it in a finite time with the appropriate rules and symbols.
The proof of this is obvious.
As an example - Grahams number.
G=f^{64}(3) where f(n)=3\uparrow^n 3
There we go. In a human lifetime, substantially less than even, using appropriate symbols and notation I have written a number that is substantially greater than the number of planck volumes in the visible universe.
quadraphonics
01-28-09, 08:12 PM
The crux of the matter is this:
Any finite number can be represented, and therefore chosen
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:
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.
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.
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.
I call bait and switch (a logical fallacy).
It is precisely the argument that is being put forward that I can not choose from an infinite pool because I can not represent an arbitraily large number in a finite period of time.
Were it otherwise, mortal lifespan would be irrelevant to the argument.
I have been saying right from the start that unchosen numbers are irrelevant, because I do not need to represent them.
I have been saying right from the start that I can represent any finite arbitrarily large number with finite symbols in a finite time and using finitely complex rules.
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.
I said no such thing, that was Pete's post thankyou.
http://www.sciforums.com/showpost.php?p=2152147&postcount=97
Pete:
Here's the substantial difference between the coin flip model and the Potassium decay thing.
The coin flip model is statistically biased - it will (for example) always produce a sequence that ends with a "Head" - hence it being a binomial distribution.
The K-40 model is not statistically biased. You can not predict what the final digit will be, because this is not controlled by the K-40 atom.
quadraphonics
01-28-09, 09:41 PM
It is precisely the argument that is being put forward that I can not choose from an infinite pool because I can not represent an arbitraily large number in a finite period of time.
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).
I have been saying right from the start that unchosen numbers are irrelevant, because I do not need to represent them.
You need to be able to represent them, otherwise how can you claim to have selected from amongst them in the first place?
I have been saying right from the start that I can represent any finite arbitrarily large number with finite symbols in a finite time and using finitely complex rules.
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 said no such thing, that was Pete's post thankyou.
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...
No, you're making the same error. The argument is that you cannot choose 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 don't have to neccessarily represent every possible outcome, but it does need to be possible to represent them if they are chosen - subtle distinction.
You need to be able to represent them, otherwise how can you claim to have selected from amongst them in the first place?
This is precisely my point, being able to represent them, and actually representing them are two different things. You've hit the nail on the head - it is requisite that it is possible to represent them, if they are selected, not that they neccessarily be represented at the time of the selection
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.
Thiis irrelevant.
I'm still only selecting a finite number.
I still only need to represent that number.
The fact that my chosen set of symbols and rules is only capable of representing a range of numbers before they become cumbersome is wholly irrelevant. I using (for example) powers of Googol instead of powers of ten, I have two options for picking the number 2.
Either:
1^0 + 1^0
Where '1' and '0' are multiples of Googol, or multiples of powers of googol.
Or, I can right.
googol^n
Where n is some number that gives 2 as the nth root of googol.
And that is okay, 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 of the symbol associated with the outcome of a random selection is also infinite.
So you're seriously suggesting that you've solved the problem:
x= (1/∞) * ∞
I don't suppose you'd care to share that proof with us?
To put it another way: for any finite set of symbols/rules/time you specify, there will still be infinitely many natural numbers that you cannot assign symbols to. Which is to say that the probability of (uniformly) picking a number that you can build a symbol for is equal to zero, no matter how much (finite) time/complexity you are willing to throw at the problem!
No. There is no such thing as an infinitely complex, or long natural number.
Unless you happen to know what the largest natural number is, would you care to share that with us?
I suspected as much, but you should realize that you posted it, without quotes, a few posts back, hence the confusion.
So what you're really saying is that when I inadvertantly made an out of place comment that completely contradicted everything i've said up until this point as part of a reply to another user, you didn't stop to check to see if that user had made it?
Anyway, the results about stopping times are highly pertinent: they constitute proof that you cannot select from an infinite uniform distribution in finite time.
No they aren't and no they don't.
The only requirement is that they have the capacity to be arbitrarily large, which what i've discussed does.
I'll try and get back to some of the posts that i've skipped today at some time in the near future.
Besides which, if I accept the objection that is being offered, at some point you still have to select a finite range of numbers from an infinite range of possible ranges.
It also seems to me that there's an infinite number of ways of selecting any given number after all, button mashing 00000001 is a different selection from button mashing 00000000000000000001, even though both symbols represent the same number.
Yes, I am.
No. Using the simplest rule "These numbers represent multiples of N" there are as many possible rules as there are natural numbers.
As far as rules that I can type in a finite period of time, they two are potentially unlimited.
My point is that there is no Finite member of the natural numbers that is sufficiently large that I can't describe it in a finite period of time with symbols of finite complexity.
I understand fully what you're saying, however I disagree with it because of the above statement.
Yes, the statement is true. No, it does not contradict my argument.
Parts of my argument may be poorly summarised, for example the statement to which you responded should read:
There is a finite number of sets of rules you can describe (within any given finite time), just as there is a finite number of data sets you can describe (within any given finite time), simply because there is a finite number of symbols you can select (within any given finite time).
And an earlier statement should read:
An algorithm that chooses from an infinite uniform distribution has zero probability of halting in any given finite time.
But this one is rock solid:
If an algorithm selects a random number from an infinite distribution in finite time, then the distribution is not uniform.
You have not attempted to address the formalism I posted to derive those statements, nor have you attempted to refute the premises used.
This is the point that seems to have been missed widely, is that although there are in infinite number of natural numbers, there are no natural numbers of infinite length, therefore all I need in order to communicate any (finite) natural number in a finite period of time, I simply need rules and symbols that are sufficiently complex.
Actually, all you need to communicate any (finite) natural number in a finite period of time is binary.
Or perhaps you made the same mistake as I, and meant to say "any given finite period of time"?
Apparently you need to go back and re-read the specific post that I was referring to and understand why I said that.
Well, in post 60 (http://www.sciforums.com/showpost.php?p=2151095&postcount=60) it seemed quite clear that you maintained that you personally chose numbers randomly from a uniform distribution of the naturals by mashing your keyboard, an impression backed up by later posts.
But, I'll happily concede that you were really trying to make a point about supertasks, if that's what you want.
Pete:
Here's the substantial difference between the coin flip model and the Potassium decay thing.
The coin flip model is statistically biased - it will (for example) always produce a sequence that ends with a "Head" - hence it being a binomial distribution.
The K-40 model is not statistically biased. You can not predict what the final digit will be, because this is not controlled by the K-40 atom.
What are you talking about?
The number chosen by the coin flip model is the number of coin flips before a head comes up. Eg 1 if the first flip is a head, 2 if theres a tail followed byu a head, 12897426798 if there are 12897426797 tails followed by a head, and so on.
You can't predict what the last digit will be.
Yes, it's statistically biased toward lower numbers. So is the potassium decay model.
Do you understand the the distribution of the potassium decay model is not uniform?
Besides which, if I accept the objection that is being offered, at some point you still have to select a finite range of numbers from an infinite range of possible ranges.
It also seems to me that there's an infinite number of ways of selecting any given number after all, button mashing 00000001 is a different selection from button mashing 00000000000000000001, even though both symbols represent the same number.
Sure, given infinite time, speed, or symbol availability.
RJBeery
01-28-09, 10:51 PM
If an algorithm selects a random number from an infinite distribution in finite time, then the distribution is not uniform.
This sums up the entire thread IMHO. Pete, quick question: if the supertask of selecting a uniform random number from an infinite list were possible for the Angel and the Devil, what do you interpret the chance to be of the Devil finding the Angel?
quadraphonics
01-28-09, 11:16 PM
You don't have to neccessarily represent every possible outcome, but it does need to be possible to represent them if they are chosen - subtle distinction.
Subtle to the point of meaninglessness, if the distribution is uniform. In that case, you will encounter outcomes that require infinite time/complexity with probability 1.
This is precisely my point, being able to represent them, and actually representing them are two different things.
Different, yes, but the former has implications on the latter. The ability to represent a uniform draw from an infinite set implies that the resulting representations have infinite length/complexity with probability 1. Ergo, any representation with finite length/complexity cannot represent a uniform draw from an infinite set.
You've hit the nail on the head - it is requisite that it is possible to represent them, if they are selected, not that they neccessarily be represented at the time of the selection
Indeed, and if the probability of encountering long symbols decreases sufficiently quickly with the length, you can still get away with a finite expected length/complexity.
But if the distribution is uniform, the probability that the length/complexity of the result is less than any finite number is zero. I.e., it is almost surely equal to infinity.
Thiis irrelevant.
I'm still only selecting a finite number.
I still only need to represent that number.
You still need to be able to represent infinitely many numbers. And if those numbers are uniformly distributed, that means almost all of the symbols must have infinite length.
The fact that my chosen set of symbols and rules is only capable of representing a range of numbers before they become cumbersome is wholly irrelevant.
The problem is that no matter how much cumbersomnity (?) we are willing to endure, there are still infinitely many natural numbers you cannot represent. Thus, the probability of a uniform draw of natural numbers producing one you that exceeds ANY finite length/complexity is one.
So you're seriously suggesting that you've solved the problem:
x= (1/∞) * ∞
I don't suppose you'd care to share that proof with us?
No; what on Earth are you talking about? This is just a simple application of
-\sum_{n=1}^\infty p_n \log p_n
where p_n is a probability mass function on the natural numbers.
No. There is no such thing as an infinitely complex, or long natural number.
What is important is that there are infinitely many natural numbers.
Unless you happen to know what the largest natural number is, would you care to share that with us?
That there is no largest natural number is exactly what implies that no matter how much time/complexity you can spend, there are always infinitely many natural numbers that you cannot represent.
So what you're really saying is that when I inadvertantly made an out of place comment that completely contradicted everything i've said up until this point as part of a reply to another user, you didn't stop to check to see if that user had made it?
I can't be bothered to follow every interaction you have with every poster in a thread. And didn't I already correct this error for you anyway?
No they aren't and no they don't.
A compelling rebuttal, if ever I've read one :]
The only requirement is that they have the capacity to be arbitrarily large, which what i've discussed does.
If "what you've discussed" has the capacity to be arbitrarily large, then it follows that, should you feed it with a uniform pick over the natural numbers, it will, with probability 1, produce an output that is longer than any finite length. If you actually observe a finite-length output, then you have not drawn uniformly from the set of natural numbers.
quadraphonics
01-28-09, 11:20 PM
And an earlier statement should read:
An algorithm that chooses from an infinite uniform distribution has zero probability of halting in any given finite time.
The "any" in that statement actually makes it pretty strong. I.e., you could just as well say:
An algorithm that chooses from an infinite uniform distribution will, with probability one, never halt.
quadraphonics
01-28-09, 11:38 PM
Besides which, if I accept the objection that is being offered, at some point you still have to select a finite range of numbers from an infinite range of possible ranges.
??? That's the exact same problem as selecting a single number uniformly from the naturals, isn't it???
It also seems to me that there's an infinite number of ways of selecting any given number after all, button mashing 00000001 is a different selection from button mashing 00000000000000000001, even though both symbols represent the same number.
They need not represent the same number, however. You could easily come up with a decoding rule that would map those two outcomes to distinct natural numbers. But you'd still have the problem that any finite sequence of button mashes, no matter how large, would still leave an infinite set of natural numbers unaccounted for.
No matter how much time/complexity you are willing to employ, you never reach a point where the proportion of outcomes you can handle increases. It is always equal to 0, for any finite time/complexity.
The information theoretic explanation I've given does not depend on the details of how you represent the numbers, only the basic requirement that you can represent all of them, and that they are uniformly distributed over an infinite set. This is enough to conclude that the symbol representing the outcome will be infinite in length with probability 1.
Pete:
I'm short of time just at the moment.
On the K-40 thing.
I've made it clear in multiple posts that I thought you were referring to a binomial distribution with the coin flip thing. Apparently either I misunderstood what was being said, or it was inadequitly desceibed, because apparently what you were describing wasn't the set up I thought you were describing.
Likewise, you seem to have misunderstood me (i've been posting from work, I'm sure you can understand the time contraints, so it may actually be my fault).
IF the K-40 model generates a 6 digit number (or a 49 one) then 999999 is as likely as 000001.
At no point have I explicitly stated that it is uniform with respect to time - in fact it occurs to me that I haven't commented on this aspect of it.
There is a profound difference between what you're suggesting with the coin flip model, and what i'm suggesting with the K-40 model.
If we grant that in any half life period, that any atom has a 50% chance of decaying, then what I'm talking about isn't simply counting coin flips.
It's rolling nD10 while flipping a coin.
In your model, when the head comes up determines the number.
In my model, when the head comes up determines the number of digits in the number.
This, I think is where we may have mis communicated, and this is where the rules become very important (hence the miscommunication - I was in too much of a hurry to realize that I'd left off a bunch of zero's which make a substantial difference, this is where semantics becomes very important.
The probability if we accept that the probability of a specific atom decaying in a half life is 50%, and we have a program that generates 1 digit each half life, then the probability of generating a six digit number is: \frac{1}{2^6} however, because we are using 10 symbols, then P(x=000001) = P(x=999999) = \frac{1}{10^6} However, this is different from the probability of generating a result that will be read as 1 after 6 half lives is:
P(x=1) + P(x=01) + P(x=001) + P(x=0001) + P(x=00001) + P(x=000001)
Which is to say:
\frac{1}{10}.\frac{1}{2} + \frac{1}{10^2}.\frac{1}{2^2} + \frac{1}{10^3}.\frac{1}{2^3} + \frac{1}{10^4}.\frac{1}{2^4} + \frac{1}{10^5}.\frac{1}{2^5} + \frac{1}{10^6}.\frac{1}{2^6}
Or about .053
So, in essence, we have three probababilities.
If we wait for 6 halflives and check the result, the chances that it will be read as '1' is about .053 (but if we wait 6 half lives and check the result, the chances of it being read as 1000000 are only 0.0000000156 hence your insistance that it wasn't uniform)
The chances that it will specifically be 000001 are 0.0000000156, but the chances of it being any other 6 digit number is also 0.0000000156 (hence my insistence that your assertion was in error).
And if after 6 halflives, we consider only those results that are six digits long (if that makes sense) then the probability of it being read as a '1' is .000001, the same as 999999
In essence, I was thinking of "Only those results that were N-digits long after N half lives" where you were considering "all results of any length after N half lives".
If any of that makes sense?
Sure, given infinite time, speed, or symbol availability.
I still disagree with this point.
I still maintain that in order to describe a finite number in a finite time, we only need finite symbols and finitely complex rules.
Subtle to the point of meaninglessness, if the distribution is uniform. In that case, you will encounter outcomes that require infinite time/complexity with probability 1.
No. Not subtle to the point of meaningless, and i'm just about done trying to explain it.
Different, yes, but the former has implications on the latter. The ability to represent a uniform draw from an infinite set implies that the resulting representations have infinite length/complexity with probability 1. Ergo, any representation with finite length/complexity cannot represent a uniform draw from an infinite set.
NO!!!
The rules and symbols I use only need to have a certain complexity.
If I have chosen a specific number then I have also chosen to disregard every other number. I do not need to represent the numbers that I have disregarded, because they are wholly irrelevant - the ONLY thing that is important is that the combination of symbols and rules I have used is capable of representing 1, and that I have a combination of symbols and rules that can represent 1 just as easily as the number I am choosing.
As long as those conditions are met, I can say that the distribution is even.
But if the distribution is uniform, the probability that the length/complexity of the result is less than any finite number is zero. I.e., it is almost surely equal to infinity.
No, because as long as the number is finite, I only need rules of finite complexity and finitely many symbols to describe it in a finite time.
You still need to be able to represent infinitely many numbers. And if those numbers are uniformly distributed, that means almost all of the symbols must have infinite length.
You're still assuming that i'm tending to represent all numbers with the same rules and the same symbols - haven't I made it clear already that I'm talking about changing the complexity of the rules?
The problem is that no matter how much cumbersomnity (?) we are willing to endure, there are still infinitely many natural numbers you cannot represent. Thus, the probability of a uniform draw of natural numbers producing one you that exceeds ANY finite length/complexity is one.
This is only relevant if you're assuming i'm talking about representing all numbers with teh same rules and the same symbols.
No; what on Earth are you talking about?
Expected value.
What is important is that there are infinitely many natural numbers.
A point which I have acknowledged how many times now?
The equally important point is that any natural number I can select IS STILL FINITE.
That there is no largest natural number is exactly what implies that no matter how much time/complexity you can spend, there are always infinitely many natural numbers that you cannot represent.
I don't need to be able to represent them all at the same time, I only need to have the potential to represent them at some time. A simple point which you seem to have failed to grasp.
And once again. EVERY SINGLE ONE OF THEM IS FINITE, and can therefore be represented by a FINITE set of Symbols usingly FINITELY complex rules in a FINITE amount of time (and if it can be represented, it can be chosen).
I can't be bothered to follow every interaction you have with every poster in a thread. And didn't I already correct this error for you anyway?
And that's my problem how again?
A compelling rebuttal, if ever I've read one :]
You? Flame? Never.
If "what you've discussed" has the capacity to be arbitrarily large, then it follows that, should you feed it with a uniform pick over the natural numbers, it will, with probability 1, produce an output that is longer than any finite length. If you actually observe a finite-length output, then you have not drawn uniformly from the set of natural numbers.
This, quite literally makes no sense, and harkens back to what Zanket was insisting, and is quite frankly wrong.
The ONLY thing observing a finite length output proves is that the number I have chosen is a finite member of the natural numbers, which is a tautology, because every member of the set of natural numbers is itself finite in length.
There are no infinite length natural numbers.
??? That's the exact same problem as selecting a single number uniformly from the naturals, isn't it???
Which would be precisely my point. By that logic, I could never select any number, period. 2. But I just did. 8 I just did it again.
They need not represent the same number, however. You could easily come up with a decoding rule that would map those two outcomes to distinct natural numbers. But you'd still have the problem that any finite sequence of button mashes, no matter how large, would still leave an infinite set of natural numbers unaccounted for.
I don't need to account for numbers that I have already decided not to choose.
No matter how much time/complexity you are willing to employ, you never reach a point where the proportion of outcomes you can handle increases. It is always equal to 0, for any finite time/complexity.
Wholly irrelevant. Once again, you're assuming I need to expand all numbers with the same ease with the same rules. I don't. The way I see it there are only two requirements.
I need to have different rules of equivalent ease for different numbers (saying, for example 'these numbers represent multiples of powers of Grahams number is equivalent to saying 'these numbers represent multiples of powers of ten - the increased complexity is in the expansion from multiples of powers of grahams number to multiples of powers of 10).
I need to be able to represent the same number in every set of rules, irrespective of complexity.
Are you beginning to understand yet teh concept i've been trying to communicate?
I suppose the simplest way to describe it could be "A set of scale dependent rules".
Sure, you can argue that then I have infinitely many rules , and you'd probably be right, and that because I can't communicate all of them, that my scheme is bunk, but in that I'd argue you're wrong. I only need to be able to communicate the relevant rule, and how it relates back to numbers that we 'understand'.
For example:
The rule "Multiples of G\uparrow \uparrow G" isn't nessarilly anymore complicated than writing "Multiples of 10,000" but the increased complexity comes in trying to convert the number '1' in the first rule into some number using the standard rules.
(note here G=Grahams Number).
(Note - to put this in perspective writing 3\uparrow \uparrow4 requires about a terrabyte of storage space).
On the K-40 thing.
I've made it clear in multiple posts that I thought you were referring to a binomial distribution with the coin flip thing. Apparently either I misunderstood what was being said, or it was inadequitly desceibed, because apparently what you were describing wasn't the set up I thought you were describing.
You described it as a binomial distribution twice (post 95 (http://www.sciforums.com/showpost.php?p=2152129&postcount=95), post 157 (http://www.sciforums.com/showpost.php?p=2153220&postcount=157)). The first time I ignored, because in the same post you described another model that also selected from an infinite non-uniform distribution, which is the key property of the coin flip model anyway. The second time I responded to in my last post.
The original description was "...just flip a coin, and count the number of flips it takes until heads comes up," which seems pretty clear to me. But anyway, we both understand it now, so let's move on.
Likewise, you seem to have misunderstood me (i've been posting from work, I'm sure you can understand the time contraints, so it may actually be my fault).
IF the K-40 model generates a 6 digit number (or a 49 one) then 999999 is as likely as 000001.
At no point have I explicitly stated that it is uniform with respect to time - in fact it occurs to me that I haven't commented on this aspect of it.
The point I was making about the decay model was that it does not produce a uniform distribution. That's the obvious thrust of my initial response (http://www.sciforums.com/showpost.php?p=2151886&postcount=79), and I explicitily asked (http://www.sciforums.com/showpost.php?p=2152033&postcount=90) three (http://www.sciforums.com/showpost.php?p=2152033&postcount=90) times (http://www.sciforums.com/showpost.php?p=2152163&postcount=98) for clarification in subsequent posts.
You responded:
Does the potassium decay model choose from a uniform distribution, or is it more likely to some numbers than others?
The potassium decay model chooses from a uniform distribution.
It's just as likely to produce 1 as it is 8765237658476592465347652947568023478029182074367
There was no confusion on that point, at least.
There is a profound difference between what you're suggesting with the coin flip model, and what i'm suggesting with the K-40 model.
If we grant that in any half life period, that any atom has a 50% chance of decaying, then what I'm talking about isn't simply counting coin flips.
It's rolling nD10 while flipping a coin.
In your model, when the head comes up determines the number.
In my model, when the head comes up determines the number of digits in the number.
Yes, I understand your model, and there are certainly differences between it and the coin model.
But the key similarity, and the point of interest for this discussion, is that both choose from non-uniform distributions. More specifically, the probability of a specific number being chosen begins at a non-zero value for 1, and decreases asymptotically to zero for larger and larger numbers.
And if after 6 halflives, we consider only those results that are six digits long (if that makes sense) then the probability of it being read as a '1' is .000001, the same as 999999
According to your description of the model, if the atom decays after 6 loops of the software, then you will of course consider only the six-digit results. But that's the whole point of having the atom - it tells you how many digits to consider. So in analysis, we need to consider the probability of how many digits will be specified.
In essence, I was thinking of "Only those results that were N-digits long after N half lives" where you were considering "all results of any length after N half lives".
I was considering what the described model actually produces, which is "Only those results that are as many digits long as specified by the decay of the potassium atom."
I suppose the simplest way to describe it could be "A set of scale dependent rules". ...
Trippy, you are stuck in algorithm land. Yes,you can get to incredibly, unimaginably large integers, but there is still an upper bound for the possibilities available in any given finite time, as I conclusively demonstrated in post 97 (http://www.sciforums.com/showpost.php?p=2152147&postcount=97).
The point I was making about the decay model was that it does not produce a uniform distribution. That's the obvious thrust of my initial response (http://www.sciforums.com/showpost.php?p=2151886&postcount=79), and I explicitily asked (http://www.sciforums.com/showpost.php?p=2152033&postcount=90) three (http://www.sciforums.com/showpost.php?p=2152033&postcount=90) times (http://www.sciforums.com/showpost.php?p=2152163&postcount=98) for clarification in subsequent posts.
You responded:
There was no confusion on that point, at least.
Right, and this is the point that I was just making, was that instead of saying:
"The potassium decay model chooses from a uniform distribution.
It's just as likely to produce 1 as it is 8765237658476592465347652947568023478029182074367 "
What I should have said is:
"The potassium decay model chooses from a uniform distribution.
It's just as likely to produce 0000000000000000000000000000000000000000000000001 as it is 8765237658476592465347652947568023478029182074367"
Or something to that effect - in otherwords, if we consider the distribution of those K-40 generators still operating after 49 halflives (or however many numbers there are there) then the probability with which any 49 digit combination will come up is uniform.
Yes, I understand your model, and there are certainly differences between it and the coin model.
But the key similarity, and the point of interest for this discussion, is that both choose from non-uniform distributions. More specifically, the probability of a specific number being chosen begins at a non-zero value for 1, and decreases asymptotically to zero for larger and larger numbers.
Right, but bear in mind that this is true for any n-digit number.
The probability of selecting at random any n-digit number is \frac{1}{10^n}.
The probability of my 'machine' selecting any n-digit number after n half lives is \frac{1}{2^n}.\frac{1}{10^n}
According to your description of the model, if the atom decays after 6 loops of the software, then you will of course consider only the six-digit results. But that's the whole point of having the atom - it tells you how many digits to consider. So in analysis, we need to consider the probability of how many digits will be specified.
Right. And if the atom decays after three half lives, we only compare it to three digit numbers, and if the atom decays after n hlaf lives, we only compare it to other n-digit numbers (and we find the distribution to be uniform over those results).
I was only using the scenario of 'choosing' how many half lives the atom decays after as a tool to demonstrate where the uniform distribution was.
As I've said/agreed.
The machine has a \frac{1}{2^n} probability of producing an n digit number, but each n digit number has an equal \frac{1}{10^n} chance of occuring - whether it be a '1' with n-1 zeros in front of it, or 9 repeated n times.
I was considering what the described model actually produces, which is "Only those results that are as many digits long as specified by the decay of the potassium atom."
Then we may have had a miscommunication about that fact.
Trippy, you are stuck in algorithm land. Yes,you can get to incredibly, unimaginably large integers, but there is still an upper bound for the possibilities available in any given finite time, as I conclusively demonstrated in post 97 (http://www.sciforums.com/showpost.php?p=2152147&postcount=97).
We may simply have to agree to disagree on this point.
I understood your post, and agree that yes, for the scenario outlined, it is valid, however, I still consider that any arbitraily large finite number can be described in a finite time, as long as some rule exists that allows an expansion.
Actually being able to perform the expansion is something that I will concede may not be possible in any reasonable finite time, whoever I consider that to be wholly irrelevant, as long as I suppose (and I really hope i'm using this in the right context) some describable mapping function exists (for example, I am perfectly willing to accept that although Grahams number is finite, and I can describe it, I can not write it as a power stack, and I can not write it in it's expanded form, but ultimately, my point is, with sufficiently 'complex' rules - namely knupfs up arrow notation, it can be described.
(and on that note, I should step AFK until tomorrow).
RJBeery
01-29-09, 10:31 AM
Trippy, Pete: I've been thinking about the K-40 issue which I thought was dead and plainly wrong (at least in the way that I interpreted Trippy's proposal). However, what if you took an infinite number of K-40 atoms, each separated and representing a binary digit of the infinite number to be selected. Then you wait exactly the expected half-life of the atoms (1.3 billion years). If an atom has decayed it represents a one, otherwise it represents a zero.
Now you have a UNIFORMLY random number generated from the infinite naturals in a FINITE TIME. Granted there are still issues regarding "reading" the number (or practically setting up the experiment) but those points are moot when talking about supertasks being possible.
Now you have a UNIFORMLY random number generated from the infinite naturals in a FINITE TIME. Granted there are still issues regarding "reading" the number (or practically setting up the experiment) but those points are moot when talking about supertasks being possible.
Wait, are you now agreeing with Trippy? I'm so confused! If you could do a supertask would you even need the atoms?
I have to say, kudos to Nasor, this is one of the more interesting threads I've seen on sciforums.
Pete, you make too much sense; I'm switching sides again. I agree, an atom can decay at an unpredictable moment, but still have high odds of decaying within the next second, in the case of an element with a half-life of a nanosecond, for example. That won't work for randomly selecting from an infinite set. You'd need an atom that decays unpredictably and has no half-life, which doesn't exist.
BenTheMan
01-29-09, 01:22 PM
It seems to me a lot of the confusion is over semantics, which is hardly new. Just look under "Platonic existence" on wikipedia or something. I have been bad and haven't been following this debate (because, frankly, I thought it was solved (http://www.sciforums.com/showpost.php?p=2145575&postcount=3) on the first page), but let me interject a word here. If it is terribly out of context you all can shout at me.
When dealing with concepts such as "ideal" or "perfect" or "infinity", you are a priori talking about something that cannot be physically realized. For example, if you took all of the energy in the universe and converted it into RAM (for the sake of argument), and used it to make a number, that number would still be smaller than infinity. This means that infinity doesn't exist in the real world. Just like a "perfect" sphere, or an "ideal" gas---various levels of approximation let us do calculations, sure, but that's not what "perfect" or "ideal" means.
So, if I'm a mathematician, I say "Obviously the probability of picking something from an infinite number of choices is 0". If I'm a physicist, I say "The probability tends to zero as I have more choices." The two are not inconsistent, but are approached from different angles.
quadraphonics
01-29-09, 01:27 PM
If I have chosen a specific number then I have also chosen to disregard every other number. I do not need to represent the numbers that I have disregarded, because they are wholly irrelevant - the ONLY thing that is important is that the combination of symbols and rules I have used is capable of representing 1, and that I have a combination of symbols and rules that can represent 1 just as easily as the number I am choosing.
[...]
You're still assuming that i'm tending to represent all numbers with the same rules and the same symbols - haven't I made it clear already that I'm talking about changing the complexity of the rules?
This is only relevant if you're assuming i'm talking about representing all numbers with teh same rules and the same symbols.
Yes, you must use one fixed set of rules for every possible outcome. Otherwise, if you want to design a custom set of rules after selecting a number, you'll have to ALSO communicate the rules and symbols in order to communicate the number.
And that is circular: the complexity of communicating a system of symbols capable of representing any particular natural number is exactly the same as the complexity of communicating any particular natural number in the first place. I.e., your system that converts "1" into an arbitrary number: it consists of the single rule "map one to the natural number n."
So I suggest you drop the whole line of thinking.
Expected value.
Yes, as you can see, the entropy (minimum expected message length) is finite for well-defined (i.e., non-uniform) distributions on the naturals, but diverges if you try to put in a uniform distribution.
There are no infinite length natural numbers.
On the contrary, they ALL have infinite length. We just express them in a certain shorthand, because they all eventually end up with an endless string of zeros.
I.e., to express a given natural number takes countably many digits. When you refer to the number "8," you're using a shorthand for the number "...00008", where the left-hand zeros go on for ever. So, to truly generate a uniform random natural number, you need to roll a countable number of 10-sided dice, one for each digit.
Your idea for exploiting the finiteness of natural numbers consists of noting that any finite natural number will eventually have an endless string of zeros on the left, which you can denote via a special symbol (a blank space, usually), followed by some finite string of digits. So, you propose that you can generate such a number in finite time because there are only finitely many non-trivial digits. The problem with this is that you're skipping a step: to generate a random number in this way, you first have to randomly select how many nontrivial digits it's going to have, before you proceed to roll that many dice to fill them in. And here's the kicker: in order for the resulting outcome to be uniformly distributed, the number of nontrivial digits must itself be drawn uniformly from the set of all natural numbers!
So, you've gone in a circle again. You're assuming that you've already done a supertask, and then citing that as proof that you've accomplished a supertask.
By that logic, I could never select any number, period. 2. But I just did. 8 I just did it again.
Again, it's only a problem to select a number uniformly from the naturals. You can quite easily select the range from any well-defined probability distribution on the naturals (in particular, the trivial r.v. of range=1 is very easy to employ), but the resulting outcome won't be uniformly distributed on the natural numbers.
I need to have different rules of equivalent ease for different numbers (saying, for example 'these numbers represent multiples of powers of Grahams number is equivalent to saying 'these numbers represent multiples of powers of ten - the increased complexity is in the expansion from multiples of powers of grahams number to multiples of powers of 10).
The thing is that almost all natural numbers don't have simple structures that allow for simple, finite rules like this.
I need to be able to represent the same number in every set of rules, irrespective of complexity.
If "the same number" can be represented in every set of rules, and you can do this for an arbitrary number, then that is equivalent to requiring every set of rules to be able to represent every natural number. Which is impossible to do with finite complexity: to represent every natural number, you need a countable number of digits.
I suppose the simplest way to describe it could be "A set of scale dependent rules".
That's fine, but the increase in scale is not the problem (10 trillion is just as easy to type as 10 million), but complexity. The big numbers you've cited all have special structure: they have long strings of zeros to the right (as well as endless strings of zeros to the left).
To put it concretely, it may be as easy to communicate "1000000000" as it is to communicate "10", given a suitable encoder. But what about ten-digit numbers that aren't full of runs of zeros? "1546388725," for example? Can you come up with a system of rules for that one that is more concise than the ten digits that comprise it? The problem here isn't scale, but dynamic range.
Sure, you can argue that then I have infinitely many rules , and you'd probably be right, and that because I can't communicate all of them, that my scheme is bunk, but in that I'd argue you're wrong. I only need to be able to communicate the relevant rule, and how it relates back to numbers that we 'understand'.
What makes you think that you can select out only a finite number of rules, and still have them work? The whole reason you have an infinite set of rules in the first place is because the requirements that you specified implied that.
RJBeery
01-29-09, 01:43 PM
Ben, you are right the thread has been resolved IMHO but I think Trippy and some others are practicing their debating skills rather than seeking truth. And in the meantime I think some people are having a bit of fun!
rpenner
01-29-09, 02:22 PM
Hello, BenTheMan.
Here is an arXiv paper that is going to get its poster de-listed:
http://arxiv.org/abs/0809.4144
Commentary:
http://scienceblogs.com/goodmath/2009/01/the_continuum_hypothesis_solve.php
Here is an arXiv paper that is going to get its poster de-listed:
Censorship: because the censors are always right, silly.
Yes, you must use one fixed set of rules for every possible outcome. Otherwise, if you want to design a custom set of rules after selecting a number, you'll have to ALSO communicate the rules and symbols in order to communicate the number.
And that is circular: the complexity of communicating a system of symbols capable of representing any particular natural number is exactly the same as the complexity of communicating any particular natural number in the first place. I.e., your system that converts "1" into an arbitrary number: it consists of the single rule "map one to the natural number n."
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.
Yes, as you can see, the entropy (minimum expected message length) is finite for well-defined (i.e., non-uniform) distributions on the naturals, but diverges if you try to put in a uniform distribution.
Only true if you restrict yourself to a single rule at all times.
On the contrary, they ALL have infinite length. We just express them in a certain shorthand, because they all eventually end up with an endless string of zeros.
I.e., to express a given natural number takes countably many digits. When you refer to the number "8," you're using a shorthand for the number "...00008", where the left-hand zeros go on for ever. So, to truly generate a uniform random natural number, you need to roll a countable number of 10-sided dice, one for each digit.
See above.
And I only need 1 ten sided dice to determine a number between 1 and 10.
Your idea for exploiting the finiteness of natural numbers consists of noting that any finite natural number will eventually have an endless string of zeros on the left, which you can denote via a special symbol (a blank space, usually), followed by some finite string of digits. So, you propose that you can generate such a number in finite time because there are only finitely many non-trivial digits. The problem with this is that you're skipping a step: to generate a random number in this way, you first have to randomly select how many nontrivial digits it's going to have, before you proceed to roll that many dice to fill them in. And here's the kicker: in order for the resulting outcome to be uniformly distributed, the number of nontrivial digits must itself be drawn uniformly from the set of all natural numbers!
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.
The thing is that almost all natural numbers don't have simple structures that allow for simple, finite rules like this.
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?
If "the same number" can be represented in every set of rules, and you can do this for an arbitrary number, then that is equivalent to requiring every set of rules to be able to represent every natural number. Which is impossible to do with finite complexity: to represent every natural number, you need a countable number of digits.
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.
That's fine, but the increase in scale is not the problem (10 trillion is just as easy to type as 10 million), but complexity. The big numbers you've cited all have special structure: they have long strings of zeros to the right (as well as endless strings of zeros to the left).
To put it concretely, it may be as easy to communicate "1000000000" as it is to communicate "10", given a suitable encoder. But what about ten-digit numbers that aren't full of runs of zeros? "1546388725," for example? Can you come up with a system of rules for that one that is more concise than the ten digits that comprise it? The problem here isn't scale, but dynamic range.
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:
94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387
Right? oops. No string of zeros there either.
What makes you think that you can select out only a finite number of rules, and still have them work? The whole reason you have an infinite set of rules in the first place is because the requirements that you specified implied that.
Because any natural number I can select is finitely complex, and can therefore be represented in a lesser form with rules of finite complexity.
Seems like everybody was wrong.
This is 400 level stats.
Infinite Discrete Random Variables (http://www.math.upenn.edu/~deturck/m480/m480lec6/m480lec6.html)
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.
quadraphonics
01-29-09, 07:48 PM
Seems like everybody was wrong.
This is 400 level stats.
Infinite Discrete Random Variables (http://www.math.upenn.edu/~deturck/m480/m480lec6/m480lec6.html)
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.
??? 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?
Trippy, Pete: I've been thinking about the K-40 issue which I thought was dead and plainly wrong (at least in the way that I interpreted Trippy's proposal). However, what if you took an infinite number of K-40 atoms, each separated and representing a binary digit of the infinite number to be selected. Then you wait exactly the expected half-life of the atoms (1.3 billion years). If an atom has decayed it represents a one, otherwise it represents a zero.
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 (http://www.springerlink.com/content/l632938j47u80732/).
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?
??? 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?
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).
quadraphonics
01-29-09, 08:17 PM
No. I've chosen not to represent those other numbers.
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.
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 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?
"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.
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.
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.
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.
Only true if you restrict yourself to a single rule at all times.
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.
See above.
And I only need 1 ten sided dice to determine a number between 1 and 10.
Indeed, but you need to determine a countable number of numbers between 1 and 10, not just "a number."
Right. And what was I saying about 'scale dependent rules'?
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.
And what was the purpose of the K-40 atom in my machine?
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.
Show me where I was assuming this again?
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.
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.
Please substantiate the assumption that any such set of 'easy' rules exists, for every natural number.
Because any natural number I can select is finitely complex, and can therefore be represented in a lesser form with rules of finite complexity.
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.
The machine has a \frac{1}{2^n} probability of producing an n digit number, but each n digit number has an equal \frac{1}{10^n} chance of occuring - whether it be a '1' with n-1 zeros in front of it, or 9 repeated n times.
Yes, Trippy.
So you do realise that your device is biased to produce numbers with fewer digits, right?
Then we may have had a miscommunication about that fact.
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.
Actually, it describes how to deal an infinite discrete random variable, the POisonn distribution falls out of that dealing.
It doesn't describe discrete random variables of uniform distribution, Trippy.
Do you not understand the importance of this?
quadraphonics
01-29-09, 08:26 PM
Actually, it describes how to deal an infinite discrete random variable, the POisonn distribution falls out of that dealing.
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.
Did it occur to you that your question might be meaningless?
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 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.
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.
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).
The probability of what, exactly? Nothing having to do with a Poisson distribution, that I know of.
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.
The evidence would appear to suggest otherwise.
The probability if we accept that the probability of a specific atom decaying in a half life is 50%, and we have a program that generates 1 digit each half life, then the probability of generating a six digit number is: \frac{1}{2^6} however, because we are using 10 symbols, then P(x=000001) = P(x=999999) = \frac{1}{10^6} However, this is different from the probability of generating a result that will be read as 1 after 6 half lives is:
P(x=1) + P(x=01) + P(x=001) + P(x=0001) + P(x=00001) + P(x=000001)
Which is to say:
\frac{1}{10}.\frac{1}{2} + \frac{1}{10^2}.\frac{1}{2^2} + \frac{1}{10^3}.\frac{1}{2^3} + \frac{1}{10^4}.\frac{1}{2^4} + \frac{1}{10^5}.\frac{1}{2^5} + \frac{1}{10^6}.\frac{1}{2^6}
Or about .053
It doesn't describe discrete random variables of uniform distribution, Trippy.
Do you not understand the importance of this?
Show me, again, where I said it did, Pete.
The evidence would appear to suggest otherwise.
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?
Show me, again, where I said it did, Pete.
Show me where I said you said it did. :rolleyes:
Do you understand that no one has a problem with non-uniform infinite discrete distributions?
Do you understand that infinite discrete random variables of [i]non-uniform[i] distribution are irrelevant to the question posed?
If so, then why do you think that page answers the question?
Firstly, that's not complete - there are more terms to add to get the complete probability of a 1.
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?
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?
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.
Pete and Quadraphonics.
Nasor, and again the answer in theory is ZERO but in reality it is greater than that because our ability truly choose a RANDOM number from an infinite set is not possible. As was mentioned, it is the same problem that arises when you consider things like the size of the hotel the Angel is in, the time it takes to visit each door, etc. The mind experiment breaks from theory when brought into "reality".
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.
Hence, the link answers the thread.
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.
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 (http://www.sciforums.com/showpost.php?p=2151886&postcount=79) that the problem of interest was regarding a uniform distribution, and you explicitly acknowledged this fact in your reply (http://www.sciforums.com/showpost.php?p=2151962&postcount=81):
The problem at hand is taking a random selection from a uniform distribution of the naturals.
Right.
...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.
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 (http://www.sciforums.com/showpost.php?p=2151886&postcount=79) that the problem of interest was regarding a uniform distribution, and you explicitly acknowledged this fact in your reply (http://www.sciforums.com/showpost.php?p=2151962&postcount=81):
...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.
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.
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?
RJBeery
01-30-09, 08:55 AM
Nasor, and again the answer in theory is ZERO but in reality it is greater than that because our ability truly choose a RANDOM number from an infinite set is not possible.
Trippy: the reason I made RANDOM in all caps is because that is the term that necessitates a uniform distribution.
Also, with regards to your K-40 number generator it had more merit than I originally gave it. I tweaked the idea here:
what if you took an infinite number of K-40 atoms, each separated and representing a binary digit of the infinite number to be selected. Then you wait exactly the expected half-life of the atoms (1.3 billion years). If an atom has decayed it represents a one, otherwise it represents a zero.
...which would work. The problem that I was having is that your proposed system 1) had no way of terminating to know when the number has been selected, and 2) had no way of choosing a digit greater than 1 (either it decayed or it did not). It was therefore confusing when you would mention waiting 6 half-lives to determine 6 decimal digits. I realize now that, the binary/decimal digit issue aside, what you MEANT was that the LENGTH of the number being chosen was pre-determined, then you use the K-40 method to generate it.
If that's what you meant then you are correct that it would in fact be a uniform distribution for a given length.
RJBeery
01-30-09, 09:00 AM
Pete, the "infinite K-40 atom" proposal (or the ones that you mentioned) do produce finite numbers if the leading digits are all zero. If you claim that producing an infinite string of zeroes is not possible then I think we're just bumping up against the very impossibility of randomly choosing a finite number from the infinite set.
The pie mans answer:
The question is what is the probability of selecting 1 choice from an infinite
number. Probability compares a part to the whole. In this case, the
whole is not defineable (unbounded), is indeterminate, thus probability does not apply.
You can match the set of even integers to the set of integers, 1 to 1, but you know that given a random sample of integers, 1/2 will be even.
Pete, the "infinite K-40 atom" proposal (or the ones that you mentioned) do produce finite numbers if the leading digits are all zero.
Yes, but that's a big if! Infinitely big! I mentioned it in post 186 (http://www.sciforums.com/showpost.php?p=2154278&postcount=186):
So, let the demon spin its infinite dice [or decay its infinite atoms, or flip its infinite coins] 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.
If you claim that producing an infinite string of zeroes is not possible then I think we're just bumping up against the very impossibility of randomly choosing a finite number from the infinite set.
Well, it's not necessarily that it's not possible, its that it turns the problem into a hypertask (http://www.springerlink.com/content/l632938j47u80732/)... the demon must not just complete infinite things in a finite time, it must complete uncountably infinite things in a finite time.
This process is more involved than it might appear:
If the demon sequentially generates countably infinite random strings of infinite digits, (eg it chooses one infinite string at t=0, another infinite string at t=1/2, a third at t=3/4, a fourth at t=7/8, etc), then I think that strictly zero of those strings will end with infinite zeros.
In order to have a non-zero chance of spinning a finite number (any finite at all!), the demon must spin its infinite dice uncountably infinite times.
Interesting, I think (not certain) that it follows that when the demon spins its first natural, it will have already completed uncountably infinite spins which were rejected for not being finite.
Do you then aknowledge that if my K-40 machine triggers after n halflives, then the probability distribution of the results is uniform?
Yes, I do.
Given any finite size, we can of course produce a uniform distribution of that size.
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).
Trippy, the problem is about choosing from an infinite distribution, right?
So, what is interesting about the device? The distribution before the atom decay, or the distribution after the atom decay?
After the atom decay has chosen the order of magnitude, the distribution of possible numbers is finite and uniform.
Before the atom decay has chosen the order of magnitude, the distribution of possible numbers is infinite and nonuniform.
I agree that there are many opportunities for confusion and misunderstanding in this topic. We're touching on some difficult areas - set theory, information theory, and the seamier side of probability. I don't pretend to have a complete grasp on the topic, and there is a very high probability that I've made some serious errors (or at least naive misinterpretations) in the thread. But, I'm only a business major! :o
Cheers,
Pete
Trippy: the reason I made RANDOM in all caps is because that is the term that necessitates a uniform distribution.
No. A purely random distribution can still be biased, or polymodal.
Being random does not neccessitate a uniform distribution of probabilities.
An example - rolling 1d10 until a 6 comes up and recording the sequence of numbers as a number - it's biased towads short numbers ending in 6
The problem that I was having is that your proposed system 1) had no way of terminating to know when the number has been selected, and 2) had no way of choosing a digit greater than 1 (either it decayed or it did not). It was therefore confusing when you would mention waiting 6 half-lives to determine 6 decimal digits. I realize now that, the binary/decimal digit issue aside, what you MEANT was that the LENGTH of the number being chosen was pre-determined, then you use the K-40 method to generate it.
If that's what you meant then you are correct that it would in fact be a uniform distribution for a given length.
You've misundestood my machine, re-read my original description:
I have a single atom of Potassium-40.
I know that an Ensemble of Potassium-40 atoms will undergo all three types of Beta decay with a half life of 1.28x10^9 years, but, I can not know how long that individual atom is going to last. It might decay 1 second from now, 100 years from now, or it might 'never' decay.
That Potassium-40 atom is in a chamber that measures when that Potassium 40 decays to Argon or Calcium (depending on the decay method). This chamber is connected to a software switch.
The software switch controls a program that checks on it's state once every loop, and generates a random number between 0 and 9 every loop.
When (and if) the atom decays, the program stops, and outputs the string as a random number.
The equivalent is you sitting there, rolling 1d10 until you're told to stop, and writing the results of each individual roll down on to a piece of paper, handing that piece of paper over to the other person who then reads the sting of single digit random numbers you've written down as a single random number.
Does that help clarify how you've misunderstood my machine?
It generates a string of single digit random numbers between 0 and 9.
The length of the string is determined by the decay of the K-40 atom, and how many random numbers I can generate per second.
That is the sole role of the K-40 atom: It determines how many digits are in the final number (that is, the string). The actual value of the random number that is generated (as the string) is determined by the random number generator.
The K-40 machine has a finite, non-zero probability of generating a number of any arbitrary length, and when it does so it has an equal chance of generating a number of any value.
Because the length of the number is important, before the machine activates and spits out a number there's a 5.26% chance (You can calculate this as the sum to infinity of a Geometric series) that it's going to produce a number that will be read as one, but that includes choices of (if I can miss apply some chemistry notation*):
1,01,001,0001,00001,000001,0000001,...,000000[0]_n1
However, if the machine produces a result after n halflives, then the result can only be in the interval:
000000[0]_n =< x =< 999999[9]_n
However the machine can not produce a result in the interval:
000000[0]_{n-1} =< x =< 999999[9]_{n-1}
But it can produce strings with the equivalent value.
For example, although it can't produce 999999[9]_{n-1} it can produce as a string 099999[9]_{n-1} which is the same length as 999999[9]_n but has the same value as a number as 999999[9]_{n-1}, but the strings 9999999[9]_{n} 0999999[9]_{n-1} and 00000[0]_{n-1}9 all have the same probability of being output if the machine gives you your number after n half lives.
Does this help any?
*In chemistry the notation [ ]_n means "Repeat what's inside the square brackets n times.
I agree that there are many opportunities for confusion and misunderstanding in this topic. We're touching on some difficult areas - set theory, information theory, and the seamier side of probability. I don't pretend to have a complete grasp on the topic, and there is a very high probability that I've made some serious errors (or at least naive misinterpretations) in the thread. But, I'm only a business major! :o
Cheers,
Pete
There have been several already in fact :) and for myself, I will confess to having been somewhat irritated at some of the suggestions that have been made - the prime one being that I am simply practicing my debating skills. If I continue arguing against an idea it is because I am genuinely unconvinced - for whatever reason, by the arguments being presented by the person I am debating with.
quadraphonics
01-30-09, 06:56 PM
No. A purely random distribution can still be biased, or polymodal.
Being random does not neccessitate a uniform distribution of probabilities.
It's standard practice to assume that the distribution is uniform when it is not otherwise specified. Indeed, the entire point of this thought experiment is to illustrate how that assumption will get you into trouble in certain cases.
Likewise, it's not uncommon for the phrase "purely random" to denote "uniformly distributed," the idea being that, for any non-uniform distribution, there is some degree of "predictability," in the sense that you can predict that the outcome will be near the mode (or will not be near a low-probability region) and you will end up being correct more often than not. With a uniform distribution, you can't do that: any guess at what the outcome will be is as good as any other (provided it's within the support of the distribution).
The kicker to all this is that, for an infinite set, we MUST have a non-uniform distribution. But any non-uniform distribution we can apply will emphasize certain regions of the naturals over others. And, since we have no information on which regions should be more likely, that amounts to the addition of arbitrary information to the thought experiment. Which is to say that the correct answer is "there is no way to assign a unique probability to the event that the angel finds the demon without more information."
It's standard practice to assume that the distribution is uniform when it is not otherwise specified. Indeed, the entire point of this thought experiment is to illustrate how that assumption will get you into trouble in certain cases.
Likewise, it's not uncommon for the phrase "purely random" to denote "uniformly distributed," the idea being that, for any non-uniform distribution, there is some degree of "predictability," in the sense that you can predict that the outcome will be near the mode (or will not be near a low-probability region) and you will end up being correct more often than not. With a uniform distribution, you can't do that: any guess at what the outcome will be is as good as any other (provided it's within the support of the distribution).
No it isn't. In fact, in all of the Statistics i've ever studied, assuming a 'uniform' distribution can get you in a lot of trouble.
quadraphonics
01-30-09, 08:02 PM
No it isn't. In fact, in all of the Statistics i've ever studied, assuming a 'uniform' distribution can get you in a lot of trouble.
Any assumption can get you into a lot of trouble, and so it's always better to specify the distribution (uniform or otherwise). But expediency being what it is, uniformity has become the standard assumption for cases where the distribution is not specified (at least for finite sets). There are also other reasons to consider a uniform distribution as the "default," such as its uninformative nature (in the Bayes sense).
If you haven't observed this convention, well, give it some time. It's quite common, particularly once you get outside the realm of actual math classes (math professors are notoriously picky about this kind of thing, and so tend to always specify the distribution).
Any assumption can get you into a lot of trouble, and so it's always better to specify the distribution (uniform or otherwise). But expediency being what it is, uniformity has become the standard assumption for cases where the distribution is not specified (at least for finite sets). There are also other reasons to consider a uniform distribution as the "default," such as its uninformative nature (in the Bayes sense).
If you haven't observed this convention, well, give it some time. It's quite common, particularly once you get outside the realm of actual math classes (math professors are notoriously picky about this kind of thing, and so tend to always specify the distribution).
Most of the distributions I deal with on a daily basis (I work for the equivalent of teh USEPA) are normal, or log normal. There's not much call for Binomial distrbibutions in environmental monitoring (that i've come across anyway).
quadraphonics
01-30-09, 08:14 PM
Most of the distributions I deal with on a daily basis (I work for the equivalent of teh USEPA) are normal, or log normal.
Yeah, those two distributions, along with uniform, account for a huge proportion of the statistics that people actually use outside of math classes. The normal is very much the "default" distribution when your domain is the real line (or plane or etc.), although it lacks the "uninformative" features of the uniform distribution.
There's not much call for Binomial distrbibutions in environmental monitoring (that i've come across anyway).
I'm sure you could find some situations if you looked. Indeed, many of the places where the Normal distribution is applied are actually approximations to binomial distributions where the number of Bernoulli trials is large.
I'm sure you could find some situations if you looked. Indeed, many of the places where the Normal distribution is applied are actually approximations to binomial distributions where the number of Bernoulli trials is large.
Perhaps, but the main place I could see that sort of thing being useful is if I wa slooking at things like Mean time between failures, which is something that might be useful in some regards, now that I think about it.
quadraphonics
01-30-09, 10:21 PM
Well, it's not necessarily that it's not possible, its that it turns the problem into a hypertask (http://www.springerlink.com/content/l632938j47u80732/)... the demon must not just complete infinite things in a finite time, it must complete uncountably infinite things in a finite time.
I'm pretty sure that uniformly drawing a natural number is a supertask. Drawing a real number would be a hypertask, in my understanding.
So I think the answer must be that if you let the demon pick digits for long enough, he will eventually type out an infinite set of zeros. But it would seem that the exact same argument would show that he will eventually type an infinite number of, say, 7's, so I must be missing something.
disease
01-30-09, 11:28 PM
I think there might be some confusion about what a number is, and making a choice. One already exists, the other is a, well, a random walk, say.
It's an enumeration problem. A calculation is a Turing machine, you know.
P.S. which means the problem: The demon goes into a hotel with an infinite number of rooms, and randomly picks a room to hide in. The point of the story was that if the angel only gets to look behind one door, there is no possible way that he could ever find the demon.
...reduces to a decidability one. Can a program be written that can look into an infinite number of 'rooms' in one attempt?
Which translates into: can a Turing machine read an infinite number of symbols (on an infinite tape), in one algorithm, and decide one of them is "the demon".
disease
01-31-09, 02:34 PM
Note: if the machine reads just one symbol on the tape, there are an infinite number of unread symbols left.
But an infinite tape has no "start position", so the problem is now: which single symbol, on an infinite length tape should the machine read, or, how many symbols should it skip over before reading one? Now there are two decisions the "algorithm" needs to make.
It's standard practice to assume that the distribution is uniform when it is not otherwise specified. Indeed, the entire point of this thought experiment is to illustrate how that assumption will get you into trouble in certain cases.No it isn't. In fact, in all of the Statistics i've ever studied, assuming a 'uniform' distribution can get you in a lot of trouble.
I agree with Trippy. It is standard practice to assume a Gaussian distribution. For one thing, there's the central limit theorem. For another, there's no random distribution more amenable to mathematical analysis than a Gaussian. This latter fact leads people to assume a Gaussian where they should not.
The kicker to all this is that, for an infinite set, we MUST have a non-uniform distribution. But any non-uniform distribution we can apply will emphasize certain regions of the naturals over others.
Correct again.
quadraphonics
02-02-09, 02:19 PM
I agree with Trippy. It is standard practice to assume a Gaussian distribution.
On the natural numbers? The only assumption that I consider 'standard' for the natural numbers is that the elements are ordered by decreasing probability (and of course that the probability adds up to 1).
For one thing, there's the central limit theorem.
What about it? There is no linear combination of independent variables going on here.
For another, there's no random distribution more amenable to mathematical analysis than a Gaussian.
I would suggest that the uniform distribution is even more amenable to mathematical analysis than the Gaussian, or at least "as amenable." Expectations don't get much simpler than whent he density is constant, and the domain finite :]
I'm pretty sure that uniformly drawing a natural number is a supertask.
I would have thought so too, but I can't construct any countably infinite set of tasks that would do the job. That's not supposed to be conclusive, just a call for further research.
Drawing a real number would be a hypertask, in my understanding.
Drawing a real number is definitely a supertask - for example, roll a ten sided die infinite times, once for each digit in the decimal representation.
quadraphonics
02-02-09, 06:54 PM
I would have thought so too, but I can't construct any countably infinite set of tasks that would do the job. That's not supposed to be conclusive, just a call for further research.
Yeah, same boat I'm in. Probably it's time to dig out some actual papers on this stuff and find out for real...
Drawing a real number is definitely a supertask - for example, roll a ten sided die infinite times, once for each digit in the decimal representation.
Seems like that would work just as well for a natural number, no? Except that you'd only have to draw "half" as many numbers, since there wouldn't be any to the right of the decimal point.
I am pretty confident that drawing a real number is a hypertask, and that drawing a natural number is only a supertask. I will let you know if I manage to either find examples of constructions that illustrate this, or find out that I am wrong.
Apparently there's also such a thing as a super-dupertask, which consists of a countable number of tasks, followed by a "last" task (0.999... != 1, anyone?). I nominate "super-dupertask" for the coolest name...
Seems like that would work just as well for a natural number, no? Except that you'd only have to draw "half" as many numbers, since there wouldn't be any to the right of the decimal point.
I made a mistake... I was only thinking of reals between zero and one, so all numbers chosen were to the right of the decimal point.
Having infinite digits to the left of the decimal point poses a problem, in that the number selected will be infinite... and I think that we need to guarantee that the selected number will be finite.
So it looks like selecting a random real from a uniform distribution of all reals might indeed be a hypertask... which is puzzling to me if randomly selecting from a subset of the reals in a given range is only a supertask.
So, to the mathematicians out there - what substantial difference is there between the set of reals that can be selected by randomly choosing infinite digits, and the set of all reals? And why does this seem to make a difference in the number of tasks required to select a random element from the set? (Does it make a difference?)
Do the two sets have the same cardinality?
I think the first set is bounded... does that make a difference?
quadraphonics
02-02-09, 07:39 PM
I made a mistake... I was only thinking of reals between zero and one, so all numbers chosen were to the right of the decimal point.
Ah, okay... although... doesn't the real segment [0,1] actually have the same cardinality as the entire real line?
Having infinite digits to the left of the decimal point poses a problem, in that the number selected will be infinite... and I think that we need to guarantee that the selected number will be finite.
Right, but that's again the same problem with drawing from the set of naturals, right? Put it this way: given some (randomly selected) natural number, we could then produce a randomly selected real number by generating a (countably) infinite number of digits to the right of the decimal.
So it looks like selecting a random real from a uniform distribution of all reals might indeed be a hypertask... which is puzzling to me if randomly selecting from a subset of the reals in a given range is only a supertask.
Yeah, I think it's actually a hypertask to choose a real from, say, [0,1]. But I'm definitely on thin ice here, so...
Ah, okay... although... doesn't the real segment [0,1] actually have the same cardinality as the entire real line?
Yes, I think it does. Which is why I'm puzzled. The set of reals in [0,infinity) seems to be a lot like the set in [0,1].
Right, but that's again the same problem with drawing from the set of naturals, right? Put it this way: given some (randomly selected) natural number, we could then produce a randomly selected real number by generating a (countably) infinite number of digits to the right of the decimal.
Right. Which is why I now agree that choosing randomly from a uniform distribution of all reals might be a hypertask.
Yeah, I think it's actually a hypertask to choose a real from, say, [0,1].
Why?
Choosing countably infinite random digits to place after the decimal point is a supertask, right?
And the pool of possible results is the same as the reals in [0,1], right?
So, to the mathematicians out there - what substantial difference is there between the set of reals that can be selected by randomly choosing infinite digits, and the set of all reals? And why does this seem to make a difference in the number of tasks required to select a random element from the set? (Does it make a difference?)
Do the two sets have the same cardinality?
I think the first set is bounded... does that make a difference?
Another mistake... I meant closed, not bounded.
But it doesn't make a difference, because we can make the first set open by simply removing the largest element - the one containing all nines.
I'm still not 100% sure on cardinality... does the set [0,1) have the same cardinality as [0,infinity)?
I suspect that it does, but how do you demonstrate it?
quadraphonics
02-02-09, 09:51 PM
Yes, I think it does. Which is why I'm puzzled. The set of reals in [0,infinity) seems to be a lot like the set in [0,1].
Yeah, there is a bijection between them (i.e., f(x) = 1/x... well, that only gets you [1,infinity), but clearly that has the same cardinality as [0,infinity) )
Choosing countably infinite random digits to place after the decimal point is a supertask, right?
I believe so, yes.
And the pool of possible results is the same as the reals in [0,1], right?
Yeah, that's where I get stuck too. I think the answer must have to do with the issue that all natural numbers must eventually end up with an infinite string of zeros, whereas the reals do not have this constraint. But I'm not sure how to make that concrete...
I'm still not 100% sure on cardinality... does the set [0,1) have the same cardinality as [0,infinity)?
I suspect that it does, but how do you demonstrate it?
Yeah, see above. There are various ways to demonstrate that kind of thing, but finding a bijection between the two sets is probably the most direct way.
Note that you can also show that R^n has the same cardinality as R.
You guys are stuck because the underlying idea is nonsense. The concept of a uniform distribution over an infinite range (or a uniform distribution over a countably infinite set) does not make any sense. There are a plethora of perfectly valid distributions over an infinite range (e.g. guassian, exponential, ...) and over a countably infinite set, but a uniform distribution is not one of them.
disease
02-06-09, 05:00 AM
It's all nonsense, in fact. Even having an idea that it's all nonsense, is complete nonsense.
iceaura
02-06-09, 11:31 AM
So, to the mathematicians out there - what substantial difference is there between the set of reals that can be selected by randomly choosing infinite digits, and the set of all reals? The selected set is countable - same size as the integers.
You could, for example, time-stamp each choice.
quadraphonics
02-10-09, 02:34 PM
After a bit of thought, it seems to me that the relevant measure here is not cardinality, but order type (http://en.wikipedia.org/wiki/Well-order).
Also, an overview of related topics (http://www-history.mcs.st-and.ac.uk/HistTopics/Real_numbers_3.html).
vBulletin® v3.8.1, Copyright ©2000-2010, Jelsoft Enterprises Ltd.