  The problem of guessing subject to distortion is considered, and the
performance of randomized guessing strategies is investigated. A one-shot
achievability bound on the guessing moment (i.e., moment of the number of
required queries) is given. Applying this result to i.i.d.~sources, it is shown
that randomized strategies can asymptotically attain the optimal guessing
moment. Further, a randomized guessing scheme which is feasible even when the
block size is extremely large is proposed, and a single-letter characterization
of the guessing moment achievable by the proposed scheme is obtained.
