Gavin writes:

> Of course for the problem in question, flipping millions of coins turns out
>  to be a waste of time when the precise answer can more easily be found by
>  examining each of the possible outcomes with something like:

I was going to mention that earlier. In this case, 2 to the 20th represents
only one million possibilities discrete possibilities that need to be
examined. It would have been 26x faster to enumerate every string than
actually randomly sample the space 26 million times as Gavin did.

In fact, Jeff's problem is actually very much simpler than that. Because
everyone recognized that only the first 15 draws were of concern (there's
only one possibility out of 64 for the sequence starting on the 15th draw,
and nonethereafter), the size of the actual sample space drops down to a
measly 2^15, which is an extremely manageable 32,768.

Random draws (which are properly called "Monte Carlo" simulations) should
only be used as a last resort, where the sample space is measured in the
billions of possibilities and enumeration quickly becomes impossible.

The best possible solution is always the development of a closed form (or at
least limiting series) equation that describes the outcome for state spaces
of any size.

Wirt Atmar*

*"A proud contributor to threads that will not die."