Tail exponents of conditional guesswork via the method of types

Adway Girish, Andreina Patrizia Motter, Emre Telatar

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 pr…