Abstract :
We study random number generators (RNGs), both in the fixed to variable-length (FVR) and the variable to fixed-length (VFR) regimes, in a universal setting in which the input is a finite memory source of arbitrary order and unknown parameters, with arbitrary input and output (finite) alphabet sizes. Applying the method of types, we characterize essentially unique optimal universal RNGs that maximize the expected output (respectively, minimize the expected input) length in the FVR (respectively, VFR) case. For the FVR case, the RNG studied is a generalization of Elias´s scheme, while in the VFR case the general scheme is new. We precisely characterize, up to an additive constant, the corresponding expected lengths, which include second-order terms similar to those encountered in universal data compression and universal simulation. Furthermore, in the FVR case, we consider also a twice-universal setting, in which the Markov order k of the input source is also unknown.
Keywords :
data compression; random number generation; Elias scheme; FVR regime; Markov order; RNG; VFR regime; additive constant; alphabet size; finite memory source; fixed-to-variable-length regime; optimal algorithm; universal data compression; universal random number generation; universal simulation; variable-to-fixed-length regime; Additives; Convergence; Dictionaries; Entropy; Indexes; Information theory; Markov processes; Markov sources; Random number generation; finite memory processes; fixed to variable-length; method of types; optimal algorithms; type classes; universal generators; variable to fixed-length;
