概率論在計算機科學中的應用有哪些？

01-21

計算機學院的學生大二學了概率論與數理統計，但是整本書都在從概念講起，如何一步步地證明一個又一個的定理，然後以一些例題來應用之。
但是至今沒有看出它和計算機科學的關係在哪裡？或者說是現在學的知識還太粗淺，還沒有到應用它的時候？
還有一個問題是：為什麼這些學科在高等教育的安排中不結合實際的專業學科，比如為了解決xxx問題我們必須以學習概率論中的xxx為基礎，而不是現在的作為基礎課來學習，等到遇到具體問題才發現原來答案在之前學過的東西里，這個順序不是很「反人類」（一般探究事物的過程）嗎？
//題主才疏學淺，各位大神求輕噴

實現WinZip

應用還是很廣泛的，舉個存儲的例子。

磁碟錯誤的統計分析，以及如何建模。很多公司會分析自家產品的磁碟錯誤（Google、Facebook、NetApp都干過這種事），得到磁碟壽命、扇區錯誤的分布。有了這些分布後，研究人員就可以建立數學模型去分析各種糾錯碼的可靠性。

統計語言模型，用於語音識別，機器翻譯，拼寫糾錯等。

https://zh.wikipedia.org/wiki/語言模型

隱含馬爾可夫模型，用處就太多啦～機器學習，語音，語言處理等。

EECS應用概率論

轉自：EECS應用概率論 (豆瓣)

內容簡介 · · · · · ·

本書精心選取了6個當前熱門的科技應用：谷歌PageRank演算法、鏈路復用技術、數字鏈路通信、追蹤預測、語音識別和路線規劃，並通過講述概率論在不同應用中的作用來詳細介紹基礎的概率知識以及概率論中的重要概念，包括馬爾可夫鏈、大數定律、中心極限定理、假設檢驗、最小方差預測等。

作者簡介 · · · · · ·

作者簡介：

Jean Walrand

在美國加州大學伯克利分校取得EECS博士學位，自1982年以來一直在該校任教，研究興趣包括隨機過程、排隊論、通信網路、博弈論和互聯網的經濟性。Walrand教授是比利時－美國教育基金會和IEEE的研究員，曾經榮獲蘭徹斯特獎、萊斯論文獎、IEEE小林宏治獎和ACM測量與評估專業卓越成就獎。

譯者簡介：

黃隆波

清華大學交叉信息研究院Tenure-track助理教授，博士生導師，中組部「青年千人計劃」入選者。於2011年在美國南加州大學電子工程系獲得博士學位，於2011年到2012年在美國加州大學伯克利分校電子工程與計算機科學系擔任博士後研究員。在美國麻省理工學院信息與系統決策實驗室（LIDS）、法國貝爾實驗室與香港中文大學網路編碼研究所（INC）等機構擔任訪問學者與訪問教授，共發表IEEE/ACM頂級雜誌和會議論文40餘篇，曾獲邀為多個IEEE/ACM頂級期刊審稿並多次擔任IEEE/ACM會議程序委員。

目錄 · · · · · ·

第1章　PageRank—A　　1

1.1　模型　　1

1.2　馬爾可夫鏈　　3

1.2.1　定義　　3

1.2.2　n 步後的分布和穩態分布　　4

1.3　分析　　5

1.3.1　不可約性和非周期性　　5

1.3.2　大數定律　　5

1.3.3　長期時間比例　　6

1.4　擊中時間　　7

1.4.1　平均擊中時間　　7

1.4.2　擊中另一狀態之前命中某一狀態的概率　　8

1.4.3　馬爾可夫鏈的首步方程　　9

1.5　小結　　10

1.6　參考資料　　10

1.7　練習　　11

第2章　PageRank—B　　15

2.1　樣本空間　　15

2.2　投擲硬幣的大數定律　　17

2.2.1　依概率收斂　　17

2.2.2　幾乎處處收斂　　18

2.3　獨立同分布隨機變數的大數定律　　20

2.3.1　弱大數定律　　20

2.3.2　強大數定律　　21

2.4　馬爾可夫鏈的大數定律　　22

2.5　期望的收斂　　23

2.6　大定理的證明　　25

2.6.1　定理1.2(a)的證明　　25

2.6.2　定理1.2(b)的證明　　26

2.6.3　周期性　　27

2.7　小結　　29

2.8　參考資料　　29

2.9　練習　　30

第3章　多路復用—A　　31

3.1　鏈路共享　　32

3.2　高斯隨機變數與中心極限定理　　34

3.3　多路復用與高斯分布　　37

3.4　置信區間　　37

3.5　緩衝器　　39

3.6　多址訪問　　43

3.7　小結　　44

3.8　參考資料　　45

3.9　練習　　45

