Thursday, October 24, 2013

Arising by chance

Suppose you had a billion dice.  How many times would you expect to roll them before you got all sixes?  That would be six to the billionth power, or about ten to the 780 millionth, that is, a one with 780 million zeroes after it.  As big numbers go, that's bigger than astronomical, but still something you could print out, if only in tiny digits on a very big sheet of paper.  It's smaller than the monstrously big numbers I've discussed previously.  Archimedes' system could have handled it (see this post on big numbers  for more details on all that).

"Bigger than astronomical" means that there's essentially no chance that anyone will ever see a billion dice randomly come up all sixes, even if, say, we set every person alive to rolling a die over and over again, and on through the generations, even if we somehow colonized the galaxy with hordes of dice-rolling humans.

Now suppose that instead of rolling all the dice repeatedly, we just re-roll the ones that didn't come up sixes.  In that case, a bit more than 100 rolls will do.  Why?  With the first roll, about a sixth of the dice -- around 167 million, will come up sixes.  On the second roll, around a sixth of the 833 million or so remaining, or about 139 million, will come up sixes, leaving about 694 million.  Since we're rolling random dice here, these numbers won't be exact, but because we're rolling a whole bunch of dice, they'll be pretty close, percentage-wise.  With each roll there are about 5/6 as many dice left to roll as with the roll before.

At some point, you can no longer assume that close to 1/6 of the dice will come up sixes, but after 100 rolls you should be down to about a dozen, and it won't take too long to get the rest.

One more game before I explain what I'm up to:  Same billion dice, but this time, after an initial roll, you pick one die at random and roll it if it's not a six.  How many times do you have to do this pick-and-roll (sorry) before you have a complete set of sixes?

At the beginning, you have about 833 million non-sixes and it will take about seven tries before you change one of them to a six.  As more and more dice get changed to sixes, it gets harder and harder to find one that isn't already there.  The last die will take about 6 billion tries -- you'll need to roll it about six times, but you'll only get a chance to one in a billion tries.  All told, according to Wolfram Alpha's handy sum calculator, it will take about 20 billion tries before you get all your sixes.  That's not something you could do in an afternoon.  If you could do one try every second, it would take somewhat more than 600 years.  Not really feasible, but not unimaginable.


If we want to talk about something arising by a random process, it matters, and it matters a lot, what kind of random process we're talking about.  In a purely random process, where everything is re-done from scratch at every step, most interesting results will be completely, beyond-astronomically unlikely.  But a process can proceed randomly and still produce a highly-ordered result with very high probability, as long as there is some sort of state preserved from one step to the next.

For example, when sugar crystalizes out of sugar water to make rock candy, it is for all practical purposes completely random which sugar molecule sticks to which part of the growing crystal at any given point.  And yet, the crystal will grow, and grow in a highly, though not completely, predictable fashion, all without violating any laws of thermodynamics.

The end result will be something that would be completely implausible if sugar molecules behaved completely randomly, but they don't.  They behave essentially randomly when drifting around in a solution, but not when near a regular surface of other sugar molecules that's already there.  With each molecule added to the crystal, it's that much easier for the next one to find a place to attach (until enough sugar has crystalized out that the system reaches equilibrium).


Put another way, there is no single such thing as a random process.  There are infinitely many varieties of random process, some with more or less non-random state than others.  It's not meaningful to ask whether something could have arisen at random without specifying what kind of random processes we're talking about.

3 comments:

  1. What happened to "Not in a million years?" I thought it fit nicely in this sequence with this one and the big numbers one.

    ReplyDelete
  2. Somehow it ended up in a "draft" state. It's back now.

    ReplyDelete