Proving a binary string of length i is less than or equal to $2^i$?

Question

This is a problem I've gotten on my Graph Theory Homework, and I'm I'm not quite sure how to start off with proving it.

The question is as follows:

Let $\mathcal S$ be a finite collection of binary strings of finite length, i.e. finite sequences of $0$’s and $1$’s.

Suppose that $\mathcal S$ has the property that no member of $\mathcal S$ is a prefix of another member of $\mathcal S$, for example $11010$ and $110$ could not be in $\mathcal S$ because $110$ is a prefix of $11010$.

Let $N_i$ be the number of sequences of length $i$ in $\mathcal S$.

Show that $$\sum \frac{N_i}{2^i}\le 1$$

Any help would be greatly Appreciated!

Answer 1

Hint: One interesting way to deal with the condition that "no string is a prefix of another" is to add in every string that any string in the set is a prefix of. For example, if $01$ is in the set, our new set contains every string starting with $01$.

Now, look at the strings in our new set of length $N$ for some large $N$ (say, larger than the length of any string in our original set). How many of them are there at most, and how do we relate this to the given sum?

Answer 2

This is a standard theorem in Kolmogorov complexity, which is sometimes called Kraft's inequality. The problem here follows directly from Theorem 1.1 in the text by Li and Vitanyi.

The most straightforward proof is to see that the set of strings you have determines an open set of the Cantor space $2^{\mathbb{N}}$. The Cantor space consists of all infinite sequences of 0s and 1s, while the open set is the union of the cylinders $\sigma \smallfrown 2^{\mathbb{N}}$ for each $\sigma$ in the set. The measure of each such cylinder under the fair coin measure is $2^{-|\sigma|}$, the cylinders are pairwise disjoint because of the prefix-free condition, the sum in the question is the total measure of the open set, and the measure of the entire Cantor space is $1$.

This also shows there is no reason to assume $S$ is finite, we only need to know it is prefix-free.