Monday, September 21, 2015

Rational Numbers and Randomized Digits

Here's a quick thought experiment to develop intuition about the cardinality of rational versus irrational decimal numbers. We know that any rational number (a/b with integer a, b and b ≠ 0) has a decimal expansion that either terminates or repeats (and terminating is itself equivalent to ending with a repeating block of all 0's).

Consider randomizing decimal digits in an infinite string (say, by using a standard d10 from a roleplaying game, shown above). How likely does it seem that at any point you'll start rolling repeated 0's, and nothing but 0's, until the end of time? It's obviously diminishingly unlikely, so effectively impossible that you'll roll a terminating decimal. Alternatively, how probable does it seem that you'll roll some particular block of digits, and then repeat them in exactly the same order, and keep doing so without fail an infinite number of times? Again, it seems effectively impossible.

So this intuitively shows that if you pick any real number "at random" (in this case, generating random decimal digits one at a time), it's effectively certain that you'll produce an irrational number. The proportion of rational numbers can be seen to be practically negligible compared to the preponderance of irrationals.


24 comments:

  1. > and terminating is itself equivalent to ending with a repeating block of all 0's

    Or 9's!

    ReplyDelete
  2. Also, I'm imagining this fair die that always lands on one side by chance. It's a world-wide sensation, scientists propose different theories for this behaviour, measure all aspects of the die; graduate students defend PhD theses on it; the die spawns a miriad of memes; cults form around it.

    ReplyDelete
    Replies
    1. Get me on that train of thought, awesome! :-D

      Delete
  3. You know, I was prepared to be bewildered by this, but you explained it in a clear, concise fashion that even a humanities wonk can grok. Thanks! I learnt something!

    ReplyDelete
    Replies
    1. Sweet, that's totally what I was aiming for!

      Delete
    2. Georg Cantor once said, "The rationals are spotted in the line like stars in a black sky while the dense blackness is the firmament of the irrationals", which I think is perfect -- but when I say this to non-math people it usually doesn't help any.

      Delete
  4. You say it's "effectively impossible" to roll repeated zeros and yet you think its perfectly possible to roll say 3141592654.. until the "end" to get an irrational number i.e. pi. the problem with existence arguments for infinities is that they are circular. If I say look, you can't do anything "for ever" so at some point you must stop rolling the dice then you have only generated rational numbers and zero irrational numbers.

    ReplyDelete
    Replies
    1. Well again, it's just an intuitive argument for our friends who can't join in discussions of limits of series, or Cantor's diagonal argument, etc. But if you say "at some point everything stops", then you don't even get all the rational numbers, just terminating ones, i.e., only fractions that have factors of 2 and 5 in the denominator. Which is a totally different subject.

      Delete
  5. Your explanation doesn't seem quite right somehow. Rolling a string of zeroes is just one of a number of possibilities and has equal probability to any other sequence. Anyway, my head is hurting now!

    ReplyDelete
    Replies
    1. True, but there are infinitely many "other sequences" (uncountably so), so the probability of the all-zero sequence is zero.

      Delete
  6. Yes, a string of zeroes has the same probability as any other string of the same length, but that's not the point. The point, as I take it, is this:

    *if you roll a "0" for the first number past the decimal, then you have an exactly 10% chance (that is, if you roll another "0") of hitting another one, which would make this a repeating decimal and you're done.

    *Now, if you roll a "0" and something else - a "1," say - you need to roll another "0" AND a "1" after it before your sequence becomes a repeating decimal. A 1% chance of that, in other words.

    *If you roll a "0" and a "1" and, I don't know, a "3," then you need to roll exactly that next before it becomes a repeating decimal - "013," in that order - which is a sequence that has only a 0.1% chance of happening.

    *Etc.

    If the sequence doesn't repeat right out of the gate (or nearly so), the chance of it repeating drops the longer the sequence goes. That, at least, is how I understood the intuitive argument. Did I get it right, Daniel?

    ReplyDelete
    Replies
    1. Well... I think you get the flavor of the idea, which is the important thing. Any repeating sequence at all is clearly a lot more constraining than just unorganized series of digits lacking any pattern.

      Delete
    2. To address your particular observation: compare trying to get (a) repeating "15" to (b) repeating "1567". The chance of satisfaction in the next 4 digits is the same for both, because in (a) you're committed to needing "1515", and in (b) you need "1567" (1-in-10,000 chance for either). Etc.

      Delete
    3. Okay, now I think I'm confused again. Why are we concerned about the next four digits in BOTH cases (a) and (b)? I mean, if I have 1.15, then if I get a "15" in the next two decimal places, it's confirmed as a repeating decimal and we're done, right? Once you get a full repetition, you don't need to look any further "downstream" to see if it will deviate, because you know it won't - isn't that how it works? Or am I confused again?

      Delete
    4. Not if you're rolling digits randomly for each place; anything could happen. Which is why it's so incredibly unlikely to keep getting 15's repeating forever.

      Delete
    5. Oh! So a decimal expansion could repeat within itself without becoming a repeating decimal? I think I was lied to by one of my teachers... grrr.

      Delete
    6. Absolutely... in fact, all non-repeating decimals are guaranteed to contain some kind of temporary repetitions. For example, you could check and search for the fairly early place where pi has a block that temporarily goes "999999". Also, lots of "666"'s and frankly everything else as well.

      That said, all fractions of integers a/b definitely must repeat or terminate as decimals, but the point is they actually make up a distinct minority of all real numbers.

      Delete
    7. Other things to do a text-search for in pi: all the times it goes "0101", "1515", and so forth.

      Delete
    8. Okay, I think I see, but if you get a FULL repetition of all the numbers that have occurred past the decimal point, THEN it's a repeating decimal, and you don't have to look any further, right? So, if I had

      1.151155

      I would need the next six digits to line up as "151155" before I could call it a repeating decimal and be done, right? Or is it suspect even then?

      Delete
    9. It's always suspect unless you have outside knowledge, like "this is the result of a fraction", or "this series of digits is known to repeat" (indicated by ellipses or a bar over the repetend). In fact, it's almost certainly not repeating unless you have that outside information.

      Delete
    10. A few examples of irrationals that start of like that: (a) √6 starts off with 2.44, but the full expansion is 2.4494897428... (b) √24 starts off with 4.8989, but the full expansion is 4.8989794856... (b) √79 starts off with 8.888, but the full expansion is 8.8881944173...

      Delete
  7. I think there is still some confusion. The point is all sequences are equally probable. So a completely random sequence (ie pi= 3.141592654...) has the same probability as all zeros or ones. What actually needs justification is that there are more non-repeating sequences than repeating sequences. Also you said that the probability of rolling all zeroes was effectively zero and @delta also said the same thing. If zero is impossible, then so are any other sequences which is a paradox isn't it? then how can this process produce any numbers at all?

    ReplyDelete
    Replies
    1. Be careful of the switch from "effectively impossible" (or "almost impossible") to "impossible". Yes, every decimal number has an equal probability of being generated, and that probability is zero (0). If we accept the idea of a distribution with infinite possibilities, then that's not the same thing as being truly impossible.

      Of course, the measure theory required to show that rationals are a set of measure 0 within the reals is exactly what we're trying to avoid here via an intuitive argument. If you want the formal demonstration, then look someplace like here.

      Delete