On Two-Stage Guessing
share
Stationary memoryless sources produce two correlated random sequences X^n and Y^n. A guesser seeks to recover X^n in two stages, by first guessing Y^n and then X^n. 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 Y^n is obtained by applying a deterministic function f component-wise to X^n. We prove that, depending on f, the least exponential growth rate in the two-stage setup is lower than when guessing X^n 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 X^n when Stage 1 need not end with a correct guess of Y^n and without assumptions on the stationary memoryless sources producing X^n and Y^n.
READ FULL TEXT