Limit of the difference between two sequences

Question

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)$.

Answer 1

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$.

Answer 2

The sequence $a_n$ diverges due to the $\log_{2}(n)$ term. The logarithm grows very slowly, but diverges as n approaches infinity.

Answer 3

I'm writing this answer using @leonbloy's ideas. Let $b_k = 2^{-l_k},\ l_k = -\log_2(b_k)$ and $B = \sum_{k=1}^\infty b_k \le 1$. We can rewrite $a_n$ as follows $$\begin{align} a_n&=-\frac{1}{n}\sum_{k=1}^{n} \log_2(b_k) - \log_2(n) \\ &=-\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) \\ &=-\frac{1}{n}\sum_{k=1}^{n} \log_2(k \,b_k) +\frac{1}{n} \log_2(n!) - \log_2(n)\end{align}$$We show that the sequence $$c_n = \frac{1}{n} \log_2(n!) - \log_2(n)$$ is convergent and the sequence $$d_n = -\frac{1}{n}\sum_{k=1}^{n} \log_2(k \,b_k) = \frac{1}{n}\sum_{k=1}^{n} \log_2(\frac{1}{k \,b_k})$$ tends to $\infty$, so their sum tends to $\infty$.

Limit of $c_n$: Note that $c_n$ can be rearranged as $$c_n = \log_2(\frac{(n!)^{\frac{1}{n}}}{n})$$Using the inequality $$e^{\frac{1}{12n+1}}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n<n!<e^{\frac{1}{12n}}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$ we have $$e^{\frac{1}{12n^2+n}}({2\pi n})^{\frac{1}{2n}}\left(\frac{1}{e}\right)<\frac{(n!)^{\frac{1}{n}}}{n}<e^{\frac{1}{12n^2}}({2\pi n})^{\frac{1}{2n}}\left(\frac{1}{e}\right) $$ It's obvious that $$\lim_{n \to \infty}e^{\frac{1}{12n^2+n}} = \lim_{n \to \infty} e^{\frac{1}{12n^2}} = 1$$ Now we compute the following limit $$\lim_{n \to \infty}({2\pi n})^{\frac{1}{2n}} = \lim_{n \to \infty} \exp(\frac{\ln(2\pi n)}{2n}) = \lim_{n \to \infty} [\exp(\frac{\ln(2\pi)}{2n})][\exp(\frac{\ln(n)}{2n})] = \\ \lim_{n \to \infty} \exp(\frac{\ln(2\pi)}{2n}) \times \lim_{n \to \infty}\exp(\frac{\ln(n)}{2n}) = \exp(0)\times\exp(0) = 1$$ where we have used of the fact $$\lim_{n \to \infty} \frac{\ln(n)}{n} = 0$$ So by the squeeze theorem we have $$\lim_{n \to \infty} \frac{(n!)^{\frac{1}{n}}}{n} = \frac{1}{e}$$ which implies $$\lim_{n \to \infty} c_n = \lim_{n \to \infty} \log_2(\frac{(n!)^{\frac{1}{n}}}{n}) = \log_2(\frac{1}{e}) = -\log_2(e)$$ Limit of $d_n$: The log sum inequality states that for nonnegative numbers $g_1,\dots,g_n$ and $f_1,\dots,f_n$ we have $$\sum_{k = 1}^{n}g_k\log_2({\frac{g_k}{f_k}})\ge(\sum_{k = 1}^{n}g_k)\log_2({\frac{\sum_{k = 1}^{n}g_k}{\sum_{k = 1}^{n}f_k}})$$Let $g_k = 1$ and $f_k = kb_k$, then $$\sum_{k = 1}^{n}\log_2({\frac{1}{kb_k}})\ge(\sum_{k = 1}^{n}1)\log_2({\frac{\sum_{k = 1}^{n}1}{\sum_{k = 1}^{n}kb_k}}) \implies d_n = \frac{1}{n}\sum_{k=1}^{n} \log_2(\frac{1}{k \,b_k}) \ge \log_2(\frac{n}{\sum_{k = 1}^{n}kb_k})$$ Assuming that $l_1\le l_2 \le \dots$ it can be shown that $$\lim_{n \to \infty} nb_n = 0$$ which implies that $$\lim_{n \to \infty} \frac{1}{n}\sum_{k = 1}^{n}kb_k = 0 $$ since the limit of a convergent sequence coincides with its arithmetic mean. This in turn implies that $$\lim_{n \to \infty} \frac{1}{\frac{1}{n}\sum_{k = 1}^{n}kb_k} = \lim_{n \to \infty} \frac{n}{\sum_{k = 1}^{n}kb_k} = \infty \implies \lim_{n \to \infty} \log_2(\frac{n}{\sum_{k = 1}^{n}kb_k}) = \infty$$ Finally, since the lower bound on $d_n$ diverges we have $$\lim_{n \to \infty} d_n = \lim_{n \to \infty} \frac{1}{n}\sum_{k=1}^{n} \log_2(\frac{1}{k \,b_k}) = \infty$$ Note that if the $l_i$'s are not in order, then the limit of $nb_n$ isn't necessarily $0$ (see here for some examples) but it can be shown that out of order lengths can only make $a_n$ larger, so even in that case $a_n$ tends to $\infty$.

