It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds: $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$ With $\epsilon_n\to 0$ for $n\to\infty$.

The proof is made in Thomas & Cover: Elements of Information Theory (Lemma 12.10.1, page 320 in the linked chapter).

I tried to generalize it to an alphabet of size $k$ by adjust the proof step by step, but I failed. So, my question:

How can I prove that the number $c(n)$ of phrases / tupel of the LZ compression is bounded by $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_k n}$$ for all words of length $n$ over an alphabet of size $k$ with $\epsilon_n\to0$ for $n\to\infty\;?$

  • $\begingroup$ Sounds like an exercise. I suggest you keep trying. $\endgroup$ Jun 19, 2014 at 16:01
  • $\begingroup$ If you mean an axercise for a course or something like that, it is not. But even if it were, your comment do not help me at all. $\endgroup$
    – Danny
    Jun 19, 2014 at 16:08
  • 1
    $\begingroup$ Perhaps if you showed us the partial proof you have constructed so far, and where you think it broke down, we could give you better help. As it is, we can't tell what concepts you are having trouble with, so there's not anything useful that we can say. $\endgroup$ Jun 19, 2014 at 19:36
  • $\begingroup$ @WanderingLogic my question was more about some other way to prove this theorem.. like the answer i accept or maybe induction. Therefore i omit my try since it contains a lot of big expressions (see $n_k$ in the proof for $k=2$) $\endgroup$
    – Danny
    Jun 20, 2014 at 6:39
  • $\begingroup$ Really? A down vote for that question? A lot of stupid questions pass that site and this question was down voted.. thanks. $\endgroup$
    – Danny
    Jun 20, 2014 at 6:41

1 Answer 1


You don't need to redo the proof for this, simply note that $n$ symbols of an alphabet of size $k$ can be represented with $n \log_2(k)$ bits. The Lempel-Ziv bound is then:

$\mbox{# phrases} \leq \frac{n log_2 k}{(1-\epsilon_{n \lg k})log_2(n \log_2 k)}$

Dividing numerator and denominator by $\log_2 k$ then gives:

$\mbox{# phrases} \leq \frac{n}{(1-\epsilon_{n \lg k})\left(log_k(n) + \log_2(\log_2(k))/log_2(k)\right)}$

Since $\epsilon_n \longrightarrow 0$ as $n \longrightarrow \infty$, the result follows.

  • $\begingroup$ Thanks, i thought about something like that when i'm asking this question. $\endgroup$
    – Danny
    Jun 20, 2014 at 6:29

Your Answer

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

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