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.
翻译:将这一结果应用到 i.d.~来源,可以证明随机化的战略可以无缘无故地达到最佳的猜测时刻。此外,还提出了一个随机化的猜测计划,即使在区块大小极大的情况下也是可行的,并获得了对拟议办法可实现的猜测时刻的单字母描述。