1 期望
1.期望的定义
每次可能结果的概率乘以其结果的总和
2.期望的性质
\(X\)是随机变量，\(C\)是常数，则\(E(CX)=C\times E(X)\)
证明：设\(X\)的多个随机变量（即能取到的数值为）\(\{{a_{i}}\}\)，对应出现概率为\(p_i\)，则求期望的式子是：
\[E(X)=\sum_{i=1}^n(a_ip_i) \]
而随机变量变为\(CX\)，即\(\{Ca_i\}\)时，求解式子变为：
\[E(CX)=\sum_{i=1}^n(Ca_ip_i)=C\sum_{i=1}^n(a_ip_i)=CE(X) \]
以下式子证明类似：
- 设\(X,Y\)是任意两个随机变量，则有\(E(X+Y)=E(X)+E(Y)\)
- 设\(X,Y\)是两个相互独立的随机变量，有\(E(XY)=E(X)E(Y)\)
- 设\(C\)为常数，有\(E(C)=C\)
3.期望与均值
比如掷骰子的均值，计算方法：
【你必须亲自掷骰子，然后才能知道，比如】
\[\dfrac{1+5+5+6+3+3}{6}=3.833333... \]
而期望无需亲自操作 如：
\[E(X)=1\times\dfrac{1}{6}+2\times \dfrac{1}{6}+...+6\times \dfrac{1}{6}=\sum_{i=1}^6(\dfrac{1}{6}i) \]
该数值恒定
在对多个均值求均值后，两者就无限接近了。
4.例题1
题面
甲乙两人赌博，丙作为裁判，五局三胜，赢的人可以获得100元，比赛进行到第四局的时候甲胜了2局，乙胜了1局，但这时赌场遇到了查封，丙逃走。这时甲乙应该如何分配100元？（每局一定有胜负）
A 平分
A胜利更多，已经拿到赛点。他显然不愿意
B 按照获胜的比例
继续进行一轮的话，
50%：甲赢了，拿走100元。
50%：乙赢了，继续比赛。
那如果下一局乙赢了，接下来两人又有50%的概率获胜，都可能拿走100元，还咋分？
C 学会期望的人应该这样做（吧）
假设甲最终输了，那么他是在什么概率下输的呢？
\(\dfrac{1}{2}\times \dfrac{1}{2}=\dfrac{1}{4}\)
他实际上只有四分之一的概率输。
显而易见，因为每局都能分出胜负，所以他有 \(\dfrac{3}{4}\)的概率赢掉。
那么情况就简单了，我们根据他们的胜率来分钱。
甲分 \(100\times \dfrac{3}{4}=75\)
乙分 \(100\times \dfrac{1}{4}=25\)
5.例题2
题面
已知3个红包中有一个1000元的，两个500元的。
抽取了一个后，随机打开剩下红包中的一个，里面装着500元钱。
询问：如果同意你们用手上的红包换取未打开的红包，你会换吗？
题解
下面定量计算一下：
设为\(A,B,C\)三个红包
当员工选择了\(A\)红包后，就将三个红包分为两组，第一组为\(A\)红包，第二组为\(B,C\)红包。很明显1000元在第一组的概率为 \(\dfrac{1}{3}\)，在第二组的概率为 \(\dfrac{2}{3}\)，而面试官打开了B红包，发现B为500元红包，这里其实是帮助员工在第二组里筛选掉了一个错误答案，所以1000元在C红包的概率其实为 \(\dfrac{2}{3}\)。
所以就要换喽
6.例题3
设一张彩票为2元，每售1000000张开奖，假设中奖号码为 342356，则每张彩票有一个对应的六位数号码，奖次如下：（中奖不叠加）
末位相等,安慰奖：奖励4元，中奖概率0.1
后两位相等,幸运奖：奖励20元，中奖概率0.01
后三位相等,手气奖：奖励200元，中奖概率0.001
后四位相等,一等奖：奖励2000元，中奖概率0.0001
后五位相等,特等奖：奖励20000元，中奖概率0.00001
我们来用简单的概率知识来计算一下，对于每一位购买彩票的用户，公司可能支出为：
\(0.1\times 4+0.01\times 20+0.001\times 200+0.0001\times 2000+0.00001\times 20000=1.2\)
也就是说，公司期望对每个人赚0.8元。
每1000000张，就是800000元！
如果6位均相等，给200000元的话，公司会少赚200000元！！（可以计算一下）
7.例题4
题面
抛一枚硬币，如果是反面就继续抛，问抛 出正面的期望次数。 ]
（期望话可以理解为概率\(\times\)代价， 比如说小A投球中的概率为\(\dfrac{1}{3}\)，那么投三 个球中的期望就是\(\dfrac{1}{3}\times 3=1\)）
题解
\(x=1+\dfrac{1}{2}\times 0+\dfrac{1}{2}\times x\)发现递归下去了。
解这类方程其实需要运用极限的思想，但 是一种简单的解法是直接移项整理解出x=2 即可
这个期望dp最好的例子
附上我的证明
\(C_i=a_ib_i,a_i=i,b_i=\left( \dfrac{1}{2}\right)^i\)，则:
\[S=\sum C_i=\sum a_ib_i=1\times\left( \dfrac{1}{2}\right)+2\times \left( \dfrac{1}{2}\right)^2+...+n\left( \dfrac{1}{2}\right)^n \]
\[\dfrac{1}{2}S=1\times\left( \dfrac{1}{2}\right)^2+2\times \left( \dfrac{1}{2}\right)^3+...+n\left( \dfrac{1}{2}\right)^{n+1} \]
\[T=S-\dfrac{1}{2}S=1\times \left( \dfrac{1}{2}\right)+\left( \dfrac{1}{2}\right)^2+\left( \dfrac{1}{2}\right)^3+...+\left( \dfrac{1}{2}\right)^n-n\left( \dfrac{1}{2}\right)^{n+1} \]
\[T=S-\dfrac{1}{2}S=\left[ \left( \dfrac{1}{2}\right)+\left( \dfrac{1}{2}\right)^2+\left( \dfrac{1}{2}\right)^3+...+\left( \dfrac{1}{2}\right)^n\right]-n\left( \dfrac{1}{2}\right)^{n+1} \]
\[M=\left( \dfrac{1}{2}\right)+\left( \dfrac{1}{2}\right)^2+\left( \dfrac{1}{2}\right)^3+...+\left( \dfrac{1}{2}\right)^n=1-\left( \dfrac{1}{2}\right)^{n} \]
\[T=S-\dfrac{1}{2}S=M-\dfrac{n}{2}\left( \dfrac{1}{2}\right)^{n}=1-\left(\dfrac{n}{2}+1\right)\left( \dfrac{1}{2}\right)^{n} \]
\[S=2-\left(n+2\right)\left( \dfrac{1}{2}\right)^{n} \]
8.例题5-UVA10288
前置知识
概率为\(p\)的事件期望\(\dfrac{1}{p}\)次后发生
\(p\)：在\(x\)次独立重复事件中，该事件发生\(xp\)次；
\(\dfrac{1}{p}\):该事件发生\(x\)次，所需独立重复事件发生\(\dfrac{x}{p}\)次。
题面
每张彩票上有一个漂亮图案，图案一共\(n\)种，如果你集齐了这\(n\)种图案就可以兑换大奖。
现在请问，在理想（平均）情况下，你买多少张彩票才能获得大奖的？
\(n\leq33\)
分析
设我们已经有了\(k\)个图案，则得到下一张新的牌的概率为\(\dfrac{n-k}{n}\).【前置知识】得到下一张牌的期望是\(\dfrac{n}{n-k}\)
定义\(E(i)\)表示\(i-1\)到第\(i\)张牌的期望，根据期望的线性性质可得：
\[E(X)=\sum_{i=1}^nE(i) \]
\[E(X)=\sum_{i=1}\dfrac{n}{n-i} \]
\[E(X)=n\sum_{i=1}^n\dfrac{1}{i} \]
模拟分数相加的过程，同分之后相加化简。
9.例题6-高次期望-P1654
题面
一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 \(X\) 个\(1\) 可以贡献 \(X^3\) 的分数，这\(X\)个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）
现在给出\(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。
样例
输入
3
0.5
0.5
0.5
输出
6.0
说明
000分数为0，001分数为1，010分数为1，100分数为1，101分数为2，110分数为8，011分数为8，111分数为27，总和为48，期望为48/8=6.0
\(N\leq 100000\)
题解
我们设\(E(X_{i})\)为在第 \(i\)个位置得的分数的期望
然后我们考虑 \(E(X_{i+1})\)和 \(E(X_{i})\)的关系
假设在\(i\)位置连续\(1\)串长度为 \(l\)的概率为 \(p_{l}\)，在 \(i+1\)位置是 \(1\) 的概率为\(P\) ，那么对于每一个单独的 \(l\) 它都有\(P\)的概率对分数产生 \((3l^{2}+3l+1)\)的额外贡献
我们把所有可能的 \(l\) 一起考虑，就可以得到这个式子
\[E(X_{i+1})=E(X_{i})+\sum_{l=0}^{i}p_{l}\times P(3l^{2}+3l+1) \]
然后我们可以发现
\(\sum_{l=0}^{i}p_{l}l^{2}=E(l^{2})\)
\(\sum_{l=0}^{i}p_{l}l=E(l)\)
于是我们将式子转化为
\(E(X_{i+1})=E(X_{i})+P\times(3E(l_{i}^{2})+3E(l_{i})+1)\)
然后我们就成功得出了分数的期望
同时我们也要维护\(E(l)\)和\(E(l^{2})\)
\(l\)和\(l^{2}\)都有 \(1\)~\(P\) 的概率变成0，\(P\)的概率增加
增加的量可以用上面类似的方法算出
\[E(l_{i+1})=P\times(E(l_{i})+\sum_{l=0}^{i}p_{l})=P\times(E(l_{i})+1) \]
\[E(l_{i+1}^{2})=P\times(E(l_{i}^{2})+\sum_{l=0}^{i}p_{l}(2l+1))=P\times(E(l_{i}^{2})+2E(l_{i})+1) \]
由此我们就得出了全部的递推关系
其实三个量完全不用用数组存，只要改变一下转移顺序就行了
代码
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
double ex,el,el2,P;
int main(){
scanf("%d",&n);
while(n--){
scanf("%lf",&P);
ex=ex+P*(3*el2+3*el+1);
el2=P*(el2+2*el+1);
el=P*(el+1);
}
printf("%.1f",ex);
return 0;
}
10.例题7-P4450
题面
\(n\)个数\(1\)~\(n\)，第\(k\)次取数需要\(k\)元，每次取数对于所有数概率均等(\(\dfrac{1}{n}\)),问取完\(n\)个数的期望花费
首先第一步很好转化吧，设用了\(x\)步，则花费为
\[\sum_{i=1}^{x}i=\dfrac{x^2+x}{2} \]
现在就转换成要求上式的期望。
有了前面那题的基础现在考虑起来就简单了
维护一个线性期望\(a\)，平方期望 \(f\)（都是数组）
\(a[i]\)表示找完\(i\)个数之后还需要的次数的期望
\(f[i]\)表示找完\(i\)个数之后还需要的次数平方的期望
不难想到最后的答案是 \(\dfrac{a[0]+f[0]}{2}\)
下面就开始考虑状态转移（dp？）
先来考虑 \(a[i]\)
\[a[i]=? \]
情况1，买到买过的
买过的是i个，概率为 \(\dfrac{i}{n}\),花费就相当于记在买到i时候的账上了（从\(i\)账上查），得到花费为 \(a[i]+1\)
可得到式子\(\dfrac{i}{n}(a[i]+1)\)
情况2，买到没买过的
没买过的是\(n−i\)个，概率为 \(\dfrac{n-i}{n}\),花费就相当于记在买到\(i+1\)时候的
账上了（从\(i+1\)账上查），因为当前多买了一个，得到花费为 \(a[i+1]+1\)
可得到式子 \(\dfrac{n-i}{n}(a[i+1]+1)\)
两种情况一合并，得：
\(a[i]=\dfrac{i}{n}(a[i]+1)+\dfrac{n-i}{n}(a[i+1]+1)\)
这时就发现了，推着推着出现了\(i+1\)，自然而然的想到了倒推
边界 \(a[n]=0\)都得全了还买什么
但是这个式子固然能做，是不是麻烦了点？
那么把它化简后发现：
\(a[i]=a[i+1]+\dfrac{n}{n-i}\)
然后考虑\(f[i]\)
跟推a的时候一个思路，新的或旧的，唯一就把平方拆开就行喽
\(f[i]=\dfrac{i}{n}(f[i]+2\times a[i]+1)+\dfrac{n-i}{n}(f[i+1]+2\times a[i+1]+1)\)
倒推
边界 \(f[n]=0\)
可算，但麻烦
化简
OK既然上面讲了写式子下面就说说化简的事吧~
\[f[i]=\frac{i}{n}(f[i]+2\times a[i]+1)+\frac{n-i}{n}(f[i+1]+2\times a[i+1]+1) \]
把第一个括号拆成 \(f[i]\)和 \(2\times a[i]+1\)两部分
然后把
\[\frac{i}{n}\times f[i] \]
给移到左边，合并得：
\[\frac{n-i}{n}f[i]=\frac{i}{n}(2\times a[i]+1)+\frac{n-i}{n}(f[i+1]+2\times a[i+1]+1) \]
然后两边同除 \(\dfrac{n-i}{n}\)
\[f[i]=\frac{i}{n-i}(2\times a[i]+1)+f[i+1]+2\times a[i+1]+1 \]
就简单一些了。
代码中精度转换注意一下，不要丢失
代码
#include<cstdio>
using namespace std;
double a[10005],f[10005];
int main()
{
int n;
scanf("%d",&n);
a[n]=0;
f[n]=0;
for(int i=n-1;i>=0;i--)
{
a[i]=a[i+1]+1.0*n/(n-i);
f[i]=1.0*i/(n-i)*(2*a[i]+1)+f[i+1]+2*a[i+1]+1;
}
printf("%.2lf\n",(f[0]+a[0])/2);
return 0;
}
11. 条件期望
【考察概率较低，感性理解】
假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
细细的考虑一下，题目所说的并不是指出现奇数就pass再扔，而是出现奇数就终止了操作！！！
所以把条件这样转换后，就可以得到正确答案： \(\dfrac{3}{2}\)了
那我把题意转换一下：
假设你不断扔一个等概率的六面骰子，直到扔出\(1,3,5,6\)停止。求骰子最后一次是6的次数的期望。