1 s t 1^{st} 1st 什么是期望

感覺是一個比較難懂的東西（

假設某隨機試驗 X X X共有 n n n種互斥的事件可能發生，其中第i個事件發生的概率為 P i P_i Pi?，價值為 X i X_i Xi?，則這個隨機試驗的期望是 E ( X ) = ∑ P i X i E(X)=\sum P_iX_i E(X)=∑Pi?Xi?，

很不好懂，對吧

那么我們只需要把它簡單的理解為加權平均數就好

2 e d 2^{ed} 2ed 期望的一些性質

1. E ( X + Y ) = E ( X ) + E ( Y ) E(X+Y)=E(X)+E(Y) E(X+Y)=E(X)+E(Y)

證明：

左 式 = ∑ i , j ( X i + Y i ) P i Q j 左式=\sum_{i,j}(X_i+Y_i)P_iQ_j 左式=i,j∑?(Xi?+Yi?)Pi?Qj? ( P i , Q i 分 別 為 X 和 Y 第 i 個 事 件 發 生 的 概 率 ) (P_i,Q_i分別為X和Y第i個事件發生的概率) (Pi?,Qi?分別為X和Y第i個事件發生的概率)

= ∑ i , j X i P i Q j + ∑ i , j Y i P i Q j + =\sum_{i,j}X_iP_iQ_j+\sum_{i,j}Y_iP_iQ_j+ =i,j∑?Xi?Pi?Qj?+i,j∑?Yi?Pi?Qj?+

= ∑ i X i P i ∑ j Q j + ∑ j Y j Q j ∑ i P i =\sum_iX_iP_i\sum_jQ_j +\sum_jY_jQ_j\sum_iP_i =i∑?Xi?Pi?j∑?Qj?+j∑?Yj?Qj?i∑?Pi?

這里 ∑ j Q j 、 ∑ i P i \sum_jQ_j、\sum_iP_i ∑j?Qj?、∑i?Pi?都為 1 1 1，對吧（自己用概率理解一下）

= ∑ i X i P i + ∑ j Y j Q j =\sum_iX_iP_i +\sum_jY_jQ_j =i∑?Xi?Pi?+j∑?Yj?Qj?

= E ( X ) + E ( Y ) =E(X) + E(Y) =E(X)+E(Y)

2. E ( X Y ) = E ( x ) E ( Y ) E(XY)=E(x)E(Y) E(XY)=E(x)E(Y)

證明：

左 式 = ∑ i , j X i Y i P i Q i 左式=\sum_{i,j}X_iY_iP_iQ_i 左式=i,j∑?Xi?Yi?Pi?Qi?

= ∑ i X i P i ∑ j Y j Q j =\sum_{i}X_iP_i \sum_{j}Y_jQ_j =i∑?Xi?Pi?j∑?Yj?Qj?

= E ( X ) E ( Y ) =E(X)E(Y) =E(X)E(Y)

3. E ( X ) = E ( X ) E ( Y ) E(X)=E(X)E(Y) E(X)=E(X)E(Y)

part3. 期望具有常數可乘性， E ( α X ) = α E ( X ) E(\alpha X)=\alpha E(X) E(αX)=αE(X)

證明： 左 邊 = ∑ α X i P i 左邊=\sum \alpha X_iP_i 左邊=∑αXi?Pi?

= α ∑ i X i P i =\alpha \sum_iX_iP_i =αi∑?Xi?Pi?

即 E ( α X ) = α ∑ i X i P i = α E ( X ) E(\alpha X)=\alpha \sum_iXiPi=\alpha E(X) E(αX)=α∑i?XiPi=αE(X)

4.可以利用數歸推廣 2 2 2 和 3 3 3，

E ( ∑ i A i ) = ∑ i A i S i , A = { X , Y , Z … } E(\sum_iA_i)=\sum_iA_iS_i,A=\{X,Y,Z…\} E(i∑?Ai?)=i∑?Ai?Si?,A={X,Y,Z…}

E ( ∏ i A i ) = ∏ i A i S i , A = { X , Y , Z … } E(\prod_iA_i)=\prod_iA_iS_i,A=\{X,Y,Z…\} E(i∏?Ai?)=i∏?Ai?Si?,A={X,Y,Z…}

3 r d 3^{rd} 3rd 例題

覺得應該先看例題，配合著例題理解可能會更好

題目

一個n面的骰子，求期望擲幾次能使得每一面都被擲到，

例題link

題解

一個期望DP的常用狀態設計方法：

dp[i]表示當前已選了 i i i 種點數，還需一直選到 n n n 種點數的丟骰子數的期望，

顯然dp[n]=0，答案為dp[0]

現在考慮轉移：

則每次丟骰子有兩種狀態，

• 和之前的點數一樣，有 i n \frac{i}{n} ni? 的概率出現，記為 X X X，
• 和之前的點數不一樣，有 n ? i n \frac{n-i}{n} nn?i? 的概率出現，記為 Y Y Y，

那么所以當前這一狀態 E ( i ) = E ( X ) + E ( Y ) E(i)=E(X)+E(Y) E(i)=E(X)+E(Y)

那么根據定義， X X X 的概率為 i n \frac{i}{n} ni?，價值為 d p i dp_i dpi?， Y Y Y 的 概率為 n ? i n \frac{n?i}{n} nn?i?，價值為 d p i + 1 dp_{i+1} dpi+1?，

而每種狀態一定都會丟一次，所以我們的 d p i dp_i dpi? 還需累加 100 % 100\% 100%，也就是 1 1 1，

于是我們得到式子： d p i = n ? i n d p i + 1 + i n d p i + 1 dp_i=\frac{n?i}{n}dp_{i+1}+\frac{i}{n}dp_{i}+1 dpi?=nn?i?dpi+1?+ni?dpi?+1

接下來化簡該式

n ? i n d p i = n ? i n d p i + 1 + 1 \frac{n-i}{n}dp_{i}=\frac{n?i}{n}dp_{i+1}+1 nn?i?dpi?=nn?i?dpi+1?+1

因為轉移時 n ≠ i n\neq i n?=i

所以兩邊同時約掉 n ? i n \frac{n-i}{n} nn?i?

d p i = d p i + 1 + n n ? 1 dp_{i}=dp_{i+1}+\frac{n}{n-1} dpi?=dpi+1?+n?1n?

那么我們就可以打出代碼了

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1005;
double dp[MAXN];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		dp[n]=0;
		for(int i=n-1;i>=0;i--){
			dp[i]=dp[i+1]+(double)n/(double)(n-i);
		}
		printf("%.2lf\n",dp[0]);
	}
return 0;
}