Editing Shannon's source coding theorem (section)

== Proof: Source coding theorem for symbol codes ==
For {{math|1 ≤ ''i'' ≤ ''n''}} let {{math|''s<sub>i</sub>''}} denote the word length of each possible {{math|''x<sub>i</sub>''}}. Define <math>q_i = a^{-s_i}/C</math>, where {{mvar|C}} is chosen so that {{math|''q''<sub>1</sub> + ... + ''q<sub>n</sub>'' {{=}} 1}}.  Then

:<math>\begin{align}
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 \\
     &=  \mathbb{E} S \log_2 a \\
\end{align}</math>

where the second line follows from [[Gibbs' inequality]] and the fifth line follows from [[Kraft's inequality]]:

:<math>C = \sum_{i=1}^n a^{-s_i} \leq 1</math>

so {{math|log ''C'' ≤ 0}}.

For the second inequality we may set

:<math>s_i = \lceil - \log_a p_i \rceil </math>

so that

:<math> - \log_a p_i \leq s_i < -\log_a p_i + 1 </math>

and so

:<math> a^{-s_i} \leq p_i</math>

and

:<math> \sum  a^{-s_i} \leq \sum p_i = 1</math>

and so by Kraft's inequality there exists a prefix-free code having those word lengths. Thus the minimal {{mvar|S}} satisfies

:<math>\begin{align}
\mathbb{E} S & = \sum p_i s_i \\
& < \sum p_i \left( -\log_a p_i +1 \right) \\
& = \sum - p_i \frac{\log_2 p_i}{\log_2 a} +1 \\
& = \frac{H(X)}{\log_2 a} +1 \\
\end{align}</math>