數學期望筆記

基礎知識點

首先明確期望公式:
\[E(X)=∑_ip_i*x_i\]
其中 \(p\) 代表概率 , \(x\) 代表發生貢獻。

然后期望的幾點性質:
對于數學期望，我們還應該明確一些知識點：

(1) 期望的“線性”性質
對于所有滿足條件的離散型的隨機變量\(X,Y\)和常量\(a,b\)有: \[E(aX+bY)=aE(x)+bE(y)\]
即常說的"期望的和等于和的期望"
類似的,我們還有 \(E(XY)=E(X)+E(Y)\).

(2)全概率公式

假設\({Bn∣n=1,2,3,...}\) 是一個“概率空間有限或可數無限”的分割，且集合\(Bn\)是一個“可數集合”，則對于任意事件\(A\)有：

\[P(A)=∑_nP(A∣Bn)P(Bn)\]

(3)全期望公式

\[E(Y)=E(E(Y∣X))=∑_iP(X=xi)E(Y∣X=xi)\]

1. P3802 小魔女帕琪

題目鏈接

Solution

今天被期望虐慘了,去洛谷找了一道顏色最淺的期望題,結果還是被虐了...

首先,很明顯,小魔女會施展\(N=\sum^{i=1}_7a_i\) 次魔法。

我們考慮一個節點 \(i\) , 以它為起點;
然后有 \(7\) 種不同顏色的概率即為:
\[\prod^{i=1}_{7}\frac{a_i}{N-i+1}\]
然后,我們可以知道每一次這種結果的貢獻即為其排列數 \(7!\)
所以對于單點 \(i\) , 其期望即為:
\[P_i=7!*\prod^{i=1}_{7}\frac{a_i}{N-i+1}\]
由因為這樣的點至多只有 \(N-6\) 個,所以最終答案即為:
\[Ans=(N-6)*7!*\prod^{i=1}_{7}\frac{a_i}{N-i+1}\]

然后此題代碼十分簡潔.不過十行.

2. UVA12230 Crossing Rivers

題目鏈接

題意翻譯

一個人每天需要從家去往公司,然后家與公司的道路是條直線,長度為 \(D\)。
同時路上有 \(N\) 條河,給出起點和寬度\(W_i\) , 過河需要乘坐速度為\(V_i\) 的渡船;
船在河中的位置隨機,固定往返時間. 且該人在陸地上行走速度為 1 .求該人去公司的路途的期望時間.

Solution

讓我多了一些對于期望的了解。
考慮過每條河流的最壞情況和最好情況.
1.最壞情況: \((3*W_i)/V_i\) ; 此時即船剛剛走。
2.最好情況: \(W_i/V_i\) ; 此時即船剛好來。

由于船的位置隨機,所以說其滿足期望線性.
所以我們每次過一條河流的期望時間即為: \((2*W_i)/V_i\) ;
然后就解決了這個問題.

3. SP1026 FAVDICE - Favorite Dice

題目鏈接

一句話題意:
給一個 \(n\) 面的骰子,問每一面都被甩到的次數期望是多少.

Solution

這是一道比較好的期望 DP 入門題.
考慮定義 \(f[i]\) 為有 \(i\) 面沒有被投到的可能次數.

那么對于沒有投到的面數 \(k\) ,我們有 \(k/n\) 的可能性繼續投到它們.
同樣,對于已經投到過的,我們有 \(n-k/n\) 的概率可繼續投到它們.
然后它們的貢獻即分別為 \(f[k]\) 和 \(f[k-1]\).

那么即得到轉移式:
\[f[i]=i/n*f[i]+(n-i)/n*f[i+1]+1\]
從 \(f[n]\) 倒推即可,\(f\) 初始為 0.

4. P1365 WJMZBMR打osu! / Easy

題目鏈接

Solution

Wa,我是真的被期望折服了,感覺這道題拿來練手正好.
DP的難度可做又巧妙...

我們定義:
\(f[i]\) 代表到第 \(i\) 次點擊的時候的最大答案.
\(g[i]\) 代表到第 \(i\) 此點擊的 \(o\) 的期望長度.

然后看轉移:
1.此時為 \(o\) ,那么我可以直接計算答案。
由于 \((x+1)^2=x^2+2x+1\) ,所以我們得到轉移方程:
\[f[i]=f[i-1]+2*g[i-1]+1\]
同時由于此時 \(o\) 的長度已經增加,所以同時 \(g[i]=g[i-1]+1\).

2.此時為 \(x\),同樣直接統計答案.
\(f[i]=f[i-1]\) , \(g[i]=0\).

3.此時為 \(?\) ,那么我們對于以上兩種情況都有 \(0.5\) 的概率.
然后直接轉移:
\[f[i]=0.5*(f[i-1]+2*g[i-1]+1+f[i-1])\]
\[g[i]=0.5*(g[i-1]+1+0)\]

然后最后面 \(f[n]\) 即為答案.