[Beowulf] Parallel Development Tools

[Robert G. Brown]

On Wed, 17 Oct 2007, Peter St. John wrote:

> If someone had thought of a way to queue up and read tiny bits of paper
> science would have advanced a decade :-)

<essay length="short">

Ahh, but but but...

Let us grant that a bucket full of such dots can be shaken to where the
order that they are drawn is unpredictable (note well that I don't say
"random" as I'm not convinced that the word means anything beyond an
abstraction in this Universe).  Not unlike the little bingo or lottery
ball machines, they get all mixed up and after enough shuffling or
shaking one can attain a high degree of mixing that makes them
unpredictable and may make them "random" within testable resolution on
the source.

However, is there any guarantee that 0-9 are uniformly distributed in
the original shuffled sample?  There is not.  If you punched out letters
drawn from (say) a dictionary, would they be uniformly distributed?  In
no way.  Would the results of using shuffled strings of either one be
likely to produce acceptable digits in a uniform random distribution?
No.

And in any event, the "randomness" comes from the shuffling, not the
source per se.  So even if one deliberated punched all the numbers out
of many cards and ensured uniform populations of each digit in the
shuffled population (and drew from that population with replacement and
additional shuffling, so that one doesn't immediately introduce bias
after the first digit is drawn) it is the shuffling that matters.  If it
is good, then you don't need "a population" -- you just need one each of
the ten digits and a good shuffler, as you draw, replace, shuffle, draw.

So one is then back to -- how to make a good shuffler?  Physically it
isn't too easy, actually -- there having many balls gives one the
ability to average over the subtle differences between balls that might
produce slight deviations from uniformity in the shuffle/draw.
Numerically you're right back where you started, because a good shuffle
requires a good random number generator (or at least a good source of
unpredictability/entropy).

This is a non-trivial problem, actually.  There are numerous physical
sources of "randomness" or "entropy" out there in the world, but many of
them produce not random bits with an equal probability of 0 and 1 but
"random" bits with some unequal probability of 0 and 1.  Some of them
have autocorrelation times associated with the drawing process.  Some of
them have long term occult periodicities in the signals.  Even with
physical RNGs, about all one can really say is ex post facto either the
strings of random bits they produce pass various statistical tests for
randomness, or they don't.

Throw in Shannon's theorem and some of its consequences -- entropy
theorems applied to code -- and "random" number generation (oxymoron
that it is) is one of the most interesting subjects on the planet, as is
testing and their various applications.
</essay>

    rgb

-- 
Robert G. Brown
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone(cell): 1-919-280-8443
Web: http://www.phy.duke.edu/~rgb
Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977