Error bounds for truncating a probability distribution based on the entropy?

Question

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.

---

Question

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?

Thanks.

Answer 1

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 http://arxiv.org/abs/cond-mat/0505140 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.