From: "Scott Collins" <scott_collins@genmagic.genmagic.com>
Date: Thu, 28 Jan 93 14:46:48 PST
To: "Cypher Punks" <cypherpunks@toad.com>
Subject: Biblio re>randomness and OT
Message-ID: <9301282246.AA28614@>
MIME-Version: 1.0
Content-Type: text/plain


Subject:  Biblio re>randomness and OTPs

Response was sufficient to merit posting this (brief
and specific) bibliography pertaining to a) randomness;
b) testing for randomness; and c) compression and
coding as it relates to privacy and maximizing entropy.

The items are listed in the order that *I* think
represents their helpfulness on this topic.

Two interesting quotes from Knuth (book [1] below):

  (sec3.2.2 para2 p25)
  One of the common fallacies encountered in
  connection with random number generation is the idea
  that we can take a good generator and modify it a
  little, in order get and "even-more-random" sequence.
  
  (sect3.3 para4 p38)
  ...The point of these remarks is that we cannot be
  trusted to judge by ourselves whether a sequence of
  numbers is random or not.  Some unbiased mechanical
  tests must be applied.

Books
==========
[1] "The Art of Computer Programming, vol 2:
Seminumerical Algorithms" by Donald Knuth.
ISBN 0-201-03822-6
Sections of interest:
  (3) Random Numbers

[2] "Text Compression" by Bell, Cleary and Witten.
ISBN 0-13-911991-4
Sections of interest:
  (5) From Probablilities to Bits, especially
    (5.2) Arithmetic Coding
  (7.3) Dynamic Markov Modeling
  (10.1.5) Privacy and Compression

[3] "Adaptive Data Compression" by Ross N. Williams.
ISBN 0-7923-9085-7
Sections of interest:
  (1.9) Arithmetic Coding
  (1.10.6.8) DMC
  (1.16) Error Correction, Data Compression and
    Cryptography

[4] "Image and Text Compression" edited by Storer.
ISBN 0-7923-9243-4
Sections of interest:
  (4) 'Practical mplementations of Arithmetic Coding'
    by Howard and Vitter.

Papers
==========
[5] "A note on the DMC data compression scheme" by
  Bell and Moffat.

[6] "Universal Coding, Information, Prediction, and
  Estimation" by Rissanen.

[7] "Linear Time Adaptive Arithmetic Coding" by Moffat.

[8] "A Simple General Binary Source Code" by Langdon
  and Rissanen.

[9] "An overview of the basic principles of the Q-Coder
  adaptive binary arithmetic coder" by Pennebaker, Mitchell,
  Langdon and Arps.

[10] "Software implementations fo the Q-Coder" by Mitchell
  and Pennebaker.

[11] "Optimal hardware and sofware arithmetic coding
  procedures for the Q-Coder" by Mitchell and Pennebaker.

[5] "Probability estimation for the Q-Coder" by Pennebaker
  and Mitchell.

I hope you find this information helpful.

Scott Collins (Scott_Collins@genmagic.com)