4
$\begingroup$

Some general discussion of smoothed entropic quantities is found for example in Watrous notes, and an overview and discussion on its operational interpretations in (Koenig et al. 2008). It seems the quantity was introduced in (Renner and Wolf 2004), and lots of related in-depth discussion is also found in Renato Renner's PhD thesis.

I didn't, however, find explicit examples where smoothed entropic quantities are calculated. Methods to calculate such quantities are discussed, in the form of conic programming, and these are fine for numerical purposes. However, is there any simple example, classical or quantum (ideally both), where we can compute a smoothed entropic quantity analytically?

Some worked out examples for smoothed min(max) entropies can be found in this math.SE post. Here, I'm looking for explicit, toy or not, classical or (but possibly and) quantum, examples where we can compute analytically smoothed conditional min(max) entropies.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

I'll just give a classical example, which is a typical motivating example for these smooth quantities. Consider an $n$-bit distribution of the form $$ p(x) = \begin{cases} 1-\delta \qquad \text{ if }x=0 \\ \frac{\delta}{2^n -1} \qquad \text{ otherwise} \end{cases} \,, $$ for some $\delta \in (0, 1/2]$. This distribution is sometimes called the "L distribution" as its histogram has a large weight on the first component then is very small and flat on the rest of the possible outcomes.

This distribution is also typically used to demonstrate the difference between the Shannon entropy and the min-entropy. For the distribution $p(x)$ its Shannon entropy can be calculated as $$ H[p] = h(\epsilon) + \epsilon \log(2^n -1) $$ where $h(\delta)= -\delta \log \delta - (1-\delta)\log(1-\delta)$ is the binary entropy. The min-entropy is given by $$ H_{\min}[p] = -\log(1-\delta) $$ Now we see that the Shannon entropy grows with $n$ whereas $H_{\min}$ does not, this demonstrates that $H_{\min}$ and $H$ can be arbitrarily different. We can also compute $$H_{\max}[p] = n$$ which if we tune $\epsilon$ we can also make arbitrarily different from $H$.

Let's turn to the smoothed counterparts. For the min-entropy the optimal smoothing is to shorten the tall peak as much as possible. That is, (provided $n$ is large enough and $\epsilon$ is small enough) for the $\epsilon$ smoothing we take $\epsilon/2$ from the large peak and add it to other outputs, for instance we get a new distribution $$ q(x) = \begin{cases} 1-\delta - \frac{\epsilon}{2} \qquad \text{ if }x=0 \\ \frac{\delta + \frac{\epsilon}{2}}{2^n -1} \qquad \text{ otherwise} \end{cases} \,, $$ such that $\|p-q\| = \epsilon$ and gives a smooth min-entropy of \begin{equation} H_{\min}^\epsilon[p] = H_{\min}[q] = -\log(1-\delta - \tfrac{\epsilon}{2})\,. \end{equation} which is not too different from the original min-entropy. However, we see a large difference for the smooth max entropy. The optimal smoothing for the max entropy is to force as many outcomes to have $0$ probability as possible and add the weight to the outcome $x=0$. To this end we find a smoothing distribution $$ r(x) = \begin{cases} 1-\delta + \frac{\delta}{2^n -1}\lfloor\frac{(2^{n}-1)\epsilon}{2\delta}\rfloor \qquad &\text{ if }x=0 \\ \frac{\delta}{2^n -1} \qquad &\text{ for }2^n-1-\lfloor\frac{(2^{n}-1)\epsilon}{2\delta}\rfloor \text{ choices of bitstrings } \\ 0 \qquad &\text{ for all $\lfloor\frac{(2^{n}-1)\epsilon}{2\delta}\rfloor$ remaining bitstrings } \end{cases} \,, $$ which gives a smooth max entropy of $$ H^\epsilon_{\max}[p] = H_{\max}[r] = \log(2^n - \lfloor\frac{(2^{n}-1)\epsilon}{2\delta}\rfloor) $$ which if $\epsilon$ is of a similar size to $\delta$ gives a huge decrease from the max-entropy.

The power of smoothing Part of the power of smoothing also comes from when we look at multiple copies of the distribution. Suppose instead of just looking at a single copy of our random variable $X$ we look at $m$ IID copies of $X$ (denoted $X^m$). Then for $m$ large enough the asympototic equipartition property (we can extend this to non-iid settings as well) tells us that $$ H_{\min}^\epsilon(X^m) \approx m H(X) \approx H_{\max}^\epsilon(X^m)\,. $$ In other words, if we allow ourselves to smooth a little, then when we take many copies our smoothing min/max entropies converge to the Shannon entropy. This is in contrast with the non-smoothed versions which in this case evaluate to $$ H_{\min}(X^m) = m H_{min}(X) $$ and $$ H_{\max}(X^m) = m H_{\max}(X) $$ which can be quite different from $mH(X)$ as we've seen above. Note that such a result is for instance useful in cryptography when we want to assess how many random bits we can extract from many copies of $X$. If we use the min-entropy we get a randomness generation rate of $H_{\min}(X)$ but if we use the smoothed version we get, for a large enough number of copies, a randomness generation rate of $H(X)$ which can be significantly better!

$\endgroup$
3
  • $\begingroup$ I think I edited the question to focus it on the conditional smooth entropies in particular just before you sent your answer, sorry about that. Do you have a good example for that as well, by any chance? If not, I'll revert the question to the previous version, where I was also asking about smoothed min(max) entropies $\endgroup$
    – glS
    Commented Sep 5, 2022 at 19:50
  • $\begingroup$ No worries. Probably the above example can be modified. I'll have a think later. $\endgroup$
    – Rammus
    Commented Sep 6, 2022 at 7:44
  • $\begingroup$ should $\epsilon$ possibly be a $\delta$ in the second equation? $\endgroup$
    – glS
    Commented Sep 19, 2022 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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