Suppose that $l_1, l_2,\dots$ are natural numbers such that $$\sum_{i=1}^{+\infty}2^{-l_i}\le1 \tag{1}$$ and let $$a_n=\frac{1}{n}\sum_{i=1}^{n}l_i – \log_2n \tag{2}$$ I think $\lim_{n \to \infty} a_n$ doesn't exist but I'm not sure about that. For example for $l_i = i$ we have: $$\sum_{i=1}^{+\infty}2^{-i} = \frac{1/2}{1-1/2} = 1 \\ a_n = \frac{1}{n}\frac{n(n+1)}{2} – \log_2{n} = \frac{n+1}{2} – \log_2{n}$$ It can be shown that in this case $\lim_{n \to \infty} a_n = \infty$. Is it possible to find a sequence of natural numbers $\{l_i\}$ such that $\lim_{n \to \infty} a_n$ exists?
Attempt: We can rewrite $a_n$ as follows: $$a_n = \frac{1}{n}(\sum_{i=1}^{n}l_i – n\log_2n) = \frac{1}{n}(\sum_{i=1}^{n}l_i – \sum_{i=1}^{n}\log_2n) = \frac{1}{n}\sum_{i=1}^{n}(l_i – \log_2n)$$ It seems that condition $(1)$ imposes some constraint on the growth of $l_i – \log_2n$ for large $n$. If we can compare this growth with $n$, it would be possible to find the limit.
Background: This question comes from information theory. A prefix-free code satisfies Kraft inequality which is $(1)$. For a source with uniform distribution on $n$ symbols the entropy is $\log_2n$. Also the average length of code for this source is $$\sum_{i=1}^{n}p_il_i = \frac{1}{n}\sum_{i=1}^{n}l_i$$ So the redundancy in code can be computed as $(2)$.
Best Answer
Let $b_k = 2^{-l_k}$, or $l_k = -\log_2 b_k$. Then
$$ \begin{align} a_n&=-\frac{1}{n}\sum_{k=1}^{n} \log_2 b_k - \log_2 n \tag{1}\\ &=-\frac{1}{n}\sum_{k=1}^{n} \log_2(k \,b_k) +\frac{1}{n} \sum_{k=1}^{n}\log_2 k - \log_2 n \tag{2}\\ &=\frac{1}{n}\sum_{k=1}^{n} \log_2 \frac{1}{k \,b_k} +O(1) \tag{3}\\ &\ge \log_2 \frac{n}{\sum_{k=1}^{n} k b_k} +O(1) \tag{4} \end{align} $$
where in $(2)\to (3)$ we've used $\sum_{k=1}^{n} \log_2(k) = \log_2 (n!) = n \log_2 n - n \log_2 e +O(\log n)$.
And for $(3)\to (4)$ we've used the log-sum inequality.
Let $B = \sum_{k=1}^\infty b_k \le 1$
If $B=1$, then $b_k$ represents a discrete distribution function. In that case we have
$$ \frac{1}{n} \sum_{k=1}^n k \, b_k \to 0$$
as $n \to \infty$ (proof here). Hence $a_n$ in $(4)$ diverges.
This also (a fortiori) applies for $B<1$.