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$ – Yuval Filmus Jun 19 '14 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 '14 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$ – Wandering Logic Jun 19 '14 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 '14 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 '14 at 6:41

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 '14 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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