Randomly selecting from an infinite number of choices

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

  1. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    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.
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    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.

    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"?

    Well, in post 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.
    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?
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    Sure, given infinite time, speed, or symbol availability.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    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?
     
  8. quadraphonics Bloodthirsty Barbarian Valued Senior Member

    Messages:
    9,391
    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.

    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.

    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.

    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 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.

    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.

    What is important is that there are infinitely many natural numbers.

    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 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?

    A compelling rebuttal, if ever I've read one :]

    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.
     
  9. quadraphonics Bloodthirsty Barbarian Valued Senior Member

    Messages:
    9,391
    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.
     
  10. quadraphonics Bloodthirsty Barbarian Valued Senior Member

    Messages:
    9,391
    ??? That's the exact same problem as selecting a single number uniformly from the naturals, isn't it???

    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.
     
  11. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    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?
     
    Last edited: Jan 29, 2009
  12. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    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.
     
  13. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    No. Not subtle to the point of meaningless, and i'm just about done trying to explain it.



    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.



    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'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.



    Expected value.



    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.



    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).



    And that's my problem how again?



    You? Flame? Never.



    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.
     
  14. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    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.



    I don't need to account for numbers that I have already decided not to choose.

    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).
     
  15. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    You described it as a binomial distribution twice (post 95, post 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.

    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, and I explicitily asked three times for clarification in subsequent posts.

    You responded:
    There was no confusion on that point, at least.

    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.

    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.

    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."
     
  16. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    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.
     
  17. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    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.


    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}\)


    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.


    Then we may have had a miscommunication about that fact.
     
  18. Trippy ALEA IACTA EST Staff Member

    Messages:
    10,890
    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).
     
  19. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    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.
     
  20. zanket Human Valued Senior Member

    Messages:
    3,777
    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.
     
  21. BenTheMan Dr. of Physics, Prof. of Love Valued Senior Member

    Messages:
    8,967
    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 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.
     
  22. quadraphonics Bloodthirsty Barbarian Valued Senior Member

    Messages:
    9,391
    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.

    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.

    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.

    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.

    The thing is that almost all natural numbers don't have simple structures that allow for simple, finite rules like this.

    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.

    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.

    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.
     
  23. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    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!
     

Share This Page