05-07-2012, 09:59 AM
Source Codes as Random Number Generators
Source Codes as Random Number Generators.pdf (Size: 441.97 KB / Downloads: 28)
Abstract
A random number generator generates fair coin flips by
processing deterministically an arbitrary source of nonideal
randomness. An optimal random number generator generates
asymptotically fair coin flips from a stationary ergodic source at a
rate of bits per source symbol equal to the entropy rate of the source.
Since optimal noiseless data compression codes produce
incompressible outputs, it is natural to investigate their capabili- ties
as optimal random number generators. In this paper we show under
general conditions that optimal variable-length source codes
asymptotically achieve optimal variable-length random bit
generation in a rather strong sense. In particular, we show in what
sense the Lempel-Ziv algorithm can be considered an optimal
universal random bit generator from arbitrary stationary ergodic
random sources with unknown distributions.
Index Terms— Data compression, entropy, Lempel-Ziv algorithm,
random number generation, universal source coding.
I. INTRODUCTION
Here we explore the possibility of using source codes as
random number generators. The rationale is that an incompressible
sequence must be random in some sense and thus an
optimal source code (which eliminates all redundancy) must
output a "random" sequence. The problem of generating ran- dom
bits has been studied in two settings: variable-length and fixedlength,
according to whether the number of random bits generated
depends on the source realization or not. This paper focuses on the
variable-length setting, as our main interest is in constructive
methods for random number generation, and in particular, in
universal methods. The Lempel-Ziv algorithm has been shown in
[14] to be optimal in a certain sense to test whether or not a
source generates independent equiprobable bits. However, the
problem of investigating how far from being truly random is the
output of a Lempel-Ziv algorithm (and other optimal source
codes) appears to be new.
In the variable-length setting the "ideal" definition of ran-
I N contrast to pseudorandom number generators which
produce zero entropy rate sequences, a random number
domness would be that, conditioned on the length of the output
binary sequence being , all the -length binary sequences
generator is a deterministic procedure to generate equiprobable occur with probability The rate at which a variable-length
independent bits from a random source The problem generator produces random bits is the expected length of the
was initially addressed by von Neumann in [12] where the binary output string per source symbol. However, we cannot
source was a Bernoulli source with More go very far with such a strict requirement of randomness.
efficient algorithms for generating random bits from a biased Consider the simplest nontrivial setting: a memoryless source
coin were given by Hoeffding and Simons [6], Stout and
Warren [9], and Peres [7]. Elias [4] showed that the entropy and
with alphabet such that
The Huffman code for this source assigns
rate is an upper bound for the rate at which it is possible the strings , , to respectively. Thus a string of
to generate random bits from stationary sources and found source symbols is mapped to a string of bits, where ranges
an optimal random number generator from stationary finite- from to The rate of bit generation is equal to the source
state, finite-order Markov sources without making use of the
Markov source distribution (other than its order). A simple
algorithm to generate arbitrary distributions from a biased coin
with a known distribution was given by Han and Hoshi [5]. The
practically important problem of constructing a universal random
number generator from arbitrary nonideal stationary
entropy (1.5 b/symbol). All generated bit strings of length
are equiprobable; however, the Huffman code generates only