Universal random number generators for finite memory sources

Dr. Marcelo Weinberger
Distinguished Scientist, Center for Science of Information
Date: Nov. 8th, 2013

Abstract

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. In this talk, we study this problem in a universal setting, in which the input is a finite memory source of arbitrary order and unknown parameters, both in the fixed-to-variable (FV) and variable-to-fixed (VF) length regime. After presenting the problem in a common framework of universal schemes for tasks such as data compression and simulation, we use the method of types to characterize (essentially unique) optimal universal random number generators which maximize the expected output (respectively, minimize the expected input) length, in the FV (respectively, VF) length regime. We precisely characterize, up to an additive constant, the corresponding expected output (respectively, input) lengths, which include model cost terms similar to those encountered in universal data compression and universal simulation. Finally, we consider a "twice-universal" setting, in which the Markov order of the input source is also unknown.

(Based on joint work with Gadiel Seroussi.)

Bio

Marcelo Weinberger is a Distinguished Scientist with the Center for Science of Information, currently residing in ISL at Stanford University. Earlier this year Marcelo retired from Hewlett-Packard Laboratories, Palo Alto, CA, where he also was a Distinguished Scientist and lead the Information Theory Research group. Prior to that, he was a Visiting Scientist at IBM Almaden Research Center, San Jose, CA, and a faculty at the Department of Electrical Engineering at Technion—Israel Institute of Technology, Haifa, Israel, for the 1991–1992 academic year. Marcelo received the Electrical Engineer degree from the Universidad de la República, Montevideo, Uruguay, and the M.Sc. and D.Sc. degrees from Technion, both in electrical engineering. His research interests include source coding, sequential decision problems, statistical modeling, and image compression. Marcelo is a coauthor of the algorithm at the core of the JPEG-LS lossless image compression standard, and was an editor of the standard specification. He also contributed to the coding algorithm of the JPEG2000 image compression standard. He is a Fellow of the IEEE and a co-recipient of the 2006 IEEE Communications/Information Theory Societies Joint Paper Award (for the "DUDE" algorithm).