機率期望 學習筆記

基礎知識

機率定義

\(P(A)\) 為事件 \(A\) 發生的機率， \(P(A|B)\) 為在 \(B\) 事件發生的前提下 \(A\) 事件發生的機率。

機率性質

1. 加法公式：\(A,B\) 獨立，則 \(P(A\or B)=P(A)+P(B)\)。（ \(P(A\or B)\) 就是 \(A\) 發生或者 \(B\) 發生）

   廣義加法公式：\(A,B\) 任意，則 \(P(A\or B)=P(A)+P(B)-P(A\and B)\)。（ \(P(A\and B)\) 就是 \(A\) 發生且 \(B\) 發生）

2. 乘法公式：

   \(A,B\) 獨立， \(P(A*B)=P(A)*P(B)\)。

   \(A,B\) 任意，\(P(A*B)=P(A)*P(B|A)=P(B)*P(A|B)\)。

3. 全機率公式、貝葉斯定理……（略）

期望定義

\(E(A)\)。

期望性質

1. 若 \(A\) 是事件， \(C\) 是常數，則 \(E(CA)=C*E(A)\)

   證明：

   設 \(A\) 的多個随機變量為 \(Ca_1,Ca_2...Ca_n\)，對應出現的機率為 \(p_1,p_2...p_n\)，則有：

   \[E(CA)=\sum\limits_{i=1}^n*(Ca_ip_i)=C\sum\limits_{i=1}^n*(a_ip_i)=C*E(A)

   \]

2. \(A,B\) 任意，則 \(E(A+B)=E(A)+E(B)\)。
3. \(A,B\) 獨立，則 \(E(AB)=E(A)E(B)\)。
4. 期望等于所有的方案數的貢獻除以方案數。

票券收集問題

題意

[連結](SP1026 FAVDICE - Favorite Dice - 洛谷 | 計算機科學教育新生态 (luogu.com.cn))

有 \(n\) 種票券，每次等機率抽取一張票券，求抽到所有 \(n\) 種票券的抽取次數的期望。

解法 1

如果手上已經有 \(i-1\) 種票券，

則 \(\large P(取一個票券為新票券)=\frac{n-i+1}{n}\)，

則 \(\large E(取到新票券)=\frac{1}{P(...)}=\frac{n}{n-i+1}\)，

則總期望為 \(\large\sum\limits_{i=1}^n\frac{n}{n-i+1}=\sum\limits_{i=1}^n\frac{n}{i}\)。

解法 2

期望 DP ！！

設 \(f_i\) 為取了 \(i\) 種票券後，還要去多少票券才能集齊的期望。

顯然 \(f_n=0\)，考慮逆推。

考慮到抽到 \(i\) 種票券後再抽一個是新票券的機率是 \(\Large \frac{n-i}{n}\) ，舊票券機率是 \(\Large \frac i n\)，則有方程 \(\Large f_i=\frac{n-i}{n}f_{i+1}+\frac i n f_i+1\)。（加一是因為一定要投一次）。

\[\frac{n-i}nf_i=\frac{n-i}nf_{i+1}+1\\

f_i=f_{i+1}+\frac{n}{n-i}\\

f_i=f_{i+2}+\frac n {n-i-1}+\frac n {n-i}\\

...\\

f_0=\sum \frac{n}{n-i+1}=\sum \frac n i

是以答案為 \(\Large \sum \frac n i\)。

走圖1

[連結](P4316 綠豆蛙的歸宿 - 洛谷 | 計算機科學教育新生态 (luogu.com.cn))

有邊權無向圖 \(G\)，從 \(1\) 出發到 \(n\)，在一個點會等機率選擇一個出度并走去下一個點，求到 \(n\) 經過的邊權和的期望。（保證從 \(1\) 能走到任何點，任何點都能走到 \(n\)）。

解法

設 \(f_i\) 為 \(i\to n\) 的期望路徑長。顯然 \(f_n=0\)。

那麼設 \(i\) 點出度為 \(k\)，有 \(f_i=\frac1 k(\sum f_v+w_E)\)。

然後拓撲或 dfs 決定更新順序。

走圖2

有無向圖 \(G\)，求随機選擇一條路徑走過的邊數的期望。

用期望性質4，設 \(sum\) 為所有路徑長度總和，\(cnt\) 為路徑個數。