IS CS-2021W-01

题目来源：Problem 1 日期：2024-07-24 题目主题：CS-信息数学-有序二叉树

解题思路

这道题目涉及有序二叉树（每个节点最多有两个有序子节点）和其叶节点的权重。我们需要找到一种特定结构的二叉树，使得某些函数达到最优值。特别地，我们可以使用哈夫曼树的概念来解决第一题。

Solution

Q1: Give the tree $T\in {\mathbf{T}}_4$ that has the smallest value of ${\mathbf{W}}_{\mathbf{P}}(T)$ in case $\mathbf{P}=(4,2,1,1)$

To minimize ${\mathbf{W}}_{\mathbf{P}}(T)$, we should construct a tree that resembles a Huffman tree, where the most frequent items (with the highest weights) are located at shallower depths. Here, the weights are $(4,2,1,1)$.

Steps to construct the tree:

1. Start by pairing the two smallest weights, which are both $1$.
2. Combine these to form a subtree with a combined weight of $2$.
3. Now, we have weights $(4,2,2)$.
4. Next, combine the two smallest remaining weights, which are both $2$.
5. Combine these to form a subtree with a combined weight of $4$.
6. Finally, combine the two subtrees $(4,4)$ to form the complete tree.

The resulting tree structure is:

      O
     / \
    4   O
       / \
      2   O
         / \
        1   1

Thus, the depth of each leaf in the tree is:

• $c_1=4$, depth ${\mathrm{d}}_{\mathrm{T}}(v_1)=1$
• $c_2=2$, depth ${\mathrm{d}}_{\mathrm{T}}(v_2)=2$
• $c_3=1$, depth ${\mathrm{d}}_{\mathrm{T}}(v_3)=3$
• $c_4=1$, depth ${\mathrm{d}}_{\mathrm{T}}(v_4)=3$

Now, we calculate ${\mathbf{W}}_{\mathbf{P}}(T)$:

$${\mathbf{W}}_{\mathbf{P}}(T)=4\cdot 1+2\cdot 2+1\cdot 3+1\cdot 3=4+4+3+3=14$$

Thus, the tree $T$ that minimizes ${\mathbf{W}}_{\mathbf{P}}(T)$ has the above structure.

