The utility of Renyi entropies?

Question

Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic measures such as relative entropy, mutual information, and so on. There are a few other measures of entropy that are commonly used in theoretical computer science and information theory, such as the min-entropy of a random variable.

I've started seeing these so-called Renyi entropies more often as I browse the literature. They generalize the Shannon entropy and the min-entropy, and in fact provide a whole spectrum of entropic measures of a random variable. I work mostly in the area of quantum information, where the quantum version of Renyi entropy is also considered quite often.

What I don't really understand is why they are useful. I've heard that oftentimes they're easier to work with analytically than say Shannon/von Neumann entropy or min-entropy. But they also can be related back to Shannon entropy/min-entropy, as well.

Can anyone provide examples (classical or quantum) of when using Renyi entropies is "the right thing to do"? What I'm looking for is some "mental hook" or "template" for knowing when I might want to use Renyi entropies.

Thanks!

Answer 1

Consider trying to make atomic guesses for an unknown random variable $X$ distributed over some finite set $A.$ In Shannon entropy, it is assumed that you can query bit by bit, i.e., if $A=\{1,\ldots,N\}$ you can ask:

Is $X\in \{1,\ldots,N/2\}$ ? (assume $N$ even or use floor/ceiling functions)

In crypto and some decoding scenarios this is not realistic. Trying to guess an unknown pasword you need to make atomic queries, i.e. query if $X$ is a specific value.

It turns out that the expected number of queries to guess a random variable $X$ then depends tightly on the Renyi entropy of order $1/2.$ So do some higher moments. For example

$$E[G]\leq \frac{(\sum_{x \in A} P_X(x)^{1/2})^2}{2}$$

and the numerator is essentially the logarithm of Renyi entropy of order $1/2.$ One can also make Shannon entropy very large while Renyi entropy and expectation of the number of guesses is very small. If you relied on Shannon entropy for security you'd be in trouble in that case.

Please also see the related question Guessing a low entropy value in multiple attempts

Some references:

1. J. O. Pliam, On the Incomparability of Entropy and Marginal Guesswork in Brute-Force Attacks. INDOCRYPT 2000: 67-79
2. E. Arikan, An inequality on guessing and its application to sequential decoding. IEEE Transactions on Information Theory 42(1): 99-105,1996.
3. S. Boztas, On Renyi entropies and their applications to guessing attacks in cryptography, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 97(12):2542-2548, 2014.

Answer 2

Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful.

Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single number that represents, in some sense, how does the typical element of $a$ look like.

One way to do so is to take the average of the numbers in $a$, which roughly corresponds to the $\ell_1$ norm: $\mathbb{E}_{1 \le i \le n}[|a_i|]$. This is often useful, but for some applications it has the following problems: First, the $\ell_1$ norm does not give us a good upper bound on the largest element of $a$, because if there is a single large element and many zeroes, the $\ell_1$ norm will be significantly smaller than the largest element. On the other hand, the $\ell_1$ norm also does not give us a good bound on how small the elements of $a$ are, for example, how many zeroes $a$ has - this problem occurs in exactly the same scenario as before.

Of course, when the elements of $a$ have a lot of variance, such as in the extreme scenario as above, no single number can give solve both problems above. We have a tradeoff. For example, if we only want to know the largest element, we can use the $\ell_\infty$ norm, but then we will lose all information about the smaller elements. If we want the number of zeroes, we can look at the $\ell_0$ norm, which is just the size of the support of $a$.

Now, the reason for considering $\ell_p$ norms is that they give us the whole continuous tradeoff between the two extremes. If we want more information on the large elements we take $p$ to be larger, and vice versa.

Same goes for Renyi entropies: Shanon's entropy is like $\ell_1$ norm - it tells us something about the "typical" probability of an element, but nothing about the variance or the extremes. The min-entropy gives us information on the element with the largest probability, but loses all information about the rest. The support size gives the other extreme. The Renyi entropies give us a continuous tradeoff between the two extremes.

For example, many times the Renyi-2 entropy is useful because it is on the one hand close to Shanon's entropy, and thus contains information on all the elements on the distribution, and on the other hand gives more information on the elements with the largest probability. In particular, it is known that bounds on the Renyi-2 entropy gives bounds on the min-entropy, see, e.g., Appendix A here: http://people.seas.harvard.edu/~salil/research/conductors-prelim.ps

Answer 3

Renyi entropy (of order 2) is useful in cryptography for analyzing the probability of collisions.

Recall that the Renyi entropy of order 2 of a random variable $X$ is given by

$$H_2(X) = - \log_2 \sum_x \Pr[X=x]^2.$$

It turns out that $H_2(X)$ lets us measure of the probability that two values drawn i.i.d. according to the distribution of $X$ happen to be the same ("collide"): this probability is exactly $2^{-H_2(X)}$. After drawing $n$ times from this distribution, the expected number of collisions among these $n$ draws is $C(n,2) 2^{-H_2(X)}$.

These facts are useful in cryptography, where collisions can sometimes be problematic and enable attacks.

For some analysis of other uses in cryptography, I recommend the following PhD dissertation:

Christian Cachin. Entropy Measures and Unconditional Security in Cryptography. PhD dissertation, ETH Zurich, May 1997.

Answer 4

This other stackexchange answer and this blog post might be very helpful to get a quick feel of a basic example,

• https://physics.stackexchange.com/questions/73424/deriving-entanglement-entropy-from-renyi-entropy

• https://johncarlosbaez.wordpress.com/2011/02/10/rnyi-entropy-and-free-energy/

Roughly speaking Renyi entropies know about the excited states of a quantum system but the entanglement entropy knows about the ground states. WARNING: This intuition could be terribly crude but might just be a good "mental hook" :D I would be VERY happy to know of a better and precise way to say this!

One can think of calculating the entanglement entropy $S_1$ (which is a more physical quantity) as the singular limit of calculating the Renyi entropies ($S_q$ for each $q \in \mathbb{Z}^+$). But this limit $S_1 = limit_{q \rightarrow 1} S_q$ is terribly badly defined. So often the idea is that one can calculate $S_q$ at an arbitrary integer value and then do an analytic continuation of that to $q \in \mathbb{R}$ and then try to define taking of the $ q \rightarrow 1$ limit. (though always $q \in \mathbb{R}$, this I call "analytic" continuation because often enough one needs to do the interpolation via contours in the complex plane - and the continuation can depend on what contours one chooses through the poles and branch-cuts of the $S_q$ that one started with)

At integral values of $q>1$ typically there is a always a very well-defined construction in terms of some integration of some function on some $q-$branched manifold. After one has done such an integration one happily forgets about the manifold used and just tries to do the analytic continuation parametrically in the variable $q$.

There are always a lot of issues about existence and well-posedness when one tries to do these anayltic continuations - but for someone like me who is brought up on a daily diet of Feynman path-integrals its a very common issue to deal with and we have a lot of tools to address these. Three nice papers to look into for these issues are, http://arxiv.org/pdf/1306.5242.pdf, http://arxiv.org/pdf/1402.5396.pdf, http://arxiv.org/pdf/1303.7221.pdf (the last of these papers might be an easier starting point) This presentation might also help, https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf

What Renyi entropy says in terms of quantum complexity theory might be an exciting question! Can one think of the Renyi index as somehow parameterizing a hierarchy of complexity classes? That should be fun if true! Do let me know :)

Answer 5

Renyi entropy has found its way into definitions of quantitative information flow, an area or security research. See G. Smith's survey paper.