# Information theory and data compression
## Information measurement
### The definition of entropy：
\begin{aligned}H(X) = - \sum_{x \in X} p(x) \log p(x)\end{aligned}

Entropy可以看成是一個機率分佈的資訊量，而如果entropy越大，代表資訊量越大。反之如果entropty越小，代表資訊量越小。

舉例來說，一個投擲出去的硬幣，是正面或反面的機率為1，不是正面也不是反面的機率為0，顯然這句話是廢話。
於是我們將上述的機率分佈代入entropy，算出$-( 0 \log 0+ 1 \log 1 ) = 0$，廢話的entropy還真的是0。

而透過微分找極值，顯然當二項分布$p=0.5$時，entropy最大，因為這個機率分佈不會暗示說哪個事件發生的可能比較大。

### The derivation of entropy:
通過上述簡單的介紹entropy，接著推導entropy的公式如何求得。

假如有三個事件$A_{1},A_{2},A_{3}$，其對應的機率分別為$p_{1},p_{2},p_{3}$。
我們將其中兩個事件$A_{2},A_{3}$組成一組，使得另外有兩個事件，$B_{1} = \{ A_{1} \}$ $,$ $B_{2} = \{ A_{2} , A_{3} \}$，其對應的機率為$q_{1}=p_{1},q_{2}=p_{2}+p_{3}$。

而我們希望，從$A_{1},A_{2},A_{3}$算出來的entropy，要與先算$B_{1},B_{2}$的entropy，再按機率比例算$B_{1},B_{2}$集合內的entropy的總和相等。也就是
$\tag{1.1.1}\label{eq_1.1.1}H(p_{1},p_{2},p_{3})=H(q_{1},q_{2})+q_{1}H(p_{1}/q_{1})+q_{2}H(p_{2}/q_{2},p_{3}/q_{2})$

得到了關係式後，我們繼續推導entropy的公式。
先令$H(1/n,1/n,1/n...)=A(n)$。

舉例來說：
$H(1/2,1/2)=A(2),H(1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=A(8)$
而從$\eqref{eq_1.1.1}$我們可以得出：
$A(8)=H(1/2,1/2)+1/2(H(1/2,1/2)+1/2H(1/2,1/2)+1/2H(1/2,1/2))=3A(2)$

從上面的例子可以觀察出下式，證明方法可以從畫顆樹下手
$\tag{1.1.2}\label{eq_1.1.2}A(j^l)=lA(j)$

而對於足夠大的$l$,可以找到一組$(k,m)$使得$A(k^m) \le A(j^l)<A(k^{m+1})$
因此$\eqref{eq_1.1.2}$可以將其化簡為$m/l \le A(j)/A(k) < m/l + 1/l$，也就是
$\tag{1.1.3}\label{eq_1.1.3}|m/l - A(j)/A(k)| < \epsilon$

而因為$k^m \le j^l<k^{m+1}$，且$\log{j^l} = l \log j$，所以透過類似$\eqref{eq_1.1.3}$的過程，
可以得到$\tag{1.1.4}\label{eq_1.1.4}|m/l - \log (j)/ \log(k)| < \epsilon$

最後將$\eqref{eq_1.1.3}$和$\eqref{eq_1.1.4}$合併，得到$|A(j)/A(k) - \log (j)/ \log(k)| <2 \epsilon$，也代表著
$\tag{1.1.5}\label{eq_1.1.5} H=K \log (n)$

其中$K$為常數。

而上面我們只探討了所有事件機率相等的情況，接下來繼續討論事件的機率不相等的情況。

這次假設我們有$\sum_{i \in I} n_{i}$種機率相等的事件。
根據$\eqref{eq_1.1.1}$和$\eqref{eq_1.1.5}$，可以得出下列結論。

\begin{aligned}H&=H(p_{1},p{2}...,p_{i})+\sum_{i \in I}p_{i}H(1/n_{i},...,1/n_{i})
\\&=H(p_{1},p{2}...,p_{i})+ K\sum_{i \in I} p_{i} \log(n_{i})\end{aligned}

左右移位後，可以得到:
\begin{aligned}H(p_{1},p_{2}...,p_{i})
&=K \log (\sum_{i \in I} n_{i}) - K\sum_{i \in I} p_{i} \log(n_{i})
\\&=-K[\sum_{i \in I} p_{i} \log(n_{i})-\log (\sum_{j \in J} n_{j})]
\\&=-K[\sum_{i=1}^{n} p_{i} \log(n_{i})-\log (\sum_{j=1}^{n} n_{j}) \sum_{i=1}^{n}p_{i}]
\\&=-K \sum_{i=1}^{n}p_{i}\log [n_{i}-(\sum_{j=1}^{n} n_{j})]
\\&=-K \sum_{i=1}^{n}p_{i}\log[\frac{n_{i}}{(\sum_{j=1}^{n} n_{j})}]
\\&=-K \sum_{i=1}^{n}p_{i}\log p_{i}
\end{aligned}
為了方便，將$K$帶入$1$，最後得到entropy的式子
$\tag{1.1}\label{eq_1.1}H=-\sum_{i \in I}p_{i}\log p_{i}$

## Reference
1. Elements of Information Theory, 2nd edition
2. Introduction to data compression, 3rd edition