In (Tomamichel 2015), in (1.2) the author mentions the result that a source $X$ with probability distribution $\rho\equiv\rho_X$ admits an $(\varepsilon,m)$-code as long as there is some $\alpha\in[\frac12,1)$ such that $$\log_2 m\ge H_\alpha(X)_\rho + \frac{\alpha}{1-\alpha} \log_2 (1/\varepsilon), \tag1$$ where $$H_\alpha(X)_\rho \equiv \frac{1}{1-\alpha}\log_2\left(\sum_x \rho_X(x)^\alpha\right).$$ Here, an $(\varepsilon,m)$-code for the source is an encoding-decoding scheme that uses $m$ letters and works with average error probability upper bounded by $\varepsilon$.

For comparison, Shannon's result, which can be seen as a special case of this one, states that there is an $(\varepsilon,2^{nR})$-code for the source as long as $R>H(X)$ with $H(X)$ the standard Shannon entropy. This result is relatively easy to understand: one can see that given a source $X$, the probability distribution obtained sampling the source $n$ times is very close to an equiprobable distribution over $2^{nH(X)}$ possible events, hence one needs $H(X)$ bits to characterise it.

Is there any similar kind of intuition/rationale behind (1)? Or a way to guess why such a result should hold, or even just why Renyi entropies (at least the ones with $\alpha\in[1/2,1)$ should have a prominent role to understand compressibility in the non-asymptotic regime?

As mentioned in the paper linked above, this result is attributed Gallager, and they cite in particular (Gallager 1991), and a Gallager 1979 paper which I could only find in this scanned version (it's a link to a pdf). Both are not exactly the most accessible kinds of sources, so I think it would be great to have a more recent discussion about this here. I also feel it worth mentioning that even though this is a question about (completely classical) information theory, I feel like these arguments are maybe discussed more in the quantum information community than in classical community, so it might make sense to have them on this site (rather than on math.SE or stats.SE, which I guess would be the obvious alternatives).



Your Answer

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