原文鏈接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é)

以上是生活随笔為你收集整理的概率论学习笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。