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. 11
edited by Amos Lapidoth

Robert Graczyk

Guess What?

1^st edition 2021. XII, 78 pages, € 64,00.

ISBN 978-3-86628-726-6

Abstract

The problem of guessing a chance variable (guessing problem for short) has

seen applications in the context of cryptography, information measures, and

data transmission. In this thesis, we introduce and solve four extensions of

the guessing problem. Each extension is solved by a different, novel method

that can be applied to a broad class of guessing problems.

The first extension consists of a setting where two correlated memoryless

sources each generate a sequence. A guesser seeks to only guess the first sequence,

but, prior to guessing it, is allowed to produce guesses of the second.

Given some > 0, we characterize the exponential growth rate (as the sequence

length tends to infinity) of the least -th moment of the number of

guesses taken until the realization of the first sequence is known. We exhibit

an asymptotically optimal guessing strategy which is a mixture of guessing

strategies that either ignore the first sequence or guess it. We also offer an

information-measure interpretation of our result.

The second extension is similar to the first, but with k sources instead

of two, and with the guesser seeking to guess every sequence. Unlike in the

first extension, the guesser is not required to guess some sequences before

others, and is assisted by a rate-limited helper that describes the sequences

prior to guessing. We characterize the exponential growth rate of the least

-th moment of the number of guesses taken until all sequences are known.

Our argument can be decomposed into two parts: first, a reduction of the

guessing strategy to a data compression scheme that satisfies a number of

desired properties; and second, using these properties in the construction of

an asymptotically optimal guessing strategy.

The third extension consists of two sources and two guessers: Guesser 1

seeks to guess the first sequence, and Guesser 2 the second. Prior to guessing,

an encoder observes both sequences and produces three descriptions; the first

two are revealed to Guesser 1, and the second two are revealed to Guesser 2

(each guesser is therefore revealed a common and a private description.) We

characterize the set of all rate triples that allow the encoder to describe the

sequences such that, for each guesser, the least -th moment of the number of

guesses does not exceed a given exponential. Building on our characterization

of these rates, we follow Wyner’s approach and propose to define the Rényi

Common Information as the least common description rate (of the message

revealed to both guessers) under the constraint that the sum-rate be minimal.

We characterize this quantity and show that it generalizes Wyner’s Common

Information just as other Rényi information measures generalize Shannon’s.

In the fourth and final extension, we again consider a two-sources setting.

A guesser seeks to produce an approximate guess that must be close to the

first sequence as measured by a given symbol-averaged distortion function.

The guesser is assisted by a helper that reveals a rate-limited description of

the second sequence prior to guessing. We characterize the exponential growth

rate of the least -th moment of the number of guesses taken until a valid

approximation is produced. Our argument is based on a change-of-measure

trick: Instead of working with the true probability measure, we construct a

new one under which a previously constructed guessing strategy is shown to

be asymptotically optimal.

Keywords: guessing, information measures, operational definitions, secrecy,

Shannon and Rényi entropy, Rényi's common information, compression,

information inequalities, change of measure.

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
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de