Wednesday, October 4, 2017

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...

No comments:

Post a Comment

ubuntu on x1c carbon 6 th

此篇網誌將會記錄 x1c 使用心得以及問題 @ 12/2018 拿到windows 10 pre-installed x1c 6th 壓縮容量 改bios開機設定 安裝 ubuntu 18 from usb @ issue 1. 電量問題 co...