$1^{st}$ 什么是期望

感觉是一个比较难懂的东西（

假设某随机试验$X$共有$n$种互斥的事件可能发生，其中第i个事件发生的概率为$P_i$，价值为$X_i$，则这个随机试验的期望是$E(X)=\sum P_i{X}_i$。

很不好懂，对吧

那么我们只需要把它简单的理解为加权平均数就好

$2^{ed}$ 期望的一些性质

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

证明：

$$左式=\sum _{i,j}(X_i+Y_i)P_i{Q}_j$$$(P_i,Q_i分别为X和Y第i个事件发生的概率)$

$$=\sum _{i,j}{X}_i{P}_i{Q}_j+\sum _{i,j}{Y}_i{P}_i{Q}_j+$$

$$=\sum _i{X}_i{P}_i\sum _j{Q}_j+\sum _j{Y}_j{Q}_j\sum _i{P}_i$$

这里${\sum }_j{Q}_j、{\sum }_i{P}_i$都为$1$，对吧（自己用概率理解一下）

$$=\sum _i{X}_i{P}_i+\sum _j{Y}_j{Q}_j$$

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

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

证明：

$$左式=\sum _{i,j}{X}_i{Y}_i{P}_i{Q}_i$$

$$=\sum _i{X}_i{P}_i\sum _j{Y}_j{Q}_j$$

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

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

part3. 期望具有常数可乘性。$E(\alpha X)=\alpha E(X)$

证明：$$左边=\sum \alpha X_i{P}_i$$

$$=\alpha \sum _i{X}_i{P}_i$$

即 $E(\alpha X)=\alpha {\sum }_{i}XiPi=\alpha E(X)$

4.可以利用数归推广 $2$ 和 $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^{rd}$ 例题

觉得应该先看例题，配合着例题理解可能会更好

题目

一个n面的骰子，求期望掷几次能使得每一面都被掷到。

例题link

题解

一个期望DP的常用状态设计方法：

dp[i]表示当前已选了 $i$ 种点数，还需一直选到 $n$ 种点数的丢骰子数的期望。

显然dp[n]=0，答案为dp[0]

现在考虑转移：

则每次丢骰子有两种状态。

• 和之前的点数一样，有 $\frac{i}{n}$ 的概率出现。记为 $X$。
• 和之前的点数不一样，有 $\frac{n-i}{n}$ 的概率出现。记为 $Y$。

那么所以当前这一状态 $E(i)=E(X)+E(Y)$

那么根据定义，$X$ 的概率为 $\frac{i}{n}$，价值为 $d{p}_i$，$Y$ 的 概率为 $\frac{n-i}{n}$，价值为 $d{p}_{i+1}$。

而每种状态一定都会丢一次，所以我们的 $d{p}_i$ 还需累加 $100\%$，也就是$1$。

于是我们得到式子： $d{p}_i=\frac{n-i}{n}d{p}_{i+1}+\frac{i}{n}d{p}_i+1$

接下来化简该式

$\frac{n-i}{n}d{p}_i=\frac{n-i}{n}d{p}_{i+1}+1$

因为转移时$n\ne i$

所以两边同时约掉$\frac{n-i}{n}$

$d{p}_i=d{p}_{i+1}+\frac{n}{n-i}$

那么我们就可以打出代码了

#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;
} 

今天的文章（期望DP）【总结】期望DP分享到此就结束了，感谢您的阅读。