Inh.: Dr. Renate Gorre
Fon: +49 (0)7533 97227
Fax: +49 (0)7533 97228
ETH Series in Information Theory and its Applications,
edited by Amos Lapidoth
1st edition 2021. XII, 78 pages, € 64,00.
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 <![if !msEquation]><![if !vml]><![endif]><![endif]> > 0, we characterize the exponential growth rate (as the sequence
length tends to infinity) of the least <![if !msEquation]><![if !vml]><![endif]><![endif]>-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
<![if !msEquation]><![if !vml]><![endif]><![endif]>-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 <![if !msEquation]><![if !vml]><![endif]><![endif]>-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 <![if !msEquation]><![if !vml]><![endif]><![endif]>-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
(0) 7533 97227
http://www.hartung-gorre.de eMail: firstname.lastname@example.org