[學習筆記] 概率與期望及其應用
前言
這是一篇初學者的學習筆記，可能有些不準確或者遺漏的地方，還請各位指出。
可以通過 目錄 或者 Ctrl + F 尋找所需內容。
點擊展開目錄
引入 – 蒙提霍爾問題
如果不需要可以跳過。
你正在參加活動。在你面前有三扇關閉的門，其中一扇門後面是獎品，另外兩扇門後面是空的。你希望能獲得獎品。
在這個題目背景下，有以下幾個問題：
你選定了一扇門後直接打開。
此時獲得獎品的概率為 \(\frac {1} {3}\)。
在你選定了一扇門後，主持人隨機打開剩下兩扇門中的一扇，如果發現是空的，他會問你是否更換選擇。你的決定是？
考慮以下情況：
- 你最開始選的門為獎勵門（概率為 \(\frac{1} {3}\)），在主持人開了空門（概率為 \(\frac{1} {2}\)）後，選擇換門。獲得獎品的概率為 \(0\)。
- 你最開始選的門為獎勵門（概率為 \(\frac{1} {3}\)），在主持人開了空門（概率為 \(\frac{1} {2}\)）後，選擇不換門。獲得獎品的概率為 \(\frac{1} {3}\)。
- 你最開始選的門為空門（概率為 \(\frac {1} {3}\)），在主持人開了空門（概率為 \(\frac {1} {2}\)）後，選擇換門。獲得獎品的概率為 \(\frac {1} {3}\)。
- 你最開始選的門為空門（概率為 \(\frac {1} {3}\)），在主持人開了空門（概率為 \(\frac {1} {2}\)）後，選擇不換門。獲得獎品的概率為 \(0\)。
- 你最開始選的門為空門（概率為 \(\frac {1} {3}\)），在主持人開了獎勵門（概率為 \(\frac {1} {2}\)）後，選擇換門。獲得獎品的概率為 \(0\)。
- 你最開始選的門為空門（概率為 \(\frac {1} {3}\)），在主持人開了獎勵門（概率為 \(\frac {1} {2}\)）後，選擇不換門。獲得獎品的概率為 \(0\)。
綜上，無論換不換門，獲得獎品的概率都為 \(\frac{1} {3}\)。
在你選定了一扇門後，主持人打開剩下兩扇門中的一扇空門，然後他問你是否更換選擇。你的決定是？
考慮以下情況：
- 你最開始選的門為獎勵門（概率為 \(\frac{1} {3}\)），在主持人開了空門後，選擇換門。獲得獎品的概率為 \(0\)。
- 你最開始選的門為獎勵門（概率為 \(\frac{1} {3}\)），在主持人開了空門後，選擇不換門。獲得獎品的概率為 \(\frac{1} {3}\)。
- 你最開始選的門為空門（概率為 \(\frac{2} {3}\)），在主持人開了空門後，選擇換門。獲得獎品的概率為 $\frac{2} {3} $。
- 你最開始選的門為空門（概率為 \(\frac{2} {3}\)），在主持人開了空門後，選擇不換門。獲得獎品的概率為 \(0\)。
綜上，換門獲得獎品的概率為 \(\frac {2} {3}\)，不換門獲得獎品的概率為 \(\frac {1} {3}\)。
通過以上問題的討論，你已經初步接觸了概率論。下文會繼續講解相關內容。
1. 事件的概念、運算與關係
1.1 基礎概念
1.1.1 隨機試驗
具有以下特點的試驗稱為隨機試驗：
- 試驗可在相同條件下重複進行。
- 試驗可能出現多種結果，且試驗前已知所有結果的可能性。
- 無法預測試驗出現哪一結果。
通常用 \(E\) 來表示隨機試驗。
舉個栗子：
- E1：搖一次骰子，觀察點數出現情況。
- E2：拋一次硬幣，觀察正反面出現情況。
1.1.2 基本事件
隨機試驗中可能出現的每一個結果，也稱樣本點。記作 \(\omega\)。
舉個栗子：
- 前文 E1 有六個基本事件，其中第 \(i\) 個基本事件為出現點數為 \(i\)。
- 前文 E2 有兩個基本事件，出現正面 和 出現反面。
1.1.3 樣本空間
隨機試驗中所有基本事件構成一個集合，稱為樣本空間。記作 \(\Omega\)。
舉個栗子：
- 前文 E1 的樣本空間為 \(\{1,2,3,4,5,6\}\)。
- 前文 E2 的樣本空間為 \(\{正面,反面\}\)。
1.1.4 隨機事件
隨機試驗中部分基本事件構成一個集合，稱為隨機事件。隨機事件是樣本空間的子集。使用大寫字母進行表示。
舉個栗子：
- 前文 E1 中出現偶數點數的事件可表示為 \(A=\{2,4,6\}\)。
- 前文 E1 中出現奇數點數的事件可表示為 \(B=\{1,3,5\}\)。
1.1.5 事件發生
當某一事件所包含的基本事件中至少有一個發生，那麼該事件發生了。
好像有點廢話
1.1.6 必然事件
一定發生的事件。也就是樣本空間 $ \Omega$。
1.1.7 不可能事件
一定不發生的事件。記作 \(\Phi\)。（然而我並不是很清楚這是什麼符號，有沒有大佬給個解答）
1.2 事件運算
1.2.1 事件的和（並）
事件 \(A\) 與 事件 \(B\) 至少有一個發生，這個事件稱為 事件 \(A\) 與 事件 \(B\) 的和（並），記作 \(A+B\) 或 \(A\cup B\)。
舉個栗子：
\(A=\{1,2\}\)
\(B=\{3,4,5\}\)
\(A+B=\{1,2,3,4,5\}\)
1.2.2 事件的差
事件 \(A\) 發生而 事件 \(B\) 不發生，這個事件稱為 事件 \(A\) 與 事件 \(B\) 的差，記作 \(A-B\)。\(A-B=\complement_A(A\cap B)\)
舉個栗子：
\(A=\{1,2,4,5\}\)
\(B=\{1,4\}\)
\(A-B=\{2,5\}\)
1.2.3 事件的積（交）
事件 \(A\) 與 事件 \(B\) 同時發生，這個事件稱為 事件 \(A\) 與 事件 \(B\) 的積（交），記作 \(AB\) 或 \(A\cap B\)。
1.2.4 推廣
事件的和與積可推廣到多個事件，而差不可以。
為什麼差不可以推廣？
和與積的推廣長這樣：
\(A+B+C=A\cup B\cup C\)
\(ABC=A\cap B\cap C\)
然而當你計算差時：
\(A-B-C=(A-B)-C=\complement_A(A\cap B)-C=\complement_{\complement_A(A\cap B)}(\complement_A(A\cap B)\cap C)\)
它似乎……不大一樣呢？
1.3 事件關係
1.3.1 包含
若 事件 \(A\) 發生，那麼事件 \(B\) 必然發生。
具體表示 \(A\subset B\) 或者 \(B\supset A\)。
注意：\(\Phi \subset A\subset\Omega\)。
1.3.2 相等
若 \(A\subset B\) 且 \(B\subset A\)，那麼 \(A=B\)。
1.3.3 互斥
若 事件 \(A\) 與 事件 \(B\) 不能同時發生（\(AB=\Phi\)），則稱 事件 \(A\) 與 事件 \(B\) 互不相容或互斥。\(A\) 與 \(B\) 互不相容意味着 \(A\) 與 \(B\) 不含公共基本事件。
1.3.4 對立（互逆）
若 事件 \(A\) 與 事件 \(B\) 發生了有且僅有一個，且 \(A\cup B=\Omega\)、\(A\cap B=\Phi\)，則稱 事件 \(A\) 與 事件 \(B\) 對立（互逆）。
其中 事件 \(B\) 叫做 事件 \(A\) 的逆事件，記作 \(B=\overline{A}\)。事件 \(A\) 叫做 事件 \(B\) 的逆事件，記作 \(A=\overline{B}\)。
1.3.5 舉例理解
進行三次射擊，\(A_i\) 表示第 \(i\) 次擊中。
\(A_1+A_2\) 表示前兩次射擊至少擊中一次
\(\overline{A_2}\) 表示第二次未擊中。
\(A_2-A_3=\complement_{A_2}(A_2\cap A_3)=A_2\overline{A_3}\) 表示第二次擊中而第三次未擊中。
2. 概率
2.1 概率的數學定義
設 \(\Omega\) 是隨機試驗 \(E\) 的樣本空間，找到一個對應法則，使得 \(E\) 的每一個事件 \(A\) 都對應一個實數，這記為 \(P(A)\)。
2.2 概率的性質及應用
2.2.1 概率的性質
- \(P(\Omega)=1\)。（正則性）
- \(P(\emptyset)=0\)。
- \(0\leq P(A)\leq1\)。（非負性）
- 若 \(A_1,A_2,A_3,…,A_n,…\) 互不相容，則 \(P\left(\bigcup_{i=1}^{\infty}A_i \right)=\sum_{i=1}^{\infty}P(A_i)\)。（可列可加性）
- 若 \(AB=\Phi\)，則 \(P(A\cup B)=P(A)+P(B)\)。（有限可加性）（可推廣到 \(n\) 個互不相容的事件）
- \(P(A)=1-P(\overline{A})\)。
- \(P(B-A)=P(B)-P(AB)\)。
- \(P(A\cup B)=P(A)+P(B)-P(AB)\)。
應該不用證明吧？
2.3 條件概率
設 \(E\) 為一隨機試驗，\(A\) 和 \(B\) 為其中的兩個事件且 \(P(A)>0\)，那麼 \(\frac{P(AB)} {P(A)}\) 為發生 事件 \(A\) 的情況下 事件 \(B\) 發生的條件概率，記作 \(P(B|A)\)。所以 \(P(B|A)=\frac{P(AB)}{P(A)}\)。（公式可變形為 \(P(AB)=P(A)\times P(B|A)\)）
舉個栗子：
布袋中有 \(3\) 個黑球和 \(2\) 個白球，每次隨機取出一顆球（不放回），求第兩次摸到白球的概率。
- 如果第一次取出了黑球（概率為 \(\frac{3} {5}\)），那麼袋子中還剩下 \(2\) 個黑球和 \(2\) 個白球，第二次摸到白球的概率為 \(\frac{1} {2}\)，該情況的概率為 \(\frac{3} {5}\times\frac{1} {2}=\frac{3} {10}\)。
- 如果第一次取到了白球（概率為 \(\frac{2} {5}\)），那麼袋子中還剩下 \(3\) 個黑球和 \(1\) 個白球，第二次摸到白球的概率為 \(\frac{1} {4}\)，該情況的概率為 \(\frac{2} {5}\times\frac{1} {4}=\frac{1}{10}\)。
第二次摸到白球的總概率就是 \(\frac{3} {10}+\frac{1} {10}=\frac{2} {5}\)。
由條件概率公式可推得 \(P(AB)=P(A\cap B)=P(B)P(A|B)=P(A)P(B|A)\)。
3. 公式與模型
3.1 全概率公式
如果事件 \(B_1,B_2,…,B_n\) 兩兩互不相容，且和為全集，\(\forall P(B_i)>0\)。
那麼對於任一事件 \(A\) 有：。\(P(A)=\sum_{i=1}^nP(AB_i)=\sum_{i=1}^n(P(A|B_i)\cdot P(B_i))\)。
特別地，對於任意兩個隨機事件 \(A\) 和 \(B\)（\(A,B\) 對立），有式子 \(P(B)=P(B|A)P(A)+P(B|\overline{A})P(\overline{A})\)。
3.2 貝葉斯公式
設 \(B1,B2,…\) 是樣本空間 $\Omega $ 的一個劃分，則對任一 事件\(A\) （\(P(A)> 0\)），有：
\(P(B_i|A)=\frac{P(B_i)P(A|B_i)} {\sum_{j=1}^nP(B_j)P(A|B_j)}\)。
上式即為貝葉斯公式，\(B_i\) 常被視為導致試驗結果 \(A\) 發生的」原因「。
貝葉斯公式建立在條件概率的基礎上，尋找事件發生的原因。（即大事件A已經發生的條件下，分割中的小事件Bi的概率）
3.3 波利亞瓦罐模型
一個瓦罐中有 \(n\) 個黑球和 \(m\) 個白球。每次取出一個，記錄其顏色，再將它和另外 \(r\) 個與它同色的球放入瓦罐中，如此循環。
結論1：第 \(k\) 次取到黑球的概率為 \(\frac{n} {n+m}\)，取到白球的概率為 \(\frac{m} {n+m}\)。
證明：
當 \(k=1\) 時，取到黑球的概率為 \(\frac{n} {n+m}\)，取到白球的概率為 \(\frac{m} {n+m}\)。
假設第 \(k\) 次成立。
考慮取到黑球的概率：
\(P(k+1)=\frac{n} {n+m}\cdot\frac{n+r} {n+m+r}+\frac{m} {n+m}\cdot\frac{n} {n+m+r}=\frac{n(n+m+r)} {(n+m)(n+m+r)}=\frac{n}{n+m}\)。
取到白球的概率：
\(P(k+1)=\frac{n} {n+m}\cdot\frac{m} {n+m+r}+\frac{m} {n+m}\cdot\frac{m+r} {n+m+r}=\frac{m(n+m+r)} {(n+m)(n+m+r)}=\frac{m} {n+m}\)。
由數學歸納法得證。
結論2：無論 \(a,b(a\neq b)\) 取什麼值，第 \(a\) 次與第 \(b\) 次同時取出黑（白）球的概率始終相等。
證明：
設 \(P_{a,b}(n,m)\) 為對應的概率，不難求出 \(P_{1,b}=\frac{n} {n+m}\times\frac{n+r} {n+m+r}\)。
同樣考慮數學歸納法。
\(P_{a,b}(n,m)=\frac{n} {n+m}\cdot\frac{n+r} {n+m+r}\cdot\frac{n+2r} {n+m+2r}+\frac{m}{n+m}\cdot\frac{n}{n+m+r}\cdot\frac{n+r}{n+m+2r}=\frac{n(n+r)(n+m+2r)}{(n+m)(n+m+r)(n+m+2r)}=\frac{n} {n+m}\cdot\frac{n+r} {n+m+r}=P_{1,2}(n,m)\)。
得證。
4. 例題
兩道期望DP題。似乎和上文沒什麼關係？？？
4.1 綠豆蛙的歸宿
//www.luogu.com.cn/problem/P4316
4.1.1 題目大意
給一張 \(n\) 個點 \(m\) 條邊的有向圖，每條邊有邊權。現從 \(1\) 走到 \(n\)，每次等概率選取一條邊走，求路徑總長度的期望。
4.1.2 思路
考慮進行期望DP。
設 \(f_i\) 表示從點 \(i\) 出發走到點 \(n\) 的期望路徑長度，答案即為 \(f_1\)。初始狀態 \(f_n=0\)。
反向連邊建圖，在圖上跑拓撲進行轉移。
具體地講，每次取出一個入度為零的點 \(x\)，枚舉它能到的點 \(v\)，在正常拓撲的同時轉移，轉移式為 \(f_v=\frac{f_x+w(x,v)} {deg_v}\)。
4.1.3 代碼實現
int n, m;
int last[N], cnt;
struct edge {
int to, next, w;
} e[N << 1];
void addedge(int x, int y, int w) {
e[++cnt].to = y;
e[cnt].next = last[x];
e[cnt].w = w;
last[x] = cnt;
}
int deg[N], lne[N]; //deg為拓撲所用的入度數, lne為出邊數
queue <int> s;
double f[N];
void topsort() {
for (int i = 1; i <= n; i++)
if (deg[i] == 0) s.push(i);
while (s.size()) {
int x = s.front(); s.pop();
for (int i = last[x]; i; i = e[i].next) {
int v = e[i].to; deg[v]--;
f[v] += (f[x] + e[i].w) * 1.0 / lne[v];
if (!deg[v]) s.push(v);
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
addedge(v, u, w); deg[u]++, lne[u]++; //反向建邊
}
topsort();
printf("%.2lf", f[1]);
return 0;
}
4.2 [NOIP2016 提高組] 換教室
//www.luogu.com.cn/problem/P1850
4.2.1 題目大意
一共有 \(n\) 個時間節點上安排了課程，對於每個時間節點 \(i\)，兩節內容相同的課會佔用 \(c_i\) 和 \(d_i\) 兩間教室。
一般來講，學生需按時間在 \(c_i\) 教室完成第 \(i\) 節課。但他們也可以通過提交申請嘗試更換教室。具體地，申請更換第 \(i\) 節課的教室通過的概率為已知實數 \(k_i\)，如果申請通過，學生就可以去 \(d_i\) 教室上課。
牛牛可以提交最多 \(m\) 次申請。由於兩教室間的距離和擁堵程度不同，牛牛在前往教室時耗費的體力也不同。當第 \(i(1\leq i<n)\) 節課結束後，他會從這間教室沿耗費體力最少的路徑前往下個教室。
問申請更換教室後 在教室間移動耗費的體力值的總和 的期望值 最小是多少。
4.2.2 思路
需要知道每兩間教室直接的最短路長度時多少。這可以用 Floyed 解決。
然後考慮DP，設 \(f_{i,j,0/1}\) 表示前 \(i\) 個時間節點換了 \(j\) 次教室，第 \(i\) 個時間節點 換/沒換 教室，耗費的體力值的總和的期望最小是多少。
怎麼轉移？
\(f_{i,j,0}=\min\{f_{i-1,j,0}+dis(c_{i-1},c_i),f_{i-1,j,1}+dis(d_{i-1},c_i)\times k_{i-1}+dis(c_{i-1},c_i)\times(1-k_{i-1}) \}\)
\(f_{i,j,1}=\min\{f_{i-1,j-1,0}+dis(c_{i-1},d_i)\times k_i+dis(c_{i-1},c_i)\times(1-k_i),\)\(f_{i-1,j-1,1}+dis(d_{i-1},d_i)\times k_{i-1}\times k_i+dis(d_{i-1},c_i)\times k_{i-1}\times(1-k_i)\)\(+dis(c_{i-1},d_i)\times(1-k_{i-1})\times k_i+dis(c_{i-1},c_i)\times(1-k_{i-1})\times(1-k_i) \}\)
答案即為 \(\min_{i=0}^mmin(f_{n,i,0},f_{n,i,1})\)。
4.2.3 代碼實現
dp轉移太長了，代碼很醜，見諒~
const int N = 2010, M = 90010;
const double INF = 1e17;
int n, m, cntroom, cntedge, c[N], d[N];
ll dis[N][N];
double f[N][N][2], k[N];
int main() {
n = read(), m = read(), cntroom = read(), cntedge = read();
for (int i = 1; i <= cntroom; i++)
for (int j = i + 1; j <= cntroom; j++)
dis[i][j] = dis[j][i] = INF;
for (int i = 1; i <= n; i++) c[i] = read();
for (int i = 1; i <= n; i++) d[i] = read();
for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);
for (int i = 1; i <= cntedge; i++) {
int u = read(), v = read(), w = read();
dis[u][v] = dis[v][u] = min(dis[u][v], w * 1ll);
}
for (int p = 1; p <= cntroom; p++)
for (int i = 1; i <= cntroom; i++)
for (int j = 1; j <= cntroom; j++)
dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
f[i][j][0] = f[i][j][1] = INF;
f[1][0][0] = f[1][1][1] = 0;
for (int i = 2; i <= n; i++) f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= min(i, m); j++) {
f[i][j][0] = min(f[i - 1][j][0] + dis[c[i - 1]][c[i]], f[i - 1][j][1] + dis[d[i - 1]][c[i]] * k[i - 1] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]));
f[i][j][1] = min(f[i - 1][j - 1][0] + dis[c[i - 1]][d[i]] * k[i] + dis[c[i - 1]][c[i]] * (1 - k[i]), f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * k[i - 1] * k[i] + dis[d[i - 1]][c[i]]* k[i - 1] * (1 - k[i]) + dis[c[i - 1]][d[i]] * (1 - k[i - 1]) * k[i] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]) * (1 - k[i]));
}
double ans = INF;
for (int i = 0; i <= m; i++) ans = min(ans, min(f[n][i][0], f[n][i][1]));
printf("%.2lf\n", ans);
return 0;
}
參考資料
蒙提霍爾問題（又稱三門問題、山羊汽車問題）的正解是什麼？ – 知乎
