Universal random number generation from finite memory sources
Mon, Oct. 26
400 Cory
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. After presenting the problem in a common framework of universal schemes for tasks such as data compression and simulation, we apply the method of types to characterize (essentially unique) optimal universal random number generators that maximize the expected output (respectively, minimize the expected input) length in the FV (respectively, VF) length case. 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. 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 at UC Berkeley. Marcelo retired in 2013 from Hewlett-Packard Laboratories, Palo Alto, CA, where he also was a Distinguished Scientist and led 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).
UC Berkeley Networking
Ashwin Pananjady and Orhan Ocal
Last Modification Date: Wednesday, February 10, 2016