2016年四月三十日是克勞德·艾爾伍德·香農（claude elwood shannon）的一百周年誕辰。雖然香農被學術屆尊為資訊時代之父，聽說過這位科學巨人名字的想必比知道宋仲基的人少得多。不過不管你們信不信，要是沒有香農，到今天咱們應該還沒有見過手機或internet，也沒有用過微信或facebook，更不能在網上看韓劇。
香農是美國數學家、資訊論的創始人。1948年，香農發表了《通信的數學理論》文章，提出了資訊熵的概念，并建立了資訊論。這篇文章奠定了香農“資訊論之父”的地位。後來，香農在1949年繼續發表了《噪聲下的通信》。幾十年來，人類科技在數字化、智能化、網絡化等的推動下經曆了一波又一波通信、資訊革命。數十年之後，在資訊流、物質流的社會中，香農的論著依然閃爍着智慧之光，并将照耀人類社會今後的數個世紀。
在學術圈子裡，人們往往對香農高山仰止。南加州大學（university of southern california) 電子工程系教授巴特·嗑死磕（bart kosko）說：愛因斯坦相對論之革命性在于它颠覆了之前的牛頓力學，而香農資訊論之革命性在于它前無古人—— 香農對資訊的認知開人類之先河，沒有什麼擋在前面需要被颠覆的；香農提出了全新的數學工具，就是所謂的資訊論，并用這個工具回答了人類從未思考過的問題。在這個意義上，香農的發現像牛頓的引力定律一樣基本。
克勞德·艾爾伍德·香農（claude elwood shannon ），1916年4月30日—2001年2月26日。
1948年，香農（claude shannon）在貝爾實驗室發表論文《通信的數學理論》。文章中提出的數學工具構成了資訊論的骨架。香農證明了信源編碼的極限是信源的熵，信道編碼的極限則是信道容量。
倚天劍一出，天下皆驚。而為達到香農預測的信道編碼的極限——信道容量，人類卻花費了半個世紀掙紮。本篇文章試圖用最少的數學科普一下資訊論裡最基礎的概念——熵（entropy）。
“二十個問題”遊戲
先從一個貌似不相幹的西方曾經流行的遊戲，“二十個問題”（the twenty-question game) 說起。遊戲是這樣的。俺心裡想一樣東西，你可以問俺二十個問題，然後猜俺心裡想的東西。你的問題必須是“是不是”這種形式的。比如，這個東西是不是可以放進冰箱裡？這個東西是不是活的？這個東西是不是能吃？諸如此類。對于你問的每一個問題，俺必須如實地回答“是”或者“不是”。你在二十個問題之内猜到了我想的東西就算赢。
這個二十個問題的遊戲曾經很受歡迎，還被做成過電子玩具。
這個遊戲的關鍵是在于如何有效地問你的問題。如果你問“明天是不是下雨”，那你肯定腦子進水了，可以不用往下看了。如果你第一個問題問的是“這東西是不是 iphone 6”，這樣的問法顯然也效率不高，因為俺一旦說“no”，你隻從大量的可能性中排除了一種可能，還是要面對剩下巨大的猜測空間。
這個遊戲可以大緻等價于這樣一個數字遊戲。假設m是個大于1的正整數，俺倆在玩遊戲之前就商議确定好。俺在1到m之間任意想一個整數，你的任務是用最少的“是不是”形式的問題問出這個數是多少。
對于這個數字版的“二十個問題”遊戲，聰明的寶寶都會發現類似這樣的結論：m的數值越大，需要的問題越多。但愛鑽研的同學可能會想到另一個問題：對于一個給定的問問題政策，所需問題的“多”或“少”又是用什麼來衡量的呢？比方說，m=8，而你的問法是依次問如下問題：“這個數是不是1”，“這個數是不是2”，“這個數是不是3”，一直到“這個數是不是7”（如果問完“這個數是不是7” 你覺得還需要問“這個數是不是8”的話，那請你去看韓劇吧）。在這種情況下，如果俺想的數字是1，你隻需要一個問題就可以知道答案；而如果俺想的數字是8，你必須在問完7個問題之後才能知道答案。換句話說，即使問問題的政策确定，因為俺心裡那個神秘數字的不确定性，你所需要的問題數目也是不确定的。是以我們需要把這個數字版“二十個問題”遊戲更準确地描述出來，或者說，把在什麼意義上“最少”定義出來。
随機變量
随機變量描述的是一個随機實驗可能出現的結果以及每種可能結果的可能性，也就是機率。先看一個例子。
例［老千擲硬币］假設某老千每次投擲硬币的結果有1/3可能性出正面，2/3的可能性出反面。那麼擲一次硬币就是一個随機實驗，擲硬币的結果就是一個随機變量，我們這裡記作大寫的 x。如果把正面記作1，反面記作0，那麼這個随機變量 x 可以通過一個函數p(x)來描述：函數的變量 （小寫的）x 的取值範圍是集合{0,1}，這個集合此後記作 s；函數在0和1的取值分别為：p(1)=1/3，p(0)=2/3。
從這個例子可以看出，一個随機變量 x 無非是通過在某個集合s上定義的一個函數p(x)來描述的，而這個函數不能取負值，而且必須在對其變量 x 求和的時候結果為1（在老千擲硬币的例子中即：p(0)+p(1)=1)。這個函數通常被稱為随機變量x的機率分布。
當然，同樣是擲硬币，可以定義出很多不同的随機變量（即不同的機率分布函數p(x)）來。普通人擲硬币對應的随機變量基本就是p(0)=p(1)=1/2。賭神擲硬币對應的随機變量可能是p(0)=1, p(1)=0。
生活中的随機變量比比皆是。比如，在擲骰子的時候，骰子擲出的結果這個随機變量對應于一個定義在s={1,2,...,6} 上的機率分布函數 p(x)，通常認為p(1)=p(2)=...=p(6)=1/6。再比如明天會不會下雨（天氣預報不準的啦），會有幾個人給俺這篇吐血之作點贊或轉發（不曉得多少人更喜歡韓劇的啦）這些不确定的事情裡都可以定義出随機變量來。記得不知道哪一位偉人曾經說過，“随機變量是到處都有的。對于我們的腦袋，不是缺少随機變量，而是缺少發現。”
在前面說的那個數字版“二十個問題”遊戲中，俺心裡想的神秘數字對你來說也是一個随機變量，它的機率分布p(x) 是定義在s={1,2,...,m} 上的函數。如果我選數字是“完全随機的”，那麼，這個函數就是p(1)=p(2)=...=p(m)=1/m。這種分布通常被稱為均勻分布。當然，取決于俺按什麼偏好選數字，這個函數也可以取其他形式：如果俺就是喜歡2，也許俺會以更高的機率取2。
随機變量的均值
假設有個随機變量 x，它的取值範圍 s={1, 2, …, m}，它的機率分布函數是某個定義在s上的函數 p(x)。那麼這個随機變量的均值 （更文化點的說法叫數學期望值）就是這樣一個東東：
1*p(1)+2*p(2)+3*p(3)+ … +m*p(m).
在上面老千擲硬币的例子中，随機變量 x 的均值就是 1*(1/3)+0*(2/3)=1/3。簡單吧。
很多同學可能都有直覺的認識，能感覺到如果把産生這個随機變量 x 的随機實驗做很多次，把得到的數字取平均，那麼這個平均數差不多就是 x 的均值。這個概念，叫做大數定理，跟俺要講的熵有着本質的聯系。
獨立随機變量
很多時候俺們關心的不止一個随機變量，而是很多随機變量。比如，俺們同時關心兩個随機變量 x 和 y，x 的取值範圍是 {1, 2}, y 的取值範圍是 {1, 2, 3}。那麼俺們可以把這兩個随機變量看作一個随機變量對，寫作 （x, y）, 而把它的取值範圍了解為所有可能的（x，y）取值的組合，也就是 {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}。把這個集合叫作s，那麼這對随機變量就是通過一個定義在s上的機率分布函數 p(x, y) 來描述的。 當這個随機變量對的分布滿足 p(x, y)=p(x)p(y) 的時候，俺們就稱這兩個随機變量是互相獨立的。
p(0, 0) = p(0)p(0) = (2/3)(2/3)=4/9
p(0, 1) = p(0)p(1) = (2/3)(1/3)=2/9
p(1, 0) = p(1)p(0) = (1/3)(2/3)=2/9
p(1, 1) = p(1)p(1) = (1/3)(1/3)=1/9
獨立随機變量的概念當然可以推廣到更多的随機變量上。如果有 n 個随機變量，它們的取值無非就對應了一個長度為 n 的序列。所有這樣序列的集合就是這組随機變量的取值範圍。如果這些随機變量是互相獨立的，那麼每個序列出現的機率無非就是把這個序列中每個數出現的機率乘在一起。比如，上面的老千連續擲了10次硬币，那麼出現1101011110的機率就是
(1/3)(1/3)(2/3)(1/3)(2/3)(1/3)(1/3)(1/3)(1/3)(2/3)=(1/3)^7 * (2/3)^3
均值和大數定理
大數定理的英文是 the laws of large number, 它的中文翻譯通常是“大數定律”而不是大數定理。
定律或是英文裡的 law 都是指不需要證明但可以被驗證的理論假設。比如牛頓的萬有引力定律。從數學上說，不需要證明就被接受的假設被認為是公理。但是這個大數定理并非公理，它是被嚴格證明出來的（證明也不複雜，隻要用馬爾可夫不等式或切比曬夫不等式就行了），是以準确的數學語言應該叫它“定理”。管他叫“定律”會讓人以為這個東東就是假設出來的公理，進而産生歧義，當年也不知道誰這麼沒涵養管它叫“law”。是以，不管你們服不服，俺都要管它叫大數定理。
大數定理大概說了這樣一個意思。假設有某個随機實驗會産生一個随機變量 x。如果你重複做這個随機實驗 n 次， 你就會得到一個随機變量序列 x1, x2, x3, …, xn。這裡假定這些随機變量互相獨立（即這些随機實驗互不影響）而且 n 是個很大的數（比如，一萬，十萬，百萬），那麼把這 n 個數加起來除以 n （即取平均），得到的數 （ 即 (x1+x2+…+xn)/n ）幾乎總是很接近随機變量 x 的均值。
咱們用老千擲硬币的例子先看看大數定理到底說了些啥子嘛。假設那個老千擲了 n 次硬币，那麼他就得到了 n 個在{0, 1} 裡取值的數。因為這 n 個數都是随機的，這 n 個數的均值當然也是個随機變量，就是說也有一個機率分布函數，有一定的不确定性。大數定理告訴俺們，當 n 很大的時候，這 n 個數的平均值“幾乎總是很接近”1/3。“幾乎總是”和“很接近”是可以在數學上嚴格定義的，套一下切比曬夫不等式得出下面這些“至少有”的結論：
當 n=1000 時，至少有 91.1% 的機率這個平均值很接近1/3。
當 n=10000 時，至少有 99.1% 的機率這個平均值很接近1/3。
當 n=100000 時，至少有 99.9% 的機率這個平均值很接近1/3。
如果把“很接近1/3”了解為跟 1/3 相差不到 0.02，那麼：
當 n=1000 時，至少有 44.4% 的機率這個平均值很接近1/3。
當 n=10000 時，至少有 94.4% 的機率這個平均值很接近1/3。
當 n=100000 時，至少有 99.4% 的機率這個平均值很接近1/3。
當 n=1000000 時，至少有 99.9% 的機率這個平均值很接近1/3。
現在展開你想象的翅膀，你應該看到當 n 變成無窮大的時候，這個平均值就不再是“幾乎總是很接近1/3”，而是“就是1/3”了！
老千擲出的序列當然是随機的、不确定的、沒有規律的。這個序列的平均數雖然也在1/3周圍随機跳動，但卻随着 n 的增大越發确定起來。當n很小、她就在你跟前的時候，變化多端、捉摸不定的她讓你無法看清；當 n 增大的時候，她漸行漸遠，但她在風中顫動的身影卻在你記憶的相機裡慢慢聚焦，越來越清晰；直到她消逝在無限的遠方，她竟定格成一幅永恒而又無比真切的畫面……
“二十個問題”遊戲的準确規則及特例
用機率論武裝一下之後，同學們應該已經認識到，在“二十個問題”遊戲中俺心裡想的神秘數字其實就是一個随機變量 x。我們可以假設它的取值範圍s={1, 2,…, m} 和機率分布函數 p(x)都 已知。當然在實際情況下我們未必真知道 p(x)，但往往可以大緻估計這個函數。如果對這個分布函數我們一無所知，我們不妨認為 p(x) 是個均勻分布。
對于任意一個給定的問問題政策，如果俺心裡的神秘數字是 x，我們把所需的問題個數記作 l(x)。比如 m=8，而我們用前面提到的那個從1問到7的政策問問題，我們就會得到：
l(1)=1, l(2)=2, l(3)=3, l(4)=4，
l(5)=5, l(6)=6, l(7)=7, l(8)=7。
（對，l(8)=7，俺沒敲錯。）
因為俺心裡想的是個随機變量 x，在這個政策下所需要的問題數目 l(x) 就也是個随機變量。這個随機變量 l(x) 也有一個分布，在知道 p(x) 的前提下，如果想算也是可以算出來的。但是俺懶得算它。
既然 l(x) 是個随機變量，一個最自然的方式定義這個政策所需要的問題個數就是用這個随機變量的均值，或者說用平均所需要的問題個數。如果你的數字直覺好，應該可以看到，即使不求 l(x) 的分布，這個随機變量的均值其實就是
l(1)*p(1)+l(2)*p(2)+…+l(m)*p(m).
用 l(x) 的均值定義一個問問題政策所需要的問題個數除了“自然”，還有什麼實體意義嗎？當然！前面的大數定理告訴咱們，如果你用這個政策玩這個遊戲很多次，你所用問題個數的平均值“幾乎總是很接近”l(x) 的均值。而當你玩了這個遊戲無數次之後，你平均每次用的問題數就正好是這個 l(x) 的均值。
由此可見，如果俺們準備玩這個遊戲很多次，那麼用 l(x) 的均值定義所需要問題的個數，用金星老師的話說就是一個動作兩個字：完美。
至此，已經确定這個“二十個問題”遊戲的準确規則，即：你要設計一種問問題的政策，當用這個政策跟俺玩很多次（更準确的說，無數次）這個遊戲之後，平均每次用的問題個數要越少越好！換句話說，我們希望尋找一個最好的問問題政策，同時确定最少需要多少個問題（平均意義上）。
其實在一些特殊的情況下，确定最優的問問題政策和最少需要的問題個數并不困難。
考慮這樣一個特例：俺心裡的神秘數字 x 的取值範圍是 s={1, 2, …, 8}，而且 x 的機率分布函數是個均勻分布。那麼最優的問問題方法就是所謂的“二分法”：每問一個問題要把這個神秘數字的可能範圍縮減一半。比如這樣的問法：
問題1: 把集合 {1, 2, …, 8} 分成左右兩份，左邊的是 {1, 2, 3, 4}, 右邊的是 {5, 6, 7, 8}。然後問：你想的數是不是在左邊啊？
問題2: 根據俺的答案，你可以确定這個神秘數字隻剩下四種選擇。你再類似地把四種選擇分成左右兩份，然後問：你想的數是不是在左邊啊？
問題3: 根據俺的答案，你現在可以确定這個神秘數字隻有兩種選擇，再把它們一個放左邊，一個放右邊。你再問：你想的數是不是在左邊啊？
如此問完三個問題，你一定知道了俺的神秘數字。相信你的直覺也應該告訴你，這就是最優問法！那麼在這個例子裡，所需的最少問題個數就是 3。從咱們用每個問題把猜測空間一切兩半的問法，同學們應該也已經認識到，這裡得出的最少問題數 3 正是因為 8=2^3, 或者說，2= log 8. （本文中所有的對數操作均以2為底數）。
在這個例子中有個現象也值得注意一下：不管俺心裡想的是個什麼數字，使用二分法所需的問題數字都是3，一個完全确定，毫無随機性的數字。
這個特例顯然可以推廣：如果神秘數字 x 的機率分布函數是在 2^k 種可能性上的均勻分布，那麼“二十個問題”遊戲的最優政策可以通過二分法實作；在這種政策下，不論神秘數字是什麼，問出它所需要的問題數都是 k，是以所需要的平均問題數也是 k。
當然，這個二分法隻适合于這樣的特例，當神秘數字的可能性總數不是2的多少次方的時候，或者當神秘數字的分布不均勻的時候，這種問法顯然不是最優的。這個問題任意形式的最優解法曾讓一個叫大衛.霍夫曼（david huffman）的年輕學生在1951年一夜成名。不過，那已經是在香農提出資訊論三年之後了。
在香農獨特的視角裡，這個問題并不至關重要。在想象中，當香農看到滿屋子小朋友們叽叽喳喳地玩這個遊戲的時候，他笑了笑，說：你們慢慢玩吧。然後他點起一支煙，凝視着窗外的遠方。在落霞與孤鹜齊飛的秋色裡，他看到了這個遊戲的另一種設計。
“二十個問題”遊戲攢着玩和資料壓縮
既然用 l(x) 的均值定義所需要問題的個數依賴于把這“二十個問題”遊戲玩很多次，那麼考慮一下這個遊戲的一個變種，就是把這很多次遊戲攢起來一起玩：俺拿出一張很長很長的紙條，然後随機想 n 個互相獨立的神秘數字，x1, x2, …, xn （每個數字的分布都是同一個定義在 s={1, 2, …, m} 上的機率分布函數，p(x)）。俺把這些數字一個一個地寫到紙條上。這裡 n 很大很大，是以紙條很長很長。然後你再來問俺“是不是”台或一百台電腦來。你問俺的問題要是計算太複雜，俺也可以去搬電腦來算。總之，咱們不用管計算有多複雜，俺倆都有無限的計算能力。在這個攢着玩的“二十個問題”遊戲中，怎樣的問問題政策才最優呢？最優的政策所需要的平均問題數目又是多少呢？
暫且先不讨論這個問題的答案，咱們先審視一下這個新的遊戲設計的應用意義吧。
想象一下， 俺寫在紙條上的序列其實是俺剛寫好的長篇小說（俺寫下的每一個數其實對應于新華字典裡的一個字），又或者俺寫在紙條上的序列其實對應于俺長期夜觀星象的結果，記錄了不為人知的宇宙奧秘（俺寫的每個數字都是對觀測到的宇宙狀态的描述）。在你問俺問題的時候，俺的回答将是一個長長的由yes/no 組成的序列。如果把 yes 記作 1，no 記作 0，俺的回答其實就是一個0/1組成的序列。
一個可以取 0/1 兩個值的變量，或者一個可以儲存 0/1 兩種不同狀态的存儲單元，就是人們常說的比特（bit）。是以俺的回答其實就是一個比特序列。你希望用最少的問題就等同于要求這個比特序列最短，或者說要求用最少的比特數表示俺紙條上的内容。這個問題其實就是通信中的資料壓縮問題！
資料壓縮，又叫“信源編碼”，大約是幹這樣一件事。假設有個資訊源，就是一個能不停往外蹦資訊的東西，比如一直在想神秘數字的俺，夜觀星象的俺，寫小說的俺，等等等等。資訊源産生的資訊從數學上說就是一個随機變量序列（更有文化的說法叫随機過程）。這個随機變量序列可以有很多種形式，最簡單形式就是其中的随機變量都互相獨立而且服從相同的分布。對這個資訊源進行資料壓縮包括了兩個環節，編碼和解碼。編碼就是把從資訊源蹦出來的随機序清單示成比特序列，而且越短越好；解碼就是從比特序列中還原出資訊源蹦出來的随機序列。資料壓縮可以大幅度降低資料存儲和通訊需要的資源，已經是現代通信技術的一個重要組成部分。
現在回到“二十個問題”遊戲。如果這個遊戲一個一個分開玩，其實就是在資料壓縮的時候，對資訊源裡蹦出的每個随機變量單獨做壓縮。如果這個遊戲攢 n 個一起玩，其實就是對随機序列中的 n 個随機變量同時進行壓縮。顯然，對每個随機變量單獨進行壓縮一定不會比對整個随機序列同時做壓縮效率更高 （這裡的效率是用平均每個随機變量壓縮後的比特數來衡量的，比特數越低，效率越高）。這裡的道理是這樣的：比如俺倆攢 n 個“二十個問題”遊戲一起玩，但你設計問題的時候，每個問題隻是針對序列中的一個随機變量，而不是針對整個序列。這樣的問問題政策顯然等同于把每個遊戲分開玩。也就是說， 這個遊戲一個一個分别玩可以認為是攢起來一起玩的一種特例。因而分别玩能達到的效率，攢起來玩也可以達到。因為同樣的道理，如果這個遊戲攢 2n 個一起玩，其效率也一定不比攢 n 個一起玩低。也就是說，為了提高效率，n 應該越大越好。
那麼攢起來玩的效率到底最高可以達到多少呢？或者說，對一個給定的資訊源，平均每個蹦出來的随機變量最少需要多少個比特來表示呢？這個數字通常跟序列的長度 n 相關，而且對于任意一個給定的 n，即使俺們能夠确定最優的壓縮方法，精确地确定這個數字也是一件很棘手的事。不過既然俺們已經認識到 n 越大越好，那不妨考慮 n 取無窮大吧。
當 n 取無窮大時，如果俺們能夠計算出資訊源裡平均每個蹦出的随機變量最少需要多少比特來表示，這個數字不僅标記了最優的壓縮效率，它同時還有着更深刻的實體意義：它跟序列的長度 n 無關，也跟編碼方法無關；換言之，這個比特數隻取決于資訊源本身（即 随機變量x或其分布 p(x)）。因為這個比特數是由最優編碼／解碼方法實作的，它同時說明了兩件事：
1. 隻要解碼端接收到的平均比特數不到這個數字（平均到每個随機變量上），不論用什麼編碼／解碼方法都一定無法重建資訊源裡蹦出的随機序列。
2. 隻要解碼端接收到的平均比特數超過這個數字，就一定有一種編碼／解碼方法可以使解碼端重建這個序列。
這就是說，在平均意義上，你一定需要這麼多比特來表達資訊源裡蹦出的每一個随機變量，而且隻要這麼多比特就夠了！是以，這個比特數實際上就标注了這個資訊源在以什麼樣的“速率”釋放“資訊”，或者說标注了這個資訊源裡蹦出的每個随機變量平均包涵了多少“資訊”！
下面俺們就來看看是否可以導出這個最小比特數。
最小比特數
還是二十個問題攢着玩吧。不過這次俺也不去想什麼随機數了。俺就把之前例子裡的那個老千找來，讓他躲在俺身後不停地擲硬币。俺就把他擲出的0/1結果寫在紙條上。等俺寫完 n 個數的時候，就讓你開始問問題。前面說過，這無非就是把這個老千擲硬币的結果當作一個資訊源，對這個資訊源做壓縮。
因為 n 很大很大，讓我們先回顧一下大數定理的情懷：
老千擲出的硬币序列的平均值幾乎總是很接近1/3。
根據俺之前對這句話不辭勞苦的解釋，這句話也可以換一種說法，而且這種說法很重要（重要的事情說三遍！）
老千擲出的序列幾乎可以肯定有差不多 n/3 個1 和 2n/3 個0！
這個重要結論很容易推廣到擲硬币之外的任意随機變量：假設随機變量 x 是通過一個在集合 s={1, 2, …, m} 上定義的機率分布函數 p(x) 描述的。那麼當俺們産生 n 個互相獨立的這樣的随機變量的時候，如果 n 是個很大的數字而 a 是 s 中的任意一個數，那麼：
産生的随機序列幾乎可以肯定有差不多 n*p(a) 個 a ！
也就是說，雖然得到的序列本身是随機的，不确定的，但是當 n 很大的時候，這個序列的組成“幾乎”是“差不多确定的”！ 而且可以想象，當 n 無窮大的時候，這裡的“幾乎”和“差不多”都可以删去！
在老千擲硬币這個例子裡，如果一個硬币的序列有差不多 n/3 個1 和 2n/3 個0，那麼俺就管這種序列叫“典型序列”。在更普遍的意義上，相對于一個在s 上定義的分布 p(x)，一個由 s 裡的數字組成的長度為 n 的序列俺也管它叫典型序列，如果 s 裡的每個數 a 在這個序列中出現了差不多 n*p(a) 次。在典型序列定義中的“差不多”是差多少？呵呵，跟前面的邏輯一樣，如果 n 很大，差不多就是差一丁點，如果 n無窮大，差不多可以是“一點不差”！
那麼上面重要的說了三遍的話用這個語言重新說，就是：
老千擲出的序列幾乎可以肯定是典型的！
當 n 無窮大的時候，這句話裡的“幾乎”當然也是可以删掉的。也就是說，在 n 無窮大的時候，不典型的序列根本不會出現！那麼，你問問題的時候豈不是隻需要針對典型序列問問題就行了？
正是如此！
那咱們看看典型序列一共有多少個。把這個要算的數記作 t。
首先注意一下每個典型序列有多大的機率被老千擲出來。因為每個典型序列“差不多”由 n/3 個1 和 2n/3 個0 組成，而這個序列中的所有随機變量又是互相獨立的，那麼，每個典型序列被擲出來的機率“差不多”就是 (1/3)^(n/3)*(2/3)^(2n/3)。不知道同學們注意到沒有，每個典型序列被擲出來的機率“差不多”都是這個數。同時注意到隻有典型序列才可能被擲出來，也就是說，所有典型序列出現的機率之和“差不多”就是 1。這樣俺們就可以得出，典型序列的數目 t “差不多”就是 1 除以每個典型序列出現的機率，也就是
1/((1/3)^(n/3)*(2/3)^(2n/3)) = (1/3)^(-n/3)*(2/3)(-2n/3).
針對這 t 個序列問問題，就“差不多”等同于俺跟你玩一次這樣的“二十個問題”遊戲：俺從{1, 2, …, t} 裡取一個數，而且這個數服從均勻分布；然後你問俺“是不是”問題來猜這個數。那麼你最少需要多少問題呢？ 現在回頭找到之前讓你們用紅筆圈出的結論：最優解是二分法；你最少需要的問題總數是 log t！而且不管俺取的是哪個數，你都需要這麼多問題！
認真的同學可能會叫闆說，哎，這個 t 也未必是 2 的整數次方啊，二分法能用嗎？！嗯，這個問題不錯。但可以這樣想，隻要把 n 弄得足夠大，總可以讓 t 非常接近 2 的某個整數次方。而且，即使 t 真的不是 2 的整數次方，還可以換一個角度得到我們後面要得到的結論，比如，一定存在一個整數k 使得 t 是在 2^k 和 2^(k+1) 之間。。。。總之，當 n 無窮大的時候，淩亂的世界都變整齊了，這個問題不再是問題了。
這個最少問題數 log t 是用來問這個長度為 n 的硬币序列的。平均到每次擲硬币，平均需要的最少問題數就是 （log t）／n。稍微整理一下這個表達式就應該可以看到，這個數字正好等于
- (1/3) log(1/3)- (2/3) log (2/3)。
這也就是壓縮這個“老千擲硬币”資訊源所需要的最少比特數。
把這種推演用到任意資訊源。如果一個資訊源往外蹦的随機變量都獨立而且服從同一個定義在s={1, 2, …, m} 上的分布p(x)，那麼以下結論依次成立。
資訊源裡蹦出的随機序列幾乎可以肯定是典型的！
每個典型序列出現的機率差不多就是 p(1)^(np(1))*p(2)^(np(2))*…*p(m)^(np(m))!
典型序列的個數 t 差不多就是p(1)^(-np(1))*p(2)^(-np(2))*…*p(m)^(-np(m))!
壓縮這個資訊源蹦出的每個随機變量平均所需要的最少比特數就是 (logt)/n！
這個數字 (logt)/n 就等于：
-p(1)log p(1) - p(2) log p(2) - … - p(m)log p(m).
這個數字，就是熵。
熵的實體意義
從熵的表達式看，熵是通過一個機率分布函數 p(x) 來定義的。因為機率分布函數 p(x) 都對應于它所描寫的随機變量 x，是以俺們也可以認為熵是對随機變量 x 的某種特性的度量，而把它記作 h(x)。從壓縮的角度講，熵值 h(x) 是對産生随機變量 x 的資訊源編碼所需要的平均最小比特數，或随機變量 x 中固有的平均資訊量。
如果随機變量 x 是在 s={1, 2, …, m} 裡取值，那麼可以證明，熵值 h(x) 的取值必定在 0 和 logm 之間。當随機變量 x 在 s 上均勻分布的時候，h(x) 取最大值 logm；當 x 以百分之百的機率取 s 中的某個數值的時候，h(x) 取最小值 0。前者對應于“不确定性”最大的 x，而後者對應于“不确定性”最小的（即完全可以确定的）x。是以，也可以把熵值 h(x) 了解為對 随機變量 x 的“不确定性“（或“不可預測性”）的度量。
是以，随機變量所包含的“資訊量”和它的“不确定性”其實是同一個概念。一個随機變量越難以确定，它所包含的資訊量越多。這種認識對初次接觸熵的人來說或許不夠自然。但仔細體會一下，确實是有道理的。如果俺想告訴你的事你很容易猜到，或者說你不用問幾個問題就能知道，那俺要說的話對你來說就沒多少資訊量。
在熵的定義裡 －logp(a) 又是什麼實體意義呢？當然這個數字可以了解為 a 編碼所需要的比特數（在前面例子裡，我們能看到以1/8機率出現的事件，需要用3個比特來編碼）。換一個角度了解，－logp(a) 可以了解為 a 的“驚奇度”。一個出現機率極低的事件 a，比如世界末日，它一旦出現就會令人非常驚奇，是以對應的 －logp(a) 就會很大；而如果 a 出現的機率很大，它的出現就不會太令人吃驚，是以對應的 －logp(a) 就會很小。是以，熵值 h(x) 也可以了解為随機變量 x 的“平均驚奇度”。
用不确定性，資訊量，或平均驚奇度來了解熵，都隻是給它賦予一個直覺的解釋。平均最小編碼長度才是對熵的數學了解。但這種了解并不能展現出大數定理在熵的定義裡所起的決定性作用以及“二十個問題”遊戲必須攢着玩才能實作最短問題數等于熵值的深刻認識。在大數定理的情懷下，熵值 h(x)還有另一個數學解釋： h(x) 是典型序列的總數随序列長度的“翻倍速率”。看，長度為 n 的典型序列總數 t 差不多是 2^(nh(x))；也就是說，每當序列長度 n 增加 1， t 就增大 2^(h(x)) 倍，或者說，翻倍翻了 h(x) 次。是以把熵了解為典型序列總數的翻倍速率才能真正展現熵的數學本質。
香農和熵
熵，或英文裡的entropy，本來源于實體中的熱力學，用來描寫系統的“混亂度”。香農在定義資訊熵的時候借用了這個詞。雖然俺經常夜觀星象，也能在夜空沒有霧霾的時候認出北鬥星，但對宇宙、相對論，或是熱力學，都一竅不通。是以俺就不試圖解釋實體熵和資訊熵的聯系了。
但在通信的範疇，熵是人類第一次對資訊有了數學的認識。人類剛剛開始研究數字通信的時候基本就是瞎子摸象，直到1948年香農在貝爾實驗室發表了那篇著名的文章，“通信的數學理論”。倚天劍一出，天下皆驚。香農一針見血地指出，通信的問題可以分解成兩個的問題，即信原編碼和信道編碼。信原編碼的目的是盡可能高效的表示資訊源，即資料壓縮；信道編碼的目的則是盡可能高效的讓資料可靠無誤地通過信道。在他1948年的文章裡，香農證明了信原編碼的極限是信源的熵，而信道編碼的極限則是個叫信道容量的東東，标注着信道可以支援的最大通信速率。（信道容量的概念是在熵的基礎上的對資訊論的進一步發展，故事更長，更精彩，不過俺還是不講了吧。）香農說，隻有當信源的熵低于信道的容量的時候，可靠的通信才可能實作；而且隻要在這個條件下，可靠的通信就一定可以實作！香農的證明是存在性證明，就是說，他告訴俺們： 反正這事兒一定可以實作，至于怎麼實作，你們自己想辦法吧。
信源編碼的問題很快被香農的追随者和逐漸解決。基于算術編碼(arithmetic coding)和 lz 編碼（lampel-ziv coding) 的信源編碼方法在上世紀七八十年代已經日漸成熟，實作了香農預測的壓縮極限并在實踐中被廣泛采納。而香農預測的信道編碼的極限，信道容量，卻花費了人類半個世紀掙紮。業外人士未必了解，對信道編碼的研究結晶了人類最高的智慧和前赴後繼的努力。然而香農預測的信道容量直到上世紀九十年代中葉才終于被實作。今天我們的手機裡也終于承載了香農在1948年的預言！
熵的提出是資訊論起點，也是人類對資訊認知的開始，而香農在他1948年文章裡提出的數學工具正是資訊論的骨架。在我們今天生活的資訊時代，香農和資訊論存在于我們的手機，我們的電腦，我們的電視，我們的藍光播放器，我們的internet，我們的facebook，我們的韓劇 ……
聖經創世紀說，在世界還是一片混沌漆黑的時候，上帝說，要有光。于是世界就有了光。
大約七十年前，當人們還在黑暗中摸索數字通信的時候，香農說，要有熵。于是，就開啟了資訊時代。
“香農的現代資訊論永不過時”
是否有人曾質疑過，随着科技的不斷發展，香農的資訊論有可能無法滿足現實的要求？答案是否定的。根源上講，資訊流、物質流組成了世界。隻要世界的根源還是資訊與物質，香農揭示的依舊是一個公理。即便發展到人工智能的今天，資訊依然是一切的基礎。業界來說，《通信的數學理論》是一篇20世紀少有的、對人類發展産生深遠影響的科學論著，可與牛頓力學相媲美。即便百年之後，我們依舊享用着這個理論來探索未知的世界。
基于香農資訊論綿延至今的技術成果:
奠定現代加密的理論基礎
20世紀60年代末開始了通信與計算機相結合，通信網迅速發展，人類開始向資訊化社會邁進。這就要求資訊作業的标準化，加密算法當然也不能例外。标準化對于技術發展、降低成本、推廣使用有重要意義。
我們都知道，美國fbi提出的資料加密标準des，以及最新圖靈獎得主斯坦福大學密碼學和網絡安全技術專家惠特菲爾德·迪菲（whitfield diffie）和馬丁·赫爾曼（martin hellman）提出的公鑰加密系統是現代密碼學的标志，是現代通信的基礎加密技術。不過，你也許不知道，這兩種标準或體制都以香農的資訊論為基本知道思想。
1949年，香農公開發表《保密系統的通信理論》一文，開辟了用資訊論來研究密碼學的新思路。這篇文章基于的理論是香農在1945年為貝爾實驗室所完成的一篇報告《a mathematical theory of cryptography》。論文發表後，香農被美國政府聘為政府密碼事務顧問。
des
des全稱為data encryption standard，即資料加密标準，是一種使用密鑰加密的算法。des設計中使用的兩個分組密碼設計原則：混淆（confusion）和擴散(diffusion)，其目的是抗擊敵手對密碼系統的統計分析。這就很好地提現了香農1949年的論文中所提出的設計強密碼思想：
組合（combine）概念：由簡單易于實作的密碼系統進行組合，構造較複雜的、密鑰量較大的密碼系統。shannon曾給出兩種組合方式，即權重和法和乘積法。 擴散（diffusion）概念：将每一位明文及密鑰盡可能迅速地散布到較多位密文數字中去，以便隐蔽明文的統計特性。 混淆（confusion）概念：使明文和密文、密鑰和密文之間的統計相關性極小化，使統計分析更為困難。
資訊論是研究和評估保密和認證系統的安全的重要工具，同時熵和資訊量也是研究和評估隐匿系統重要工具。
shannon曾用揉面團來形象地比喻“擴散”和“混淆”的作用，密碼算法設計中要巧妙地運用這兩個概念。與揉面團不同的是，首先密碼變換必須是可逆的，但并非任何“混淆”都是可逆的；二是密碼變換和逆變換應當簡單易于實作。分組密碼的多次疊代就是一種前述的“乘積”組合，它有助于快速實作“擴散”和“混淆”。
可以說，分組密碼設計中将輸入分段處理、非線性變換，加上左、右交換和在密鑰控制下的多次疊代，都在香農構造密碼的思想下指導進行。
公鑰加密系統
香農在1949年指出：
“好密碼的設計問題，本質上是尋求一個困難問題的解，相對于某種其它條件，我們可以構造密碼，使其在過程中的某點上等價于解某個已知數學難題。”
在此影響下，迪菲和赫爾曼提出了公鑰加密系統。
迪菲和赫爾曼提出的公鑰加密系統，其中的rsa、rabin、背包、elgamal、ecc、ntru、多變量公鑰等所有公鑰算法都是基于某個數學問題求解的困難性。
迪菲和赫爾曼的可證明安全理論就是在于證明是否可以将所設計的密碼算法歸約為求解某個已知數學難題。
破譯密碼的困難性，所需的工作量，即時間複雜性和空間複雜性，與數學問題求解的困難性密切相關。計算機科學的一個新分支——計算複雜性理論與密碼需的研究密切關聯起來了。
擴頻通信與調制解調
網絡化社會的今天，我們必定離不開電子計算機和通信。下面我們用通俗易懂的方式來講一下，我們今天孜孜以求的帶寬、wifi、藍牙、gps等與香農的關系吧：
根據香農（c.e.shannon）在資訊論研究中總結出的信道容量公式，即香農公式：
c=w×log2（1+s/n）
式中：c——資訊的傳輸速率，s——有用信号功率，w——頻帶寬度，n——噪聲功率，也就是說：
為了提高資訊的傳輸速率c，可以從兩種途徑實作，既加大帶寬w或提高信噪比s/n。換句話說，當信号的傳輸速率c一定時，信号帶寬w和信噪比s/n是可以互換的，即增加信号帶寬可以降低對信噪比的要求，當帶寬增加到一定程度，允許信噪比進一步降低，有用信号功率接近噪聲功率甚至淹沒在噪聲之下也是可能的。擴頻通信就是用寬帶傳輸技術來換取信噪比上的好處。
擴頻的出發點是加密，後來主要是用來減低幹擾，同樣是香農公式裡面提到的另一個因子信噪比，也可以得到高帶寬。簡單來說，所謂降噪就是，帶寬越寬，抗幹擾能力越強。但是，帶寬擴充上去了，信号功率就降低了，不符合市場經濟。是以現代通信不是要無限擴大帶寬，而是要找平衡點。基于這個思想，我們還在尋找這個平衡點。
資訊論與機器學習
如果前面說的還是過去和當下的影響，那麼接下來就不得不佩服香農的未來預示能力了。
香農是最早提出資訊智能化的學者之一。資訊論與人工智能之機器學習同為涉及計算機科學和應用數學等學科的分支領域，這兩門交叉學科在起源和應用上有很多相似之處。不過，看起來神乎其神的機器學習，主要還是借用資訊論的方法以此拓展理論研究和應用場景，比如關于分類計算上，借鑒于資訊理論來創造和改進學習算法。
資訊論中的一些度量也可以作為學習算法的度量。“學習就是一個熵減的過程”，學習的過程也就是使資訊的幹擾度下降的過程。比起傳統的經驗公式為基礎的機器學習，以資訊理論為基礎的機器學習也擁有無可比拟的優勢。
好吧來個具體一點的例子。上個月人機大戰中的alphago，其決策樹算法是戰勝人類的重要武器。那麼，據來自于nsf博士論文《 information theory and its relation to machine learning》所闡述，以互資訊作為學習準則，例如以應用資訊增益（歸一化的互資訊）構造最簡結構決策樹就是其中一種應用。這種基于資訊理論為學習準則的原理就是将無序資料轉變為有序資料，以資訊熵內插補點作為測量尺度來評價轉換效果。
如今也有不少研究者猜想，在機器學習中，所有學習目标的計算表征都是可以用熵函數的優化來描述或者解釋的。這個猜想給了機器學習界一個很好的研究着力方向。
原文釋出時間為：2016-05-01
本文來自雲栖社群合作夥伴“大資料文摘”，了解相關資訊可以關注“bigdatadigest”微信公衆号