Hierarchical guessing with a fidelity criterion

In an earlier paper, we studied the problem of guessing a random vector X w ithin distortion D, and characterized the best attainable exponent E(D, rho ) of the rho th moment of the number of required guesses G(X) until the gue ssing error falls below D. In this correspondence, we extend these results to a multistage, hierarchical guessing model, which allows for a faster sea rch for a codeword vector at the encoder of a rate-distortion codebook. In the two-stage case of this model, if the target distortion level is D-2, th e guesser first makes guesses with respect to (a higher) distortion level D -1, and then, upon his/her first success, directs the subsequent guesses to distortion D-2. As in the above-mentioned earlier paper, we provide a sing le-letter characterization of the best attainable guessing exponent, which relies heavily on well-known results on the successive refinement problem. We also relate this guessing exponent function to the source-coding error e xponent function of the two-step coding process.