Re: AES and Diehard

From: Douglas A. Gwyn (DAGwyn_at_null.net)
Date: 09/13/03 

Date: Sat, 13 Sep 2003 00:42:25 -0400

Mok-Kong Shen wrote:
> Knuth uses 'random' almost synonymously with 'pseudo-random'.

No, he doesn't:
"How can a sequence generated in such a way be random,
since each number is completely determined by its
predecessor? ... The answer is that the sequence *isn't*
random, but it *appears* to be. ... Sequences generated
in a deterministic way such as this are often called
*speudorandom* or *quasirandom* sequences in the highbrow
technical literature, but in most places of this book we
shall simply call them random sequences, with the
understanding that they only *appear* to be random."
I.e., he explicitly establishes that he is using an
informal term solely within the context of the book.
Presumably that was simply to improve readability, since
the entire chapter was concerned with generation of
pseudorandom sequences, testing them against the random
model, and generating nonuniformly distributed variates.

If you want to determine what "random" means in general,
you have to look outside a context where it has explicitly
be introduced as shorthand for the technically correct
"pseudorandom". Any decent textbook on statistics ought
to provide a suitable definition, although most likely
it will be of "random variable" rather than "random" as
such. A *random sequence* is a sequence of values of a
random variable, and can be thought of as outcomes of a
sequence of executions of some definite experiment where
each execution has exactly the same initial context.
Pseudorandom sequences do not have the same context for
production of each value and thus are not random
sequences.

> Perhaps (presumably of some surprise to you) I should
> mention that in the current mathematical terminology
> there is another subtype of 'randomness', namely
> 'quasi-randomness'. Unfortunately I don't have the
> knowledge to give an exact definition of that. ...
> That says all that needs to be said.
> M. K. Shen

Indeed.

Relevant Pages

  • Re: Problems I have with 1.999...=2
    ... Thank you for the time you took, and for the consideration in using small words that a child or layman might understand. ... mean by these infinite decimal expansions and from the context of geometry slowly built up the properties we wanted them to have using the rational numbers and our own reasoning. ... Since the above defines precisely what we mean by two of these infinite sequences being the same, we now turn to the question of 1.999... ...
    (sci.math)
  • Re: Statin Adverse Effects FAQ: ELDERLY
    ... It has a "censorship" feature that blindly looks for particular letter ... sequences, regardless of context, and converts them to hyphens. ...
    (sci.med)
  • Re: Statin Adverse Effects FAQ: ELDERLY
    ... It has a "censorship" feature that blindly looks for particular letter ... sequences, regardless of context, and converts them to hyphens. ...
    (sci.med.cardiology)
  • Re: AES and Diehard
    ... > informal term solely within the context of the book. ... > pseudorandom sequences, ... Look at how the statisticians work. ...
    (sci.crypt)
  • searching for numeric subsequences
    ... why isn't there an equivalent of STRFIND for numeric sequences? ... One frequent application is searching long pseudorandom sequences for ... context of pseudorandom sequences it is reliable, as long as one takes enough ...
    (comp.soft-sys.matlab)