# Probabilistic Proof of Kraft-Mcmillan Inequality

Let $\mathcal{C}$ be a finite binary code such that for any two sequences $\{a_n\},\{b_n\}\in \mathcal{C}$ if $a_j\not=b_j$ for some $j$ then the concatenation binary sequence $a_1a_2\cdots a_n\not=b_1b_2\cdots b_n$, the Kraft-Mcmillan Inequality says that $$\sum_{i}\frac{N_i}{2^{i}}\le 1,$$where $N_i$ is the number of codes in $\mathcal{C}$ with length of $i$.

If we assume the code is prefix free, we will have an elegant probabilistic proof at here (consider the infinite binary sequence generated by i.i.d. binomial random variable with probability $1/2$, define $E_x$ be the event that the sequence has prefix $x\in \mathcal{C}$, then $\sum_i\frac{N_i}{2^i}\le \sum_i P[E_x]= P[\cup_i E_x]=1$). But for the general case one will not necessarily have the events $E_i$s disjoint, I'm curious if similar argument exists for the general case. (The problem is an excercise in the probabilistic method of alon, I guess some probabilistic argument should exist)

(My attempt is that consider the product topology $T=\prod_i\mathcal C$ whose open sets generated by $E_x$s where $x$ is the concatenation codes of $\mathcal{C}$, we define a natural product measure $\mu$ over $T$ by $\mu(E_x)=2^{-|x|}$. Clearly $\mu(T)\le 1$ (as $T$ is a sub-topology of $\prod_i\{0,1\}$), I want to show $\mu(E_x\cap E_y)=0$ for $x\not=y\in \mathcal{C}$, if not we can find $E_z$ such that $E_z\subset E_x\cap E_y$ by compactness, if we can show $z$ can be write as concatenation code start with both $x,y$ we will done, but I get stuck at here.)

• Your statement "for any two sequences $\{a_n\},\{b_n\}\in \mathcal{C}$ if $a_j\not=b_j$ for some $j$ then the concatenation binary sequence $a_1a_2\cdots a_n\not=b_1b_2\cdots b_n$" seems meaningless to me. If $a_j\neq b_j$ then the concatenation sequences are automatically distinct. So what exactly are you trying to say with that condition? Commented Oct 2, 2016 at 4:34
• @kodlu The second '$\not=$' was compared in the binary sense.
– Paul
Commented Oct 2, 2016 at 6:46
• I think the statement is not quite correct. The two sequences needn't have the same number of terms, need they? Commented Dec 18, 2017 at 10:12
• @saulspatz Yes, you are right, the number of terms are not necessary the same.
– Paul
Commented Dec 18, 2017 at 20:35

EDIT: I originally posted a partial proof, and the OP showed me how to complete it in a comment. I'm revising the post to give a complete proof.

Suppose on the contrary that $$\sum_{i=1}^{k}\frac{N_i}{2^{i}} > 1,$$ and let $$E_n$$ be the expected number of ways that a random binary string of length $$n$$ can be deciphered, where $$n$$ is longer than the longest codeword. Then $$E_n = \sum_{i=1}^k\frac{N_i}{2^{i}}E_{n-i},$$ since the probability that the the first $$i$$ bits of the string is a codeword is $$\frac{N_i}{2^{i}},$$ and the expected number of ways to decipher the rest of the string is $$E_{n-i}.$$

If for some $$n$$ we have $$E_n > 1,$$ then there is some string of length $$n$$ with more than one decipherment, contradiction.

At this point, I was struggling with the roots of the characteristic equation, but the OP showed me a much simpler way. The remainder of the proof is based on his insight.

Let $$I = \{i| N_i > 0\}.$$ Suppose $$n = \sum_{i \in I}{a_ii},$$ where the $$a_i$$ are nonnegative integers. Then $$E_n>0,$$ because the string $$\sum_{i\in I}w_i^{a_i}$$ is a string of length $$n$$ with a decipherment. Here each $$w_i$$ is a codeword of length $$i,$$ $$w_i^{a_i}$$ indicates the $$a_i-$$fold repetition of $$w_i,$$ and the sum means concatenation. (Of course, the only way $$E_n$$ can be 0 is if no $$n$$-bit string has a decipherment.)

Now let $$r = \text{gcd}(I).$$ Then there is a $$N$$ such that for every $$n\ge N, nr$$ can be written in the form $$nr = \sum_{i \in I}{a_ii}, \text{ with }a_i\ge 0,$$ so that for sufficiently large $$n, E_{nr} > 0.$$ Then for some $$n,$$ in the recurrence $$E_{nr} = \sum_{i \in I}\frac{N_i}{2^{i}}E_{nr-i}\tag1,$$ every expectation on the right-hand side is positive. Let $$c$$ be the minimum of these expectations. Then $$E_{nr} \ge c \sum_{i\in I}\frac{N_i}{2^{i}} = ct, \text{ where } t >1.$$

Now if we replace $$n$$ by $$n+1$$ in $$(1)$$, the minimum expectation on the right-hand side will be at least $$c$$, since $$ct > c$$. Thus, the same argument shows that $$E_{nr+r} \ge tc.$$ Continue in this manner through enough terms so that each expectation on the the right-hand side is $$\ge tc.$$ Then the next expectation in the sequence is $$\ge t^2c,$$ and we can find expectations $$\ge t^hc$$ for every positive integer $$h$$. Since $$t>1,$$ some $$E_n>1,$$ which completes the proof.

The number-theoretic fact about representation of large multiples of $$r$$ follows at once from Schur's theorem, the $$r=1$$ case. Schur gave his name to several theorems, so in googling it's better to search for "Frobenius coin problem."

• This is a nice proof! The gap can be fixed as follows: let $I=\{i|N_i\not=0\}$, denote r=gcd(I) as the greatest common divisor of all the elements in I, by a simple result in number theory we know that there exist a sufficient large M, such that for all $m\ge M$, we have $E_{rm}\ge c>0$. Take $n=hMr$, we have $E_{n}> ct^h} where$t=\sum N_i/2^i>1$, thus, by taking h sufficient large, we have$E_n>1$. – Paul Commented Dec 18, 2017 at 20:29 • @Paul Thanks. I've been struggling to apply Perron-Frobenius to the companion matrix of the characteristic polynomial, and I think it can be done that way, but I haven't been able to resolve all the technicalities. Once I've verified your comment, I'll edit my answer to be a complete proof. Commented Dec 18, 2017 at 21:49 • @saulspatz Nice proof. But can you also mention what is the characteristic equation in this context? Commented Apr 25, 2020 at 16:19 • @caffeinemachine$E_n = \sum_{i=1}^k\frac{N_i}{2^{i}}E_{n-i}$is a linear recurrence relation so it has an associated characteristic equation, as explained in the wikipedia article. Commented Apr 25, 2020 at 18:34 • I have two questions: (1) What about the case where$r \neq 1$? (2) Could you elaborate a bit on the paragraph starting with “Since$ct > c\$,…”? Commented Jul 29, 2020 at 11:32