Stationary memoryless sources produce two correlated random sequences
and
. A guesser seeks to recover
in two stages, by first guessing
and then
. The contributions of this work are twofold: (1) We
[...] Read more.
Stationary memoryless sources produce two correlated random sequences
and
. A guesser seeks to recover
in two stages, by first guessing
and then
. The contributions of this work are twofold: (1) We characterize the least achievable exponential growth rate (in
n) of any positive
-th moment of the total number of guesses when
is obtained by applying a deterministic function
f component-wise to
. We prove that, depending on
f, the least exponential growth rate in the two-stage setup is lower than when guessing
directly. We further propose a simple Huffman code-based construction of a function
f that is a viable candidate for the minimization of the least exponential growth rate in the two-stage guessing setup. (2) We characterize the least achievable exponential growth rate of the
-th moment of the total number of guesses required to recover
when Stage 1 need not end with a correct guess of
and without assumptions on the stationary memoryless sources producing
and
.
Full article