Q2: Show that ${\sum }_{i=1}^n{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$ holds for any ordered binary tree $T\in {\mathbf{T}}_{\mathbf{n}}$ with leaves $v_1,v_2,\dots ,v_n$ using mathematical induction

To prove the inequality ${\sum }_{i=1}^n{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$ using mathematical induction, we need to follow these steps:

1. Base Case
2. Inductive Step

Base Case: For $n=1$ (a tree with only one leaf), the depth of the only leaf $v_1$ is 0.

$$\sum _{i=1}^1{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}=2^{-{\mathrm{d}}_{\mathrm{T}}(v_1)}=2^0=1$$

Thus, the base case holds.

Inductive Step: Assume that for any ordered binary tree with $k$ leaves, the inequality holds:

$$\sum _{i=1}^k{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$$

Now, we need to prove that the inequality holds for an ordered binary tree with $k+1$ leaves.

1. Consider an ordered binary tree with $k+1$ leaves.
2. Let’s denote the depth of the leaves in this tree by ${\mathrm{d}}_{\mathrm{T}}(v_1),{\mathrm{d}}_{\mathrm{T}}(v_2),\dots ,{\mathrm{d}}_{\mathrm{T}}(v_{k+1})$.

When we add an additional leaf to a tree with $k$ leaves to form a tree with $k+1$ leaves, we must split one of the existing leaves into two children. This operation increases the depth of the affected leaf by 1 and adds a new leaf with the same depth.

Suppose we split the leaf $v_j$ (where ${\mathrm{d}}_{\mathrm{T}}(v_j)=d$) into two new leaves $v_j^{\prime }$ and $v_{k+1}$, both at depth $d+1$.

Thus, we need to show:

$$\sum _{i=1}^k{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}+2^{-(d+1)}+2^{-(d+1)}\le 1$$

By the inductive hypothesis, for the original tree with $k$ leaves:

$$\sum _{i=1}^k{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$$

In the new tree:

$$\sum _{i=1}^k{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}-2^{-d}+2^{-(d+1)}+2^{-(d+1)}$$

Since $2^{-(d+1)}+2^{-(d+1)}=2^{-d}$:

$$\sum _{i=1}^{k+1}{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}=\sum _{i=1}^k{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$$

Thus, the inequality holds after adding a new leaf and increasing the depth of the original leaf.

By induction, the inequality ${\sum }_{i=1}^n{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$ holds for all $n$.

Q3: Assume that $x_1,x_2,\dots ,x_n$ range over the set of positive real numbers so that ${\sum }_{i=1}^n{x}_i=1$. Show that ${\sum }_{i=1}^n(c_i\cdot {\log }_2{x}_i)$ is maximized when $x_i=c_i/{\mathbf{S}}_{\mathbf{P}}$ for any sequence $\mathbf{P}=(c_1,c_2,\dots ,c_n)$ of $n$ positive real numbers

To maximize ${\sum }_{i=1}^n(c_i\cdot {\log }_2{x}_i)$ under the constraint ${\sum }_{i=1}^n{x}_i=1$, we use the method of Lagrange multipliers.

Define the Lagrangian:

$$\mathcal{L}(x_1,\dots ,x_n,\lambda )=\sum _{i=1}^n(c_i\cdot {\log }_2{x}_i)+\lambda \left(1-\sum _{i=1}^n{x}_i\right)$$

Take the partial derivatives and set them to zero:

$$\frac{\partial \mathcal{L}}{\partial x_i}=\frac{c_i}{x_i\ln 2}-\lambda =0\Rightarrow x_i=\frac{c_i}{\lambda \ln 2}$$

Using the constraint ${\sum }_{i=1}^n{x}_i=1$:

$$\sum _{i=1}^n\frac{c_i}{\lambda \ln 2}=1\Rightarrow \lambda \ln 2={\mathbf{S}}_{\mathbf{P}}\Rightarrow \lambda =\frac{{\mathbf{S}}_{\mathbf{P}}}{\ln 2}$$

Thus, the maximizing $x_i$ is:

$$x_i=\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}$$

Q4: Show that any ordered binary tree $T\in {\mathbf{T}}_{\mathbf{n}}$ satisfies ${\mathbf{W}}_{\mathbf{P}}(T)\ge {\mathbf{H}}_{\mathbf{P}}$ for any sequence $\mathbf{P}=(c_1,c_2,\dots ,c_n)$ of $n$ positive real numbers

To show that ${\mathbf{W}}_{\mathbf{P}}(T)\ge {\mathbf{H}}_{\mathbf{P}}$, we need to use the definitions of ${\mathbf{W}}_{\mathbf{P}}(T)$ and ${\mathbf{H}}_{\mathbf{P}}$ and employ some fundamental principles of information theory and entropy.

Recall:

$${\mathbf{W}}_{\mathbf{P}}(T)=\sum _{i=1}^n(c_i\cdot {\mathrm{d}}_{\mathrm{T}}(v_i))$$ $${\mathbf{H}}_{\mathbf{P}}=-\sum _{i=1}^n\left(c_i\cdot {\log }_2\left(\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\right)\right)$$

We start by rewriting ${\mathbf{H}}_{\mathbf{P}}$ in a more convenient form:

$${\mathbf{H}}_{\mathbf{P}}=\sum _{i=1}^n{c}_i\cdot \left({\log }_2({\mathbf{S}}_{\mathbf{P}})-{\log }_2(c_i)\right)={\log }_2({\mathbf{S}}_{\mathbf{P}})\cdot \sum _{i=1}^n{c}_i-\sum _{i=1}^n(c_i\cdot {\log }_2(c_i))$$

Since ${\sum }_{i=1}^n{c}_i={\mathbf{S}}_{\mathbf{P}}$, we get:

$${\mathbf{H}}_{\mathbf{P}}={\mathbf{S}}_{\mathbf{P}}\cdot {\log }_2({\mathbf{S}}_{\mathbf{P}})-\sum _{i=1}^n(c_i\cdot {\log }_2(c_i))$$

Next, consider the following inequality derived from Jensen’s inequality for the concave function $f(x)=-x{\log }_2(x)$:

$$-\sum _{i=1}^n\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\cdot {\log }_2\left(\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\right)\le -{\log }_2\left(\sum _{i=1}^n\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\cdot \frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\right)$$

This simplifies to:

$$-\sum _{i=1}^n\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\cdot {\log }_2\left(\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\right)\le -{\log }_2\left(\sum _{i=1}^n\frac{c_i^2}{{{\mathbf{S}}_{\mathbf{P}}}^2}\right)$$

Since ${\sum }_{i=1}^n{c}_i={\mathbf{S}}_{\mathbf{P}}$, we get:

$$-\sum _{i=1}^n\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\cdot {\log }_2\left(\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\right)\le -{\log }_2\left(\frac{1}{{{\mathbf{S}}_{\mathbf{P}}}^2}\sum _{i=1}^n{c}_i^2\right)$$

So:

$$-\sum _{i=1}^n\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\cdot {\log }_2\left(\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}\right)\le -{\log }_2\left(\frac{1}{{{\mathbf{S}}_{\mathbf{P}}}^2}\cdot {\mathbf{S}}_{\mathbf{P}}\cdot \frac{1}{n}\sum _{i=1}^n{c}_i\right)={\log }_2({\mathbf{S}}_{\mathbf{P}})$$

The weighted path length ${\mathbf{W}}_{\mathbf{P}}(T)$ can be understood using Kraft’s inequality, which relates the depths of leaves in a binary tree to probabilities that sum up to 1. Let $p_i=\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}$ be the probability associated with the $i$-th leaf. According to Kraft’s inequality:

$$\sum _{i=1}^n{2}^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le 1$$

We multiply both sides by ${\mathbf{S}}_{\mathbf{P}}$:

$${\mathbf{S}}_{\mathbf{P}}\sum _{i=1}^n{p}_i\cdot 2^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le {\mathbf{S}}_{\mathbf{P}}$$

Using the fact that $p_i=\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}$:

$$\sum _{i=1}^n{c}_i\cdot 2^{-{\mathrm{d}}_{\mathrm{T}}(v_i)}\le {\mathbf{S}}_{\mathbf{P}}$$

Now, we apply the definition of entropy:

$${\mathbf{H}}_{\mathbf{P}}=-{\mathbf{S}}_{\mathbf{P}}\sum _{i=1}^n{p}_i{\log }_2(p_i)$$

Using Gibbs’ inequality, we know that:

$$-\sum _{i=1}^n{p}_i{\log }_2(p_i)\le \sum _{i=1}^n{p}_i{\mathrm{d}}_{\mathrm{T}}(v_i)$$

Multiplying both sides by ${\mathbf{S}}_{\mathbf{P}}$:

$${\mathbf{S}}_{\mathbf{P}}\cdot {\mathbf{H}}_{\mathbf{P}}\le {\mathbf{S}}_{\mathbf{P}}\sum _{i=1}^n{p}_i\cdot {\mathrm{d}}_{\mathrm{T}}(v_i)$$

Substituting $p_i=\frac{c_i}{{\mathbf{S}}_{\mathbf{P}}}$ into the inequality:

$${\mathbf{H}}_{\mathbf{P}}\le \sum _{i=1}^n{c}_i\cdot {\mathrm{d}}_{\mathrm{T}}(v_i)$$

Thus, we have shown that ${\mathbf{W}}_{\mathbf{P}}(T)\ge {\mathbf{H}}_{\mathbf{P}}$ for any ordered binary tree $T\in {\mathbf{T}}_{\mathbf{n}}$ and any sequence $\mathbf{P}=(c_1,c_2,\dots ,c_n)$ of $n$ positive real numbers.

知识点

有序二叉树哈夫曼树信息论拉格朗日乘数法数学归纳法

重点词汇

• Ordered binary tree 有序二叉树
• Huffman tree 哈夫曼树
• Depth 深度
• Lagrange multipliers 拉格朗日乘子
• Entropy 熵
• Lagrange multiplier 拉格朗日乘数
• Jensen’s inequality 詹森不等式
• Gibbs’ inequality 吉布斯不等式
• Kraft’s inequality 克拉夫特不等式

参考资料

1. Introduction to Algorithms, Chapter 16: Greedy Algorithms
2. Information Theory, Inference, and Learning Algorithms, David J.C. MacKay