No puedo resolver el siguiente problema:
Dejemos que $$n \geq 2$$ $$p_{1} \geq p_{2} \geq ... \geq p_{n}$$ $$p_{i} = 2^{-k_{i}}$$ avec $k_{i} \in \mathbb{N}$ y $\sum_{i=1}^{n}p_{i} = 1$ .
$p_{i}$ es la probabilidad de que el carácter $c_{i}$ aparece. A continuación, ejecutamos el algoritmo de Huffman. Mostrar: La longitud de código esperada del código Huffman resultante es $$-\sum_{i=1}^{n}p_{i}\log{p_{i}}$$
¿Cómo se demuestra eso? En la primera parte de la tarea mostré que $p_{n-1} = p_{n}$ .
Esto es lo que tengo hasta ahora: Creo que el valor esperado de la longitud del código se define como $E(C) = \sum_{i=1}^{n}p_{i}h(c_{i})$ donde $h(c_{i})$ es la altura del carácter $c_{i}$ en el árbol de Huffman.
De ahí se deduce que tengo que demostrar que $E(C) = \sum_{i=1}^{n}p_{i}h(c_{i}) = \sum_{i=1}^{n}p_{i}k_{i}$ Así que pensé en mostrar eso $h(c_{i}) = k_{i}$ . Me han dicho que esto se puede hacer por inducción. Pero, ¿cómo se demuestra esto?
Agradecería mucho cualquier ayuda, consejo, idea o solución/prueba. Espero haber dejado claro cuál es el problema, ya que lo he traducido de mi lengua materna al inglés. Si hay algo que no es comprensible, por favor hágamelo saber. ¡Gracias de antemano y que tengan un buen día!