第4章　多路復用—B　　47

4.1　特徵方程　　47

4.2　中心極限定理的證明（概要）　　48

4.3　N(0,1)的高階矩　　49

4.4　兩個獨立同分布於N (0,1)的隨機變數平方和　　50

4.5　特徵函數的兩個應用　　51

4.5.1　泊松分布作為二項分布的近似　　51

4.5.2　指數分布作為幾何分布的近似　　51

4.6　誤差函數　　52

4.7　自適應多址訪問　　53

4.8　小結　　55

4.9　參考資料　　55

4.10　練習　　55

第5章　數字鏈路—A　　57

5.1　檢測與貝葉斯準則　　58

5.1.1　貝葉斯準則　　58

5.1.2　最大後驗概率（MAP）與最大似然估計（MLE）　　59

5.1.3　二元對稱信道　　60

5.2　霍夫曼編碼　　62

5.3　高斯信道　　64

5.4　多維高斯信道　　66

5.5　假設檢驗　　67

5.5.1　規範化問題　　68

5.5.2　解答　　68

5.5.3　示例　　69

5.6　小結　　75

5.7　參考資料　　76

5.8　練習　　76

第6章　數字鏈路—B　　79

6.1　霍夫曼編碼最優性的證明　　79

6.2　低密度奇偶校驗碼（LDPC碼）　　80

6.3　聯合高斯分布隨機變數　　85

6.4　聯合高斯分布隨機變數的密度函數　　86

6.5　奈曼-皮爾遜定理5.6的證明　　88

6.6　小結　　89

6.7　參考資料　　90

6.8　練習　　90

第7章　追蹤定位—A　　91

7.1　估計問題　　92

7.2　線性最小平方估計（LLSE）　　93

7.3　線性回歸　　97

7.4　最小均方估計（MMSE）　　98

7.5　隨機向量的情況　　104

7.6　卡爾曼濾波器　　106

7.6.1　濾波器　　106

7.6.2　示例　　107

7.7　小結　　110

7.8　參考資料　　110

7.9　練習　　 111

第8章　追蹤定位—B　　115

8.1　LLSE的更新　　115

8.2　卡爾曼濾波器的推導　　116

8.3　卡爾曼濾波器的特性　　118

8.3.1　可觀測性　　119

8.3.2　可達性　　120

8.4　擴展卡爾曼濾波器　　121

8.5　小結　　124

8.6　參考資料　　124

第9章　語音識別—A　　125

9.1　學習：概念和示例　　125

9.2　隱馬爾可夫鏈　　126

9.3　期望最大化和聚類　　129

9.3.1　一個簡單的聚類問題　　129

9.3.2　回首再探　　130

9.4　學習：隱馬爾可夫鏈　　132

9.4.1　硬期望最大化　　132

9.4.2　訓練維特比演算法　　132

9.5　小結　　132

9.6　參考資料　　133

9.7　練習　　133

第10章　語音識別—B　　135

10.1　在線線性回歸　　135

10.2　隨機梯度投影理論　　136

10.2.1　梯度投影　　137

10.2.2　隨機梯度投影演算法　　140

10.2.3　鞅收斂定理　　142

10.3　大數據　　143

10.3.1　相關數據　　143

10.3.2　壓縮感知　　147

10.3.3　推薦系統　　150

10.4　小結　　151

10.5　參考資料　　151

10.6　練習　　151

第11章　路線規劃—A　　153

11.1　系統建模　　153

11.2　方法1：提前規劃　　154

11.3　方法2：適應性演算法　　155

11.4　馬爾可夫決策問題　　156

11.5　無限時域問題　　161

11.6　小結　　162

11.7　參考資料　　162

11.8　練習　　163

第12章　路線規劃—B　　166

12.1　線性二次型高斯問題　　166

12.2　有雜訊觀測時的線性二次型高斯問題　　169

12.3　部分可觀測的馬爾可夫決策問題　　171

12.4　小結　　173

12.5　參考資料　　174

12.6　練習　　174

第13章　視野拓展和補充　　176

13.1　推斷問題　　176

13.2　充分統計量　　177

13.3　無限馬爾可夫鏈　　179

13.4　泊松過程　　181

13.4.1　定義　　181

13.4.2　獨立自增量　　182

13.4.3　跳躍次數　　183

13.5　連續時間馬爾可夫鏈　　184

13.6　二元對稱信道的容量　　186

13.7　概率界　　190

13.8　鞅　　194

13.8.1　定義　　194

13.8.2　示例　　195

13.8.3　大數定律　　199

13.8.4　沃爾德等式　　200

13.9　小結　　201

13.10　參考資料　　201

13.11　練習　　202

附錄A　概率論基礎知識　　206

附錄B　線性代數基本知識　　240

附錄C　Matlab　　253

