<p>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$.</p>

<p>This is part of the reason why people went on to examine Renyi entropies.</p>

CC BY-SA 3.0
2012-10-12T02:19:28.460Z
2012-10-12T02:19:28.460Z
kodlu
<p>Bob's best bet is to guess the $t$ values with largest probability.</p>

<p>If you're willing to use Rényi entropy instead, Proposition 17 in Boztaş' <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.8601">Entropies, Guessing and Cryptography</a> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-10-10T21:22:17.483Z
Thanks for the answer! I tried the optimization approach you suggest, but could not get good estimates.
Or Meir
CC BY-SA 3.0
2012-10-11T01:33:37.990Z
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!
Or Meir
CC BY-SA 3.0
2012-10-10T21:18:52.663Z
2012-10-10T21:18:52.663Z
Yuval Filmus
<p>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$.</p>

<p>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}$.</p>

<p>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 <em>failure</em> probability decreases exponentially with $t$?</p>

<it.information-theory><pr.probability>
Guessing a low entropy value in multiple attempts
Or Meir
# Guessing a low entropy value in multiple attempts

(Asked by: username_0 on 2012-10-10)

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$?

**Tags:** it.information-theory, pr.probability

---

## 2 answers

### Answer by username_2 on 2012-10-10. Score: 10 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.8601) 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.

> **Comments:**
> **username_0**: Thanks for the answer! I tried the optimization approach you suggest, but could not get good estimates.  
> **username_0**: 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!  

---

### Answer by username_1 on 2012-10-12. Score: 8

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.


---

