シャノンの情報源符号化定理
1 ≤ i ≤ n について、si をそれぞれ可能な xi の語長とする。 q i = a − s i / C {\displaystyle q_{i}=a^{-s_{i}}/C} と定義する。ここで、 C は q1 + ... + qn = 1 となるように選択される。
H ( X ) = − ∑ i = 1 n p i log 2  p i ≤ − ∑ i = 1 n p i log 2  q i = − ∑ i = 1 n p i log 2  a − s i + ∑ i = 1 n p i log 2  C = − ∑ i = 1 n p i log 2  a − s i + log 2  C ≤ − ∑ i = 1 n − s i p i log 2  a ≤ E S log 2  a {\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}}