Information Theory (資訊理論)

這篇文章會記錄我對 information theory 的了解。

＝＝＝＝ Entropy ＝＝＝＝

先來討論所有機率是平均分佈

A 有一個硬幣，正面反面出現機率各一半

A 擲了一次硬幣 現在他想把結果告訴 B

但是A 和 B 不可以直接溝通 只能透過其他方式

這些方式有共通點, 只能有兩個狀態

例如：聲調高低, 顏色深淺

我們可以把兩種狀態用 0, 1 來表示

在硬幣的例子，我們可以用 0 代表反面,  1 代表正面

A 擲了2次硬幣 2 次都是正面。

A 現在只要用兩個 1 就可以讓 B 知道結果了

現在我們可以換一個角度想兩種狀態的意義，

A 給 B 0 或 1

可以想成 B 可以問 A 一個問題

A 會回答 0 或 1 代表 是或否

這個例子B 問 A 1個問題就可以知道 1 次結果 

2 個問題 2 次結果

現在考慮骰子 x  = [1, 2, 3, 4, 5, 6], p(x) = 1/6

我們一樣只有兩種狀態

A 丟了 6

現在 B 需要什麼資訊才能知道 A 拿到 6 呢？

a,  B 可以問 A, 是 1,  是 2 ,  是 3 ... 是6?

考慮最壞結果

B 必須問 A 6 個問題

但是  B 也有可能第一次就問到正確結果

 B 實際上不能確定他到底要問幾次才知道

b.  B 可以問A：這個數字是否是 {1, 2, 3} 

這樣子的話我們一次可以把一半的可能去除

1 -> 01

2 -> 001

3 -> 000

4 -> 11

5 -> 100

6 -> 101

由於 log2(6)  = 2.58 不是整數，

我們需要 3 個問題 來確定數字是什麼

a, b 的差別：

假設丟的次數很大

a. 

我們可以想成我們平均需要 3.5 個問題可以問出結果

b.

在 b 情況 3 個問題就可以得到 A 丟的結果

當次數很大時

我們考慮長度

2 * (2 * 1/6) +  4 * (3*1/6) = 2.667

這裡可以看到我們算出來的平均長度會比log2(6) 大

2.667  > log2(6)  = 2.58


to be continue...