Upper bound on Huffman codeword length I am reading Elements of Information Theory by Cover and Thomas and have been unable to find an upper bound on the length of a codeword in a Huffman code, either in this book or on the web.  Does one exist?  If so, could someone provide an outline of a proof and an example achieving this bound?  Please assume that we don't know the number of symbols to be encoded in advance, only the probability of a given codeword.
 A: The length of a codeword is simply the length of the path from the root of the tree in the construction of the Huffman code to the leaf corresponding to the symbol that it codes for. If you know the total number of symbols to be coded for, then you know the number of leaves, so what is the maximum path length possible?
After edit
If you only have the probability of a codeword, then you need to have a finer grasp of the Huffman tree. You should of course first understand the proof of the Huffman code optimality, since the core property is the key to most of its other properties. Recall that in the tree the weight of a leaf is just the probability of the symbol and the weight of an internal node is just the sum of the children's weights.
The core property is that in any optimal tree, for any two nodes $a,b$, if $a$ is heavier than $b$ then $a$ is not below $b$, otherwise swapping the subtrees will give a better tree. This is key to proving that any optimal tree can be transformed into another optimal tree that agrees with the code generated by the Huffman algorithm.
This same core property is key for this question too. We want for any node an upper bound on its depth given a lower bound on its weight. Equivalently, we want an upper bound on its weight given a lower bound on its depth. But if we go from the root to the lightest child at each step, its weight must decrease by a factor of at least $2$ at each step. Thus the lightest node at depth $k$ has weight at most $2^{-k}$. But any node at depth $k+1$ is at least as light as the lightest node at depth $k$ by the core property, and hence we have an upper bound on its weight. From this it is easy to get an upper bound on the depth given the weight.
A: I would have posted a reply to the previous answer instead but I do not have enough reputation so I will try to make this answer worth while still. The previous response by user21280 is not percise. A lightest path to a node at depth $d$ does not always exist. For instance take the distribution $(1/3, 1/3, 1/3)$, the lightest child of the root has weight of $1/3$ but has no children, thus there is no lightest path of depth 2. It is possible to observe that this example is scalable and this indeed is no fluke, there is an underlying truth which is: huffman trees, although minimize the average depth of a node and are optimal in that sense, do not necessarily achieve the $\text{ideal length} + 1$ bound for all nodes. In order to prove the $\text{entropy} + 1$ bound one can consider the Shannon Fano code which, whereas not necessarily optimal, achieves the $\text{ideal length} + \text{at most $1$}$ for each node. This means that SF codes achieve the $\text{entropy} + 1$ bound, and through optimality of the huffman code on the average depth one can deduce that the previous upper bound holds for huffman trees as their average depth is upper bounded by that of SF trees.
Proving that there are codes that achieve ideal length up to 1 (without using SF codes) can be done simply using Kraft's inequality (Kraft-McMillan) as can be seen at this link on pages 10-13.
