We investigate the problem of guessing a random vector X within distortion level D. Our aim is to characterize the best attainable performance in the sense of minimizing, in some probabilistic sense, the number of required guesses G(X) until the error falls below D. The underlying motivation is that G(X) is the number of candidate code words to be examined by a rate-distortion block encoder until a satisfactory code word is found. In particular, for memoryless sources, we provide a single-letter characterization of the least achievable exponential growth rate of the pth moment of G(X) as the dimension of the random vector X grows without bound. In this context, we propose an asymptotically optimal guessing scheme that is universal both w.r.t the information source and the value of p. We then study some properties of the exponent functuion E(D,p) along with its relation to the source coding error exponent. Finally, we provide extensions of our main results to the Gaussian case, guessing with side information, and nonmemoryless sources.
PDF
download
878987797
028-85220240
