Hartung-Gorre Verlag Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de

S

ETH Series in Information Theory and its Applications, Vol. 10
edited by Amos Lapidoth

Christoph Pfister

On Rényi Information Measures

and Their Applications

1^st edition 2020. X, 174 pages, € 64,00.

ISBN 978-3-86628-663-4

Abstract

The solutions to many problems in information theory can be expressed using Shannon’s information measures such as entropy, relative entropy, and mutual information. Other problems—for example source coding with exponential cost functions, guessing, and task encoding—require Rényi’s information measures, which generalize Shannon’s.

The contributions of this thesis are as follows: new problems related to guessing, task encoding, hypothesis testing, and horse betting are solved; and two new Rényi measures of dependence and a new conditional Rényi divergence appearing in these problems are analyzed.

The two closely related families of Rényi measures of dependence are studied in detail, and it is shown that they share many properties with Shannon’s mutual information, but the data-processing inequality is only satisfied by one of them. The dependence measures are based on the Rényi divergence and the relative α-entropy, respectively.

The new conditional Rényi divergence is compared with the conditional Rényi divergences that appear in the definitions of the dependence measures by Csiszár and Sibson, and the properties of all three are studied with emphasis on their behavior under data processing. In the same way that Csiszár’s and Sibson’s conditional divergence lead to the respective dependence measures, so does the new conditional divergence lead to the first of the new Rényi dependence measures. Moreover, the new conditional divergence is also related to Arimoto’s measures.

The first solved problem is about guessing with distributed encoders: Two dependent sequences are described separately and, based on their descriptions, have to be determined by a guesser. The description rates are characterized for which the expected number of guesses until correct (or, more generally, its ρ-th moment for some positive ρ) can be driven to one as the length of the sequences tends to infinity. The characterization involves the Rényi entropy and the Arimoto–Rényi conditional entropy.

The related second problem is about distributed task encoding: Two dependent sequences are described separately, and a decoder produces a list of all the sequence pairs that share the given descriptions. The description rates are characterized for which the expected size of this list (or, more generally, its ρ-th moment for some positive ρ) can be driven to one as the length of the sequences tends to infinity. The characterization involves the Rényi entropy and the second of the new Rényi dependence measures.

The third problem is about a hypothesis testing setup where the observation consists of independent and identically distributed samples from either a known joint probability distribution or an unknown product distribution. The achievable error-exponent pairs are established and the Fenchel biconjugate of the error-exponent function is related to the first of the new Rényi dependence measures. Moreover, an example is provided where the error-exponent function is not convex and thus not equal to its Fenchel biconjugate.

The fourth problem is about horse betting, where, instead of Kelly’s expected log-wealth criterion, a more general family of power-mean utility functions is considered. The key role in the analysis is played by the Rényi divergence, and the setting where the gambler has access to side information motivates the new conditional Rényi divergence. The proposed family of utility functions in the context of gambling with side information also provides another operational meaning to the first of the new Rényi dependence measures. Finally, a universal strategy for independent and identically distributed races is presented that asymptotically maximizes the gambler’s utility function without knowing the winning probabilities or the parameter of the utility function.

Keywords: guessing, task encoding, hypothesis testing, horse betting, Shannon’s information measures, Rényi’s information measures, new conditional Rényi divergence, dependence measures by Csiszár and Sibson, Rényi entropy, Arimoto–Rényi conditional entropy.

Reihe "ETH Series in Information Theory and its Applications" im Hartung-Gorre Verlag

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de