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!
The utility of Renyi entropies?
it.information theory;quantum information
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 attemptsSome references:J. O. Pliam, On the Incomparability of Entropy and Marginal Guesswork in Brute-Force Attacks. INDOCRYPT 2000: 67-79E. Arikan, An inequality on guessing and its application to sequential decoding. IEEE Transactions on Information Theory 42(1): 99-105,1996.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.