Universal Random Number Generation from Finite Memory Sources
Tuesday, December 2, 2014
11:30 am - 12:30 pm
Gross Hall 330
Dr. Gadiel Seroussi, MSRI
lunch served following talk Procedures for transforming non-uniform random sources into ¿perfectly random¿ ones have been a subject of great interest in statistics, information theory, and computer science for decades. Various assumptions on the nature of the input process, what is known about it, and how the samples are accessed, give raise to different settings for the problem. In this talk, we study this problem, both in the fixed-to-variable (FV) and variable-to-fixed (VF) length regimes, in a universal setting in which the input is a finite memory source of arbitrary order and unknown parameters. We apply the method of types to characterize (essentially unique) pointwise optimal universal random number generators that maximize the expected output (respectively, minimize the expected input) length in the FV (respectively, VF) regime. 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 simulation. In the FV case, our analysis amounts to showing that, when studied explicitly in the context of the method of types, the original optimal Elias scheme is applicable, almost verbatim, to broader classes of processes than originally designed for, and is amenable to a very precise analysis. In the VF case, the optimal scheme we describe is new, can be regarded as a counterpart to the Elias scheme, and admits an efficient sequential implementation.