Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A$ be a finite alphabet with $|A|=a$, let $S$ be a (not neccesarily finite) set of non-empty words in the free monoid $A^*$ such that $S$ generates a free monoid of $A^*$. Prove that $$\sum\limits_{w\in S}\frac{1}{a^{l(w)}}\leq 1$$ where $l(w)$ is the length of word $w$.

share|cite|improve this question
You need to formulate more carefully. You want $S$ to be independent, to freely generate a free monoid so to speak. If not, you can just take $S=A^*$, which certainly generates the free monoid $A^*$, for a counterexample. – Marc van Leeuwen Nov 18 '12 at 9:54
Assuming that $S$ is intended to be the minimal generating set of $S^*$, $S$ is a code, and this is the Kraft inequality. (The link gives only the finite case, but the countably infinite case is a consequence.) – Brian M. Scott Nov 18 '12 at 10:16

As pointed out by Brian Scott, this is the Kraft inequality (more precisely the Kraft-McMillan theorem in your case since you don't assume that $S$ is prefix). For a proof of the general case and an interesting extension to Bernoulli distributions, see Chapter 2 in

J. Berstel, D. Perrin and C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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