Answer 4

Let $$a_n=\frac{1}{n}\sum_{i=1}^{n}l_i - \log_2n \tag{2}$$ and l_i = i.

Taken apart the expression becomes $$a_n=(\frac{1}{n}\sum_{i=1}^{n}i) - \log_2n \tag{2}$$

Which becomes $$\frac{1}{n}\frac{(n)(n+1)}{2} - \log_2n$$ Which equals $$\frac{(n+1)}{2} - \log_2n$$

I believe the question is whether both parts together would approach a definite point as n approaches infinity:

$$\lim_{n \to \infty}$$

$\log_2{n}$ can be replaced with this expression $\frac{\ln n}{\ln 2}$ and proved by $$2^{\log_2{n}} = 2^{\frac{\ln n}{\ln 2}} = (e^{\ln 2})^{\frac{\ln n}{\ln 2}} = e^{\ln n} = n$$

Visually the graph of $\frac{n + 1}{2}$ diverges from the graph of $\frac{\ln n}{\ln 2}$ so therefore $\lim_{n \to \infty}$ = $\frac{\infty + 1}{2}$

There is also the option of replacing the logarithmic function of 2 into a power series:

There exists a power series for ln such that 0 ≤ x ≤ 2 $$\ln(x) = \sum_{i=0}^{\infty}\frac{-1^i}{i+1}(x - 1)^{i+1}$$$$x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} + \frac{x^5}{5}\dots$$

likewise for the domain $\frac{1}{2}$ ≤ x ≤ $\infty$ $$\ln(\frac{1}{x}) = \sum_{i=0}^{\infty}\frac{-1^i}{i+1}(\frac{1}{x} - 1)^{i+1}$$

multiplying both sides by -1 gives $$-\ln(\frac{1}{x}) = -\sum_{i=0}^{\infty}\frac{-1^i}{i+1}(\frac{1}{x} - 1)^{i+1}$$ becomes $$-\ln(\frac{1}{x}) = \sum_{i=0}^{\infty}\frac{-1^{i+1}}{i+1}(\frac{1}{x} - 1)^{i+1}$$

So when $$\lim_{n \to \infty}$$ a_$\infty$ = $\frac{n+1}{2} - \log_{2}{\infty}$ can be restated as $$a_\infty = \frac{\infty+1}{2} - \frac{\ln{\infty}}{\ln 2}$$

or as $$a_\infty = \frac{\infty+1}{2} - \frac{1}{\ln 2}\sum_{i=0}^{\infty}\frac{-1^{i+1}}{i+1}(\frac{1}{\infty} - 1)^{i+1}$$

which can be reduced in the following steps

$$a_\infty = \frac{\infty+1}{2} - \frac{1}{\ln 2}\sum_{i=0}^{\infty}\frac{-1^{i+1}}{i+1}(0 - 1)^{i+1}$$ $$a_\infty = \frac{\infty+1}{2} - \frac{1}{\ln 2}\sum_{i=0}^{\infty}\frac{-1^{i+1}}{i+1}(-1)^{i+1}$$ $$a_\infty = \frac{\infty+1}{2} - \frac{1}{\ln 2}\sum_{i=0}^{\infty}\frac{1^{i+1}}{i+1}$$ $$a_\infty = \frac{\infty+1}{2} - \frac{1}{\ln 2}\sum_{i=0}^{\infty}\frac{1}{i+1}$$ $$a_\infty = \frac{\infty+1}{2} - \frac{1}{\ln 2} - \frac{1}{2 \ln 2} - \frac{1}{3 \ln 2} - \frac{1}{4 \ln 2}\dots$$

diverging to $\frac{\infty}{2}$