Tail exponents of conditional guesswork via the method of types
We study the problem of guessing a realization of an i.i.d. random sequence given element-wise correlated side-information. We use type-counting to provide estimates of the tail probabilities of the number of guesses for the case without side-information, which was shown earlier through large-deviation techniques. We then extend the same counting argument to the conditional setting, obtaining new explicit expressions for the corresponding guesswork exponents as divergences involving conditional tilted distributions. Finally, we provide an application of these exponents to brute-force…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.17949
curl -X POST /api/v1/records/arxiv/2608.17949/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.17949/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'