MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Heuristic Background

Consider a set of states labeled $n=1,2,...$ in order of non-increasing probability $p(n)$. The standard Shannon argument gives meaning to the entropy $S$ of $p$ in terms of the number of states needed to encode the distribution with small error in the limit of many iid copies.

Roughly speaking I want to know how badly this can fail in the one-shot setting. My primary motivation is to understand how non-trivial it is to be able to show that $e^S$ states suffice to give small error for a given probability distribution. The distributions I have in mind have a system size-like parameter (like the number of iid copies) but the "copies" are correlated in a complicated way.

Given the subject matter this may be a very elementary question, but I cannot seem to find much information on it.


Fix a large number $S$. Let $p$ be a probability distribution with $p(n) \geq p(n+1)$ and entropy $S$, and let $p_S$ be the probability truncated to its first $e^S$ states i.e. $p_S(n \leq e^S) = p(n)$ and $p_S(n > e^S) = 0$. Is there a bound on the error $||p - p_S ||_1$ (varying $p$ with fixed $S$) or can I make this as close to one as I want?


share|cite|improve this question
Do you want to renormalize $p_S$ to be a probability, or not? – Mark Meckes Jun 19 '12 at 15:23
up vote 1 down vote accepted

I was able to answer my own question with a little help from my fellow physicists :)

Similar result for Renyi entropy

I stumbled upon a weaker version of this result before finding Lemma 2 of which also gives a simple proof using majorization.

Let $p_\chi$ denote the probability distribution truncated to its $\chi$ largest values (see above), and let the error be $\epsilon = ||p-p_\chi||_1$.

"Lemma 2": If $S_\alpha = \frac{1}{1-\alpha} \ln{\left(\sum_n (p(n))^\alpha\right)}$ is the Renyi entropy then we have $ \ln{(\epsilon)} \leq \frac{\alpha}{1-\alpha} \left(S_\alpha - \ln{\left(\frac{\chi}{1-\alpha}\right)}\right)$ for $\alpha <1$.

This gives a partial answer to my question in that keeping roughly $e^{S_\alpha}$ states for $\alpha <1$ is guaranteed to lead to small error.

Case of $\alpha =1$

This leaves open the question of $\alpha=1$. I came up with a trivial and very pathological counterexample showing that no simple theorem of the type I was asking about can exist.

Consider a probability distribution over $n$-bit strings given by $p(0...0) = p + \frac{1-p}{2^n}$ and $p(other) = \frac{1-p}{2^n}$. For $\alpha <1$ then $n\rightarrow \infty$ we have $S_\alpha = n \ln{2}$ while for $\alpha=1$ then $n\rightarrow \infty$ we have $S_1 = (1-p) n \ln{2}$. The Renyi entropy for $\alpha > 1$ doesn't even scale with $n$.

Keeping $\chi = e^{S_1}$ states leads to an error of $\epsilon = \frac{(2^n - 2^{(1-p)n})(1-p)}{2^n} \sim (1-p)$. Thus we can make $\epsilon$ as close to one as we like by taking $p$ to zero.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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