Weighted probability using Huffman Tree I want to produce a value from a set, where each value has an associated weight.

Eg:

[(1, 4), (2, 3), (3, 3)]


should give me a 40% chance of picking 1, and a 30% chance of picking 2 or 3 respectively. 

Using a cumulative sum table and binary searching on it yields the value I want in O(logN) where N is the number of values in the set.

I was thinking of another approach to this using a huffman tree (as described here) with the combined weights of its children stored on each node.

For the above case, the tree would look like

    (10)
   /    \
(1, 4)  (6)
       /   \
   (2, 3) (3, 3)


The algorithm for generate() would be something like:


Generate random number k in range [0, {value of root node})
Start at root node
If at a leaf node, return value
If k >= {value of left child}, go right else go left
Repeat from third step.


Now, in the case that the weights are about the same, this will take O(logN), similar to the binary search method.

However, if the weights increase in an exponential manner and the tree essentially becomes a list, the complexity becomes

$$
\sum\limits_{i=1}^N   k/2^k 
$$

Which tends to 2.

I'm having some difficulty coming up with an expression for the average case for generate, but it definitely has an upper bound of O(logN) and a lower bound of O(1). Of course, worst case is O(N).

What's a good approach to figuring this out, and what are the possible pitfalls of this kind of an approach?
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) &lt; 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 &lt; \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} &lt; 1$, let $\ell = \max_i \ell_i$. Notice that
$$
\sum_i 2^{\ell-\ell_i} &lt; 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 &lt; \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&gt;0$ there are distributions $\mu$ for which $T(\mu) \geq H(\mu) + 1 - \epsilon$. Given $\delta&gt;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!