🚀 go-pugleaf

In article <1130@kepler1.rentec.com> andrew@rentec.com (Andrew Mullhaupt) writes:
>In article <1992Jul29.132817.7113@Princeton.EDU> rdnelson@phoenix.Princeton.EDU (Roger D Nelson) writes:
|>Why don't people interested in "good" RNG's simply use one or another of 
|>the physical random sources, such as radioactive decay or quantum tunneling.
|>Obviously these would not be appropriate for cases where a repetition of
|>the random sequence is desired, but otherwise...?  For a couple of
|>thousand dollars, which is a trivial cost compared to the time spent on
|>algorithmic RNG research, one can buy excellent, well designed and
|>executed commercial RNG's.  I would be interested in some discussion of
|>problems or inadequacies (or indeed virtues) of so-called "true" random 
|>event generators.

>As far as I can tell, there are 4 big problems with using experimental
>observations as RNG's.

>1.	Says who they're _really_ random? Sure we like to think so, but
>	how do you know there isn't a little bias in say, the A/D
>	converter, etc. Keep in mind that a high correlation over a
>	long period is usually as bad as a periodicity, and that if
>	you think about how long a period you get with algorithms,
>	it means that you need to have very good control over the
>	frequency response of your measurement device over a range
>	of frequencies covering more than 10 decades. This is not
>	trivial.

Thes problems you have stated are not the major ones.  If one uses 
radioactive counts, the process is as close to independent as it
is unbiased, and long-term effects are essentially impossible.
HOWEVER, there is no way of testing them beyond the .001 level
of randomness, and there are good reasons for questioning .00001
on the physical grounds of the asymmetry of counters when changing.

There are ways to overcome this, and they are not complicated.  If
one combines with XOR several streams, the problems should disappear.

One problem of pseudo-random numbers is the problem of either having
a not good enough, or a too good, frequency response.  By chance, there
should be a few rather large spectral points.

>2.	They aren't repeatable. This lets out the crypto people who need
>	pseudo-random numbers, anyways, and it probably isn't so convenient
>	for people with giant Monte Carlo things to debug.

For crypto, I agree except for the purpose of one-time pads.  For this,
I doubt that the failure to quite achieve independence or unbiasedness
will be major.

The bigger problem with non-repeatability is the verification on another
machine.  However, avoiding this is very difficult.  Slight numerical
differences in acceptance-rejection routines, or even the choice of
buffer sizes, can introduce a major discrepancy.  

This CAN be handled, but only at great cost, or by having the pedigree
of every random variable used.  It should only be done when absolutely
necessary.  It is a problem also with pseudo-random numbers.

>3.	You can't prove theorems about their outputs very easily. This
>	is similar to (1), but it can also be a defect of some algorithms
>	too.

I do not see that this is a problem, if the points I have mentioned above
are taken care of.

>4.	They tend to have low bandwidth compared to the same quality
>	digital algorithms. I'm not really current on this, but last
>	time I knew anything about this question, there was just no
>	way to beat parallel implementation of algorithmic RNG's on
>	chips.

I agree that this is a problem, unless IO is comparable to the algorithmic
costs.  There is another problem; getting enough of them.  Even on a particular
machine, programs should be checked.  This means that the random numbers 
should be strored on some device and not generated in "real time."   To 
do the procedures I recommend in 1. above would be difficult to do at 
more than 10-100 bits/second anyhow.

It might be a good idea to seed a long-period Tausworthe word procedure
with random numbers, or even an approximation thereof.  This would involve
somewhere between 5KB and 100 KB.  To compare this to existing files of
physical random numbers, the binary version I have of the RAND numbers
is a little over 400 KB, and the Argonne set is a little over 10 MB.

>The way I look at it, the problem with 'natural' RNG is that the market
>is small for it, and so the use of general purpose hardware is always
>economically favored - i.e. algorithmic RNG.

Algorithmic RNG is likely to have some hidden flaws.  There is the 
matter of cost, but it seems that some physical random numbers are
needed to give reasonable assurance that they will not occur.  
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)