9
$\begingroup$

Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice draws a value $x$ from $\mu$, and then asks Bob (who knows $\mu$) to guess $x$.

What is the success probability for Bob? If he is only allowed one guess, then one can lower bound this probability as follows: the entropy upper bounds the min-entropy, so there is an element that has probability of at least $2^{-\varepsilon}$. If Bob chooses this element as his guess, his success probability will be $2^{-\varepsilon}$.

Now, suppose that Bob is allowed to make multiple guesses, say $t$ guesses, and Bob wins if one of his guesses is correct. Is there a guessing scheme that improves Bob's success probability? In particular, is it possible to show that Bob's failure probability decreases exponentially with $t$?

$\endgroup$
10
$\begingroup$

Bob's best bet is to guess the $t$ values with largest probability.

If you're willing to use Rényi entropy instead, Proposition 17 in Boztaş' Entropies, Guessing and Cryptography states that the error probability after $t$ guesses is at most $$ 1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu), $$ where $n$ is the size of the domain. Granted, the dependency on $t$ is pretty bad, and perhaps Boztaş was focused on a different regime of the entropy.

For the Shannon entropy, you can try to solve the dual optimization problem: given a fixed failure probability $\delta$, find the maximal entropy of such a distribution. Using the convexity of $-x\log x$, we know that the distribution $\mu$ has the form $a,b,\ldots,b;b,\ldots,b,c$, where $a\geq b\geq c$, $a+(t-1)b = 1-\delta$, and $c = \delta-\lfloor\frac{\delta}{b}\rfloor b$. We have $t-1+\lfloor\frac{\delta}{b}\rfloor$ values that get probability $b$. Conditioning on $s = \lfloor\frac{\delta}{b}\rfloor$, we can try to find $b$ which minimizes the entropy. For the correct value of $s$, this will be an internal point (at which the derivative vanishes). I'm not sure how to get asymptotic estimates using this approach.

$\endgroup$
  • $\begingroup$ Thanks for the answer! I tried the optimization approach you suggest, but could not get good estimates. $\endgroup$ – Or Meir Oct 10 '12 at 21:22
  • $\begingroup$ Hi Yuval, after some more work, it seems that this optimization approach yields the solution. Unfortunately, in this case too, the error decreases only inverse-logarithmically in the number of guesses. Thanks! $\endgroup$ – Or Meir Oct 11 '12 at 1:33
7
$\begingroup$

Unfortunately there is no good answer to your question. John Pliam [PhD Thesis, 2 papers in the LNCS series] was the first to observe the disparity between Shannon entropy and expected number of guesses. His thesis is easy to find online. In section 4.3, by choosing a suitable probability distribution for $X$ (dependent on an arbitrary positive integer $N$) which comes from self-similar huffman trees he demonstrates that by guessing in decreasing order of probability, one must make more than $N+H(X)$ guesses before the probability of success reaches $1/2$.

This is part of the reason why people went on to examine Renyi entropies.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.