2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Use the alias method instead. $\endgroup$ – Yuval Filmus May 18 '18 at 17:28
  • $\begingroup$ Interesting! However, my question is not about an optimal way to solve this problem, but rather help analyzing this particular method. $\endgroup$ – 1419636215 May 18 '18 at 18:07
  • $\begingroup$ There is no "smart" expression for the average depth of a leaf. However, it always lies between $H(\mu)$ and $H(\mu)+1$, where $\mu$ is the distribution being generated. $\endgroup$ – Yuval Filmus May 18 '18 at 18:09
  • $\begingroup$ Sorry, I'm somewhat unfamiliar with the notation. What is H? $\endgroup$ – 1419636215 May 18 '18 at 19:03
  • $\begingroup$ It's the entropy of $\mu$, given by $H(\mu) = \sum_i \mu_i \log_2 (1/\mu_i)$, where $\mu_i$ is the probability of element $i$. $\endgroup$ – Yuval Filmus May 18 '18 at 19:19
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ If I had the reputation, I'd upvote this. I'm not sure what to make of the last 2 paragraphs though. You've shown that there exists probability distributions such that T(μ)≥H(μ)+1−ϵ. What does this imply? Also, what gap do you mean with small probabilities? $\endgroup$ – 1419636215 May 21 '18 at 20:05
  • $\begingroup$ So this tells me that the average height of a leaf is near H(μ). The cost associated with visiting this average node is H(μ). Therefore, on average lookup for this structure is H(μ). Please correct me if I'm wrong. $\endgroup$ – 1419636215 May 21 '18 at 20:15
  • $\begingroup$ The second-to-last paragraph shows that the inequality $T(\mu) < H(\mu) + 1$ is best possible in the sense that $1$ cannot be replaced by any smaller constant. The last paragraph shows that the gap between $H(\mu)$ and $T(\mu)$ doesn't go to zero even if the distribution is very "smooth". $\endgroup$ – Yuval Filmus May 21 '18 at 20:42
  • $\begingroup$ Ah. Didn't pick up on that. Appreciate it. $\endgroup$ – 1419636215 May 21 '18 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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