Proof average codeword length of a prefix code $C$ is the sum of probability of all leaf vertices that are descendant

50 Views Asked by At

Let $I$ represent the set of all interior vertices in a binary tree. Define the probability of vertex $v \in I$ is $P(v)$, which is the sum of the probabilities of all leaf vertices that are descendants of $v$. Show that (or given a counter-example)

$$L(C) = \sum_{v\in \mathcal{I}}^{} P(v) .$$

1

There are 1 best solutions below

0
On

Suppose that $u$ is a leaf at depth $d(u)$; then there are $d(u)$ interior vertices in the path from $u$ to the root, so $u$ contributes $d(u)P(u)$ to $\sum_{v\in I}P(v)$. Thus, if $L$ is the set of leaves,

$$\sum_{v\in I}P(v)=\sum_{v\in L}d(v)P(v)\,.$$

On the other hand, $d(u)$ is the length of the code word corresponding to a leaf $u$, so $\sum_{v\in L}d(v)P(v)$ is the mean length of a code word of $C$.