Given a distribution $\mu$ on a finite set, let us denote by $T(\mu)$ the average depth of a leaf in a Huffman tree of $\mu$ (depth is measured by the number of edges from root to leaf); we assume that no element has zero probability. Then
$$
H(\mu) \leq T(\mu) < H(\mu)+1,
$$
where $H(\mu) = \sum_i \mu_i \log_2 (1/\mu_i)$ is the entropy of $\mu$ (here $\mu_i$ is the probability of the $i$th element).
To prove this, let us start with Kraft's identity. In the statement below, a complete binary tree is one in which every internal node has exactly two children.
Kraft's identity. There is a complete binary tree whose leaf depths are the multiset $\{\ell_1,\ldots,\ell_n\}$ if and only if $\sum_{i=1}^n 2^{-\ell_i} = 1$.
Proof. Let us first show that the leaf depths satisfy Kraft's identity. The proof is by induction on $n$. If $n = 1$ then $\ell_1 = 0$, and indeed $2^{-\ell_1} = 1$. Otherwise, arbitrarily choose two sibling leaves, and remove them. If the original depth was $\ell$, this affects the multiset of depths by removing $\ell,\ell$ and adding $\ell-1$. The induction hypothesis shows that the new multiset satisfies Kraft's identity. Since $2^\ell + 2^\ell = 2^{\ell-1}$, the original multiset also does, completing the proof.
Let us now show that if a multiset $L$ satisfies Kraft's identity, then there is a complete tree whose leaf depths are $L$. Once again, the proof is by induction on $n = |L|$. If $n = 1$, then necessarily $L = \{0\}$, and the tree consisting of a single leaf works. Otherwise, let $\ell = \max L$. Notice that
$$
2^\ell = \sum_i 2^{\ell - \ell_i}.
$$
If $\ell_i = \ell$ then $2^{\ell - \ell_i} = 1$, and if $\ell_i < \ell$ then $2^{\ell - \ell_i}$ is even. Hence the number of copies of $\ell$ in $L$ is even, and in particular there are at least two such copies. Let us form $L'$ by removing two copies of $\ell$ and replacing them by a copy of $\ell-1$. Applying the induction hypothesis, we obtain a tree $T'$ whose leaf depths are $L'$. By construction, $T'$ has a leaf of depth $\ell-1$. Adding to it two children, we obtain a tree $T$ whose leaf depths are $L$, completing the proof. $\square$
We can now prove the inequalities on $T(\mu)$, starting with $T(\mu) \geq H(\mu)$.
Lower bound on $T(\mu)$. Consider any tree whose leaves are labeled by the support of $\mu$, and suppose that element $i$ is on a leaf at depth $\ell_i$. Let $\nu_i = 2^{-\ell_i}$. Kraft's identity shows that $\sum_i \nu_i = 1$. Since $\ell_i = \log_2(1/\nu_i)$, we have
$$
T(\mu) - H(\mu) = \sum_i \mu_i (\ell_i - \log_2 (1/\mu_i)) = \sum_i \mu_i \log_2 (\mu_i/\nu_i).
$$
The function $\log_2 (1/x)$ is convex, hence Jensen's inequality shows that
$$
\sum_i \mu_i \log_2 (\mu_i/\nu_i) =
\sum_i \mu_i \log_2 \frac{1}{\nu_i/\mu_i} \geq \log_2 \frac{1}{\sum_i \mu_i (\nu_i/\mu_i)} = 0,
$$
using $\sum_i \nu_i = 1$. We conclude that $T(\mu) \geq H(\mu)$. $\square$
The other direction uses Shannon–Fano coding.
Upper bound on $T(\mu)$. Let $\ell_i = \lceil \log_2 (1/\mu_i) \rceil$. Then
$$
\sum_i 2^{-\ell_i} \leq \sum_i 2^{-\log_2 (1/\mu_i)} = \sum_i \mu_i = 1.
$$
If $\sum_i 2^{-\ell_i} < 1$, let $\ell = \max_i \ell_i$. Notice that
$$
\sum_i 2^{\ell-\ell_i} < 2^\ell,
$$
where all summands are integral.
If we decrement one copy of $\ell$ to $\ell-1$ then we increase the left-hand side by $2^{\ell-(\ell-1)} - 2^{\ell-\ell} = 1$, so the left-hand side is still at most $2^\ell$. Hence after the update, we still have $\sum_i 2^{-\ell'_i} \leq 1$, where $\ell'_i$ are the new values. Continue doing so until the sum reaches 1; this must happen, since the decreasing process cannot continue forever (the depths keep decreasing while never dipping below zero). Denoting by $r_i$ the new values, Kraft's identity implies that there exists a tree whose leaf depths are the $r_i$. The average depth of a leaf in this tree is
$$
\sum_i \mu_i r_i \leq \sum_i \mu_i \ell_i < \sum_i \mu_i (\log_2 (1/\mu_i) + 1) = H(\mu) + 1.
$$
Huffman's algorithm will find a tree which is at least as good. $\square$
Finally, let me show that for every $\epsilon>0$ there are distributions $\mu$ for which $T(\mu) \geq H(\mu) + 1 - \epsilon$. Given $\delta>0$, consider the distribution $\mu$ on two elements with $\mu_1 = 1-\delta$ and $\mu_2 = \delta$. Clearly $T(\mu) = 1$, while $\lim_{\delta\to0} H(\mu) = 0$. Therefore we can find positive $\delta$ for which $H(\mu) \leq \epsilon$. For such $\mu$ we have $T(\mu) = 1 \geq H(\mu) + 1 - \epsilon$.
What happens if we force all probabilities to be small? Gallager, in his classic paper Variations on a theme by Huffman showed that even in this regime, there are distributions for which the gap is roughly $\log_2 [(2/e)\log_2 e] \approx 0.086$. Amazingly, this is attained by uniform distributions!
