# Tag Info

7

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample. And if you want a really nice counterexample, consider the many non-isomorphic Huffman trees you can make when you have probabilities proportional to $$1,1,1,2,3,5,8,13,21,34$$ (the Fibonacci ...

7

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are reachable from the start state Helpful subroutine Suppose we have an NFA $N$, a state $q$, and a nonempty string $s$. The following subroutine will let us evaluate ...

3

Because an optimal prefix free code, e.g. a Huffman code, can be shown to be within one bit of source entropy. This is certainly in Cover and Thomas, I am pretty sure.

3

I'll try to show this, hope I interpreted the question correctly. Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies $$\max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup A_k \}\leq k+ \log k,$$ for $k\geq N$, for some finite $N$, where $\ell(c(x))$ is the length of the codeword $c(x)$ assigned to $x.$ So this means that  \sum_{...

2

Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots$ and $v_1,\dots,v_n,\dots$ such that: For each $n\ge 1$, $u_n$ and $v_n$ are non-empty and start with distinct letters; $S=\{u_0v_1,\dots,u_0\dots u_n v_{n+1},\dots\}$. ...

1

Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] proved that deciding if a binary code contains a code word of weight $w$ is NP-complete. In http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf Diaconis and Graham prove that deciding if a binary code of ...

Only top voted, non community-wiki answers of a minimum length are eligible