HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.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
9783866287266
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
informationmeasure 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 ratelimited 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 sumrate 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 twosources
setting.
A guesser seeks to produce an approximate guess that must be close to
the
first sequence as
measured by a given symbolaveraged distortion function.
The guesser is assisted by a helper that reveals a ratelimited
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 changeofmeasure
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 HartungGorre Verlag
Direkt bestellen
bei / to order directly from:
HartungGorre Verlag / D78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227
http://www.hartunggorre.de eMail: verlag@hartunggorre.de