Graduate School and Research Center in Digital Sciences

Seminar: Informational Random Number Generation: A Converse

Georg Böcherer (Technical University of Munich) - Dr

Communication systems

Date: May 2, 2013

Abstract: Given is a stream of random bits and a target distribution over a set of symbols. An encoder maps the random bit stream to a stream of symbols. The encoder is subject to the constraint that the distribution of the output should approximate the target distribution. The rate of the encoder is the average input length divided by the average output length. Two scenarios are of interest. First, the encoder can use a random mapping, but we want to recover the input from the output. In this situation, we want to maximize the rate. Second, the encoder is restricted to be deterministic, but we do not need to recover the input from the output. In this situation, we want to minimize the rate. We show that for arbitrarily good approximation of the target distribution, the rate has to be slightly smaller (respectively larger) than the entropy of the target distribution. As a measure of approximation, we use normalized informational divergence. This implies that our converse directly applies to un-normalized informational divergence and exact generation. Relation to existing work is discussed and open problems are stated. Biography: Georg Böcherer obtained his MSc degree in Electrical Engineering and Information Technology from the ETH Zürich. He spend one semester at the EPF Lausanne and wrote his master thesis at the Federal University of Pernambuco in Recife, Brazil. From 2007 to 2012 he worked towards his Phd degree at the Institute of Theoretical Information Technology at RWTH Aachen University. Since April 2012, he is with the Institute for Communications Engineering at Technische Universität München. His research interest are information theory, communications, and coding.

Génération de nombres aléatoires: Le point de vue de la théorie de l'information

Informational Random Number Generation: A Converse