參考文獻　273

· · · · · · (收起)

不用說樓上那些高端的應用，就最基礎的的演算法和數據結構，不學概率你能學明白？：

Min-Cut: Karger"s Algorithm

Bloom Filter

Quicksort: Average case analysis, Randomized quicksort analysis

...

計算機網路性能分析，排隊輪，都是基於概率分析的，用來評估網路服務質量，平均服務時間和客戶的等待時間等等。

還有上面提到的貝葉斯分類，廣泛應用於數據挖掘，自然語言處理等領域

說學科你可能會覺得遠，說點離生活近的，人們生活中常接觸到的應用都有概率論的身影：

搜索：比如xxxxxxx

小廣告：比如你經常上網看編程技術，更容易看到頸椎病治療的廣告

輸入法：比如為什麼同是敲cjk，有人是「蒼井空」，有人是「超級快」

內容推薦：比如QQ彈個窗，要先估計你喜歡這個新聞的概率

殺毒：估計一段位元組代碼是新病毒的概率

語音助手：Cotarna、Siri

圖像識別：人臉登錄系統、上傳圖片猜你年齡

機器翻譯

概率論在其中如何應用，不可能一下子說清楚，有本科普不錯——《數學之美》

還有一個問題是：為什麼這些學科在高等教育的安排中不結合實際的專業學科，比如為了解決xxx問題我們必須以學習概率論中的xxx為基礎，而不是現在的作為基礎課來學習，等到遇到具體問題才發現原來答案在之前學過的東西里，這個順序不是很「反人類」（一般探究事物的過程）嗎？

關於概率論的應用別的答主已經說了很多了，我想回答下這個問題。題主認為應當通過問題導向的方式來學習概率論，其實是很正確的，帶著問題去學習效率的確會高很多。但問題在於，當你將來遇到需要用到概率論知識才能解決的問題時，如果你未曾接觸概率論，未必能想到這種解決方式。就跟你學習高等數學的原因是一樣的，當你以後有機會接觸到計算機圖形學你就明白它的意義。

第二個學習概率論的原因是，概率論一定程度上可以改變你的世界觀。比如設想這樣一個問題：有三個門，其中一個背後有汽車作為獎品，選對了就是你的，你可以選擇其中一個門，確認以後主持人打開另外兩扇門的其中一個，並且詢問你是否要更換選擇，這時候你會選擇換還是不換呢？（先想一下再往下看）

一般來說，按照常識換與不換都是有50%的幾率選到車，因為只剩下兩個門。但實際上，主持人開門並不是隨機開的，他不會選擇有車的門開（這句話須理解），實際上，更換選擇會有更高的概率(2/3)獲得汽車。三門問題_百度百科（放百度百科不會給噴吧?）相當有趣。除此之外，還有生日悖論_百度百科，你是否有過這樣的經驗，你的班級裡面總有那麼兩個人同一天生日，其實在一個超過23人的群體裡面，就有50%的概率有兩個人同一天生日，而超過60人，這個概率超過99%，Interesting.還有很多這樣Interesting的違反常識的東西。這也是同人於野先生在他的書《萬萬沒想到——用理工科思維理解世界》中建議所有人都去學習概率論的原因。

第三點，在本科階段，可以打好的基礎就打好，這些基礎課如果都等以後用到再帶著問題去學，其實是相當累的。

基於全概率公式的貝葉斯分類演算法，應該是最為大眾熟知的概率論的應用，具體場景就是垃圾郵件過濾，打tag等。

基於概率的素數測試演算法 Miller Rabin演算法

推薦一本書：

數學之美

看完你就知道了，很多很常見的本科知識在世界最前沿的互聯網應用。

數據挖掘啊親~

網路監控：使用分布以及隨機變數相關性來抽象出各個網路節點的數據樣本間的相關性，然後利用部分節點的樣本去估計剩餘節點，減少監控的overhead。

個人覺得先盡量理解課本，儘可能把概念記住，到時候用到了再回來翻然後加深理解。如果有精力可以邊學邊找論文來看看這些概念是怎麼用的。

概率統計對於機器學習是非常對口的。所以如果對於一個數理統計專業的學生，如果想考研究生的計算機時，其實機器學習方向其實是一個理想的選擇。

如機器學習方面的經典書籍都是和概率統計相關的：

《 Pattern Recognition and Machine Learning》和《The Elements of Statistical Learning》

不定語者的語音識別就是李開復用統計學的知識解決的

LDA BTM PAM

我們學校的概率論就是engineering 單獨提供的，然而我寧可學math department的課。。。強行在應用題里介紹各種ee的電路設計和概念，作為cs student，根本不明所以。

DataMing,SearchEngine,NLP,MachineLearning。。。

很多的。。。

密碼學