概率论学习笔记
原文鏈接www.cnblogs.com/zhouzhendong/p/probablity.html
概率論學(xué)習(xí)筆記
前言
博主不會(huì)做概率題,一遇到這種題就只會(huì)通過(guò)尋找容易理解的模型來(lái)做。但是概率題往往可以用更為抽象的公式來(lái)簡(jiǎn)單解決。
所以我決定系統(tǒng)地學(xué)習(xí)一下概率論相關(guān)的知識(shí)。
我學(xué)習(xí)與參考的材料是 2013年候選隊(duì)員論文 中 胡淵鳴 的《淺析信息學(xué)競(jìng)賽中概率論的基礎(chǔ)與應(yīng)用》。可以將本文看作論文的摘錄和我個(gè)人的一些理解與補(bǔ)充。
定義和公式
概率:對(duì)某件事情發(fā)生的可能性的度量。
樣本空間(Omega):某個(gè)隨機(jī)事件的所有可能結(jié)果的集合。論文中提到,在競(jìng)賽中,往往可以認(rèn)為 (Omega) 每個(gè)自己都是一個(gè)事件。
事件集合(F):事件集合是樣本空間的所有子集所構(gòu)成的集合。
概率測(cè)度(P):是事件集合到實(shí)數(shù)的一個(gè)函數(shù),表示某個(gè)事件集合發(fā)生的概率。一個(gè)合理的概率測(cè)度乣滿足3條概率公理。
概率公理:
(1)對(duì)于任意事件 (A) ,有 (P(A) geq 0) 。
(2)(P(Omega) = 1) 。
(3)對(duì)于事件 (A) 和 (B) ,如果 (Acap B = phi) ,則 (P(Acup B) = P(A) + P(B)) 。
概率空間:符合要求的三元組 ((Omega,F,P)) 為概率空間。
條件概率:條件概率表示在一定條件下某個(gè)事件發(fā)生的概率。我們往往用 (P(A|B)) 來(lái)表示當(dāng)事件 (B) 發(fā)生時(shí),事件 (A) 發(fā)生的概率。計(jì)算條件概率的公式如下:
[P(A|B) = cfrac{P(AB)}{P(B)}
]
這里我們把 (Acup B) 寫成了 (AB),在后面的表述中, (A,B) 也將有相同的含義。
對(duì)于上式,當(dāng)發(fā)生特殊情況 (Acap B = phi) 時(shí),可以得到:
[{m If Acap B = phi then P(A|B) = cfrac{P(AB)}{P(B)} = P(A)}.
]
全概率公式:如果 (B_1, B_2, cdots, B_n) 是樣本空間 (Omega) 的一個(gè)劃分,那么
[egin{eqnarray*}P(A) = sum_{k} P(A,B_k) = sum_{k} P(A|B_k)P(B_k)end{eqnarray*}
]
如何理解這個(gè)公式?因?yàn)?(B_1,B_2,cdots , B_n) 是樣本空間 (Omega) 的一個(gè)劃分,所以我們可以認(rèn)為事件 (A) 被劃分成了事件 (AB_1,AB_2,cdots ,AB_n) ,即 (A = AB_1+AB_2+cdots AB_n) 。
(m Bayes)公式:因?yàn)?(P(A|B)P(B) = P(AB) = P(B|A) P(A)) ,所以可以得到 (m Bayes)公式:
[P(A|B) = cfrac {P(B|A)P(A)}{P(B)}
]
將 (m Bayes)公式 與全概率公式結(jié)合,可以得到
[P(B_k|A) = cfrac{P(A|B_k)P(B_k)}{P(A)} = cfrac{P(A|B_k)P(B_k)}{sum_{i}P(A|B_j)(B_j)}
]
隨機(jī)變量(m(random variable)):隨機(jī)變量不是變量,而是定義在樣本空間(Omega) 上的一個(gè)實(shí)值函數(shù)。形式化地說(shuō)
函數(shù) (X:Omegaightarrow mathbb{R}) 被稱為一個(gè)隨機(jī)變量。
論文中提到,在大多數(shù)情況下,有了隨機(jī)變量之后就可以拋棄對(duì)原先樣本空間的關(guān)注,而是集中注意于對(duì)于每個(gè)實(shí)值,隨機(jī)變量能取得該值的概率。這個(gè)過(guò)程實(shí)際上是對(duì)樣本空間重新劃分的一個(gè)過(guò)程,將在這個(gè)函數(shù)下取得同意實(shí)數(shù)值的樣本空間中的元素合并了。
期望((m expectation)):是對(duì)隨機(jī)變量表現(xiàn)出的平均情況的一種刻畫(huà)。
對(duì)于一個(gè)隨機(jī)變量,第一其期望如下:
[egin{eqnarray*}E[x] = sum_{omega}P(omega)X(omega) = sum_{x} xP(X = x)end{eqnarray*}
]
隨機(jī)變量的獨(dú)立性:隨機(jī)變量的獨(dú)立性是指兩個(gè)隨機(jī)事件在其輸出層上的屬性。對(duì)于兩個(gè)隨機(jī)事件 (X_1,X_2) 和實(shí)數(shù) $x_1 in X_1(Omega), x_2 in X_2 (Omega) $ ,如果 (P(X_1 = x_1,X_2 = x_2) = P(X_1 = x_1) P(X_2 = x_2)) 就稱 (X_1,X_2) 互相獨(dú)立。
乘積的期望:如果兩個(gè)隨機(jī)變量互相獨(dú)立,那么其積的期望等于其期望的積。證明:
[egin{eqnarray*} E[X_1X_2] &=& sum_{xin(X_1X_2)(Omega)} xP(X_1X_2=x)\ &=&sum_{xin (X_1X_2)(Omega) }sum_{x_1in X_1(Omega)} x_1 cfrac x {x_1} P(X_1 = x_1)P(X_2 = cfrac x {x_1})\&=&sum_{x_1in X_1(Omega)} x_1 P(X_1 = x_1)sum_{xin (X_1X_2)(Omega) }cfrac x {x_1} P(X_2 = cfrac x {x_1})\&=&sum_{x_1in X_1(Omega)} x_1 P(X_1 = x_1)sum_{x_2in X_2(Omega)} x_2 P(X_2 = x_2)\&=& E[X_1]E[X_2]end{eqnarray*}
]
期望的線性性:不管隨機(jī)變量 (X_1,X_2) 是否獨(dú)立,總有
[E[alpha X_1+eta X_2] = alpha E[X_1] + eta E[X_2]
]
全期望公式:類似于條件概率,全期望公式是指當(dāng)一個(gè)時(shí)間一定發(fā)生時(shí),隨機(jī)變量 (X) 的期望。
首先我們寫出條件概率的式子:
[P((X|A) = x) = cfrac{P(X=x,A)}{P(A)}
]
接下來(lái)給出全期望公式:
[E[E[X|Y]] = E[X]
]
證明:
[egin{eqnarray*} E[E[X|Y]] &=& sum_{yin Y(Omega)} E[X|Y=y] P(Y=y)\&=& sum_{yin Y(Omega)} sum_{xin X(Omega)}x P(X=x|Y=y)P(Y=y)\&=&sum_{yin Y(Omega)} sum_{xin X(Omega)}x P(X=x,Y=y) \&=&sum_{xin X(Omega)}xsum_{yin Y(Omega)} P(X=x,Y=y)\&=& sum_{xin X(Omega)} xP(X = x)\&=&E[x] end{eqnarray*}
]
Markov不等式:
[forall a>0,P(Xgeq a ) leq cfrac{E[X]}a
]
這個(gè)不等式給出了隨機(jī)變量的取值大于某一個(gè)值的概率的一個(gè)粗略上界。可以用于證明某些隨機(jī)算法的在時(shí)間消耗上的可行性。
例子與一些拓展
CF123E 推論
有一棵有根樹(shù) (T),設(shè)根節(jié)點(diǎn)為 (1) ,(t) 為某個(gè)葉子節(jié)點(diǎn),(S(x)) 為節(jié)點(diǎn) (x) 的子節(jié)點(diǎn)序列。
計(jì)數(shù)器 C 的初始值為 0。考慮以下 DFS 的過(guò)程(初始時(shí)調(diào)用 DFS(1) ):
DFS(x){
若 x = t,則終止程序。
random_shuffle(S(x));
For y in S(x) {
C <- C+1;
DFS(y);
}
C <- C+1;
}
求證:若有根樹(shù) (T) 的節(jié)點(diǎn)個(gè)數(shù)為 (n) ,則 (E[C] = n-1) 。
證明
首先,根據(jù)期望的線性性,可以得到
[E[C] = sum_{ein {mathbb E}} E[e被經(jīng)過(guò)的次數(shù)]
]
其中 “經(jīng)過(guò)邊e一次” 表示沿著邊e遞歸或者回溯一次。
于是我們將所有的邊分兩種來(lái)考慮:
從根到 (t) 路徑 (a) 上的邊:顯然這中的邊會(huì)且只會(huì)被一次。
對(duì)于其他的邊,它們只會(huì)被經(jīng)過(guò) 0 次或者 2 次。那么,我們要求具體期望的話,需要知道這兩種情況發(fā)生的概率之比。考慮一條邊向上第一次走到 (a) 上的節(jié)點(diǎn)。對(duì)于其子節(jié)點(diǎn)的排列,如果它所在的子樹(shù)在 (t) 所在子樹(shù)之前,那么他就會(huì)被訪問(wèn),否則就不會(huì),所以概率均為 (0.5) ,所以期望為 (1) 。
由于總邊數(shù)為 (n-1) ,每條邊期望被經(jīng)過(guò)一次, 所以 (E[C] = n - 1) 。
最小點(diǎn)覆蓋隨機(jī)增量法退化成 (O(n^2)) 的一個(gè)概率上界
我們都知道最小點(diǎn)覆蓋的期望時(shí)間復(fù)雜度為 (Theta (n)) 。
那么它退化為 (n^2) 的概率的一個(gè)上界是什么呢?
根據(jù)Markov不等式,可得
[P(Xgeq n^2)leq cfrac{E[x]}{n^2}=cfrac 1n
]
一般來(lái)說(shuō) (n) 的大小為 (10^5) 級(jí)別。所以退化的概率的一個(gè)上限在 (10^{-5}) 級(jí)別,非常小,不必?fù)?dān)心。事實(shí)上,這只是一個(gè)不緊的上界,也許可以通過(guò)更加精妙的證明得到更好的上界。
概率轉(zhuǎn)移網(wǎng)絡(luò)上的經(jīng)典問(wèn)題
概率轉(zhuǎn)移網(wǎng)絡(luò)是一個(gè)有向網(wǎng)絡(luò),由點(diǎn)集(狀態(tài)集)V,轉(zhuǎn)移概率矩陣(一個(gè)二元函數(shù))$$G : V imes V ightarrow [0,1]$$ ,以及起點(diǎn) (v_0) 組成。其中,對(duì)于每個(gè) (uin V),有 (sum_v G[u,v] leq 1) 。
這類問(wèn)題常常會(huì)以 “圖上隨機(jī)游走” 的模型出現(xiàn)。設(shè)節(jié)點(diǎn) (x) 到達(dá)終點(diǎn)的期望步數(shù)為 (E[x]) ,建立方程組之后直接采用高斯消元算法即可在 (O(n^3)) 的時(shí)間復(fù)雜度內(nèi)解決問(wèn)題。特別地,當(dāng)圖較為稀疏時(shí),存在更加高效的做法。但這與概率期望的建模關(guān)系不大,主要在于優(yōu)化稀疏矩陣高斯消元,故這里不做展開(kāi)。詳見(jiàn) IOI2019中國(guó)國(guó)家候選隊(duì)論文集 中 王修涵 的《淺談圖模型上的隨機(jī)游走問(wèn)題》。
UOJ#299. 【CTSC2017】游戲
題意自行查看,不再贅述。
做法:
首先,根據(jù)期望的線性性,容易得知,總期望等于以已知點(diǎn)為界的各個(gè)未知段的期望之和加上已知點(diǎn)的和。易知每段區(qū)間的期望只和自身轉(zhuǎn)移系數(shù)和這段區(qū)間兩端的已知點(diǎn)信息有關(guān)。
考慮到每次加入和刪除信息時(shí),只會(huì)影響 (O(1)) 段區(qū)間的兩端節(jié)點(diǎn)。
形式化地,我們?cè)O(shè) (R_i) 表示事件 “(R) 在第 (i) 局中勝出”, (B_i) 表示事件 “(B) 在第 (i) 局中勝出”。
題意中提到的獲勝概率可以表示為
[P(R_i|R_{i-1}) = p_i,P(B_i|R_{i-1}) = 1-p_i\P(R_i|B_{i-1}) = q_i,P(B_i|B_{i-1}) = 1-q_i
]
設(shè)行向量 (L_i = [P(R_i),P(B_i),E[R_i],E[B_i]]),其中 (E[R_i],E[B_i]) 到第 (i) 局 (R) 獲勝和 (B) 獲勝時(shí),(R) 獲勝局?jǐn)?shù)的期望。
建立概率期望轉(zhuǎn)移矩陣 (M_i),使得 (L_i M_i = L_{i+1})。容易得到:
[M_i = egin{bmatrix}p_i& 1-p_i& p_i & 0\q_i& 1-q_i& q_i& 0\0& 0& p_i&1-p_i\0 &0 &q_i &1-q_iend{bmatrix}
]
假設(shè)我們已經(jīng)推得了某個(gè)區(qū)間的最后一個(gè)位置的概率行向量。接下來(lái)我們還要加上右側(cè)已知信息對(duì)概率期望的影響。
我們直接求得 (L_{i+1}),根據(jù)條件概率的計(jì)算公式,可以直接計(jì)算答案。
為了方便,我們可以設(shè) (P(R_0) = 0, P(B_0) = 1)。
由于本題涉及 double 類型的精度問(wèn)題,所以對(duì)矩陣求逆會(huì)導(dǎo)致過(guò)大的精度誤差,所以只能使用線段樹(shù)來(lái)得到區(qū)間矩陣積。
每次在修改操作的時(shí)候重算 (O(1)) 個(gè)區(qū)間對(duì)答案的貢獻(xiàn)即可。
時(shí)間復(fù)雜度 (O(mlog n)) 。
總結(jié)
- 上一篇: 使用OpenGL绘制圆环体(Torus)
- 下一篇: 超硬核!我统计了BAT笔试面试出现频率最