1
$\begingroup$

Let $\mathcal{T}_n$ be the set of ordered binary trees that have n leaves.

$d_T(v)$ means the node $v$'s depth in the tree T.

Prove: for any $T\in \mathcal{T}_n$ , for any $\{c_1,c_2,...c_n\}$ , $c_i >0$ , $S=\sum_i c_i$

$$ -\sum_{i=1}^n(c_i\cdot\log_2(c_i/S)) \le \sum_{i=1}^{n} (c_i\cdot d_T(v_i)) $$

$v_i$ means the i-th leaf in tree T.


My primary thought:

Since it has log2, so maybe 2^x can be a direction. Then 2 leaves have the same parent, their depth are the same. $2^{-depth1} + 2^{-depth} = 2^{-parent's depth}$

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Gibbs'inequality implies that $$-\sum _{i=1}^{n}p_{i}\log p_{i}\leq -\sum _{i=1}^{n}p_{i}\log q_{i}$$ if $p_i\ge0$, $q_i\ge0$, $\sum _{i=1}^{n}p_{i}=1$ and $\sum _{i=1}^{n}q_{i}\le1$.


Let $T$ be a binary tree with $n$ leaves $v_1, \cdots, v_n$ and $q_i=2^{-d_T(v_i)}$. Let $p_i=c_i/S$. It is obvious that

  1. $p_i\ge0$ and $\sum _{i=1}^{n}p_{i}=1$,
  2. $q_i\ge0$ and $\sum _{i=1}^{n}q_{i}\le1$,

except that last inequality.

Claim: $\sum_{i=1}^{n} 2^{-d_T(v_i)}\le 1$.
Proof: This is immediate from the recursive nature of a binary tree, as indicated by the thought at the end of the question.

Now we can obtain the inequality at the start of this answer. It is none other than the wanted inequality in the question.

$\endgroup$
1
  • $\begingroup$ so there is a little trick: $x = \log_2(2^x)$ , to make both side has $\log_2$ $\endgroup$ Apr 18, 2022 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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