0.前言：
数学期望当前在OI中是一个类似于数论方面门槛的知识，在竞赛中有考察。本文将详细的讲解此内容，但也不是只纠缠于简单的概念，而会解决一些题目.可能这样介绍的知识对于大佬来说还是比较基础，但对像我这样的萌新来说通俗易懂，所以请各位大佬不要喷我。
1.什么是期望?
日常生活中，我们每做一件事，都有对它的期望，这里的期望不仅仅只结果的胜负之类，也可以与状态有关。但在OI中，一般指的就是达到结果的期望，最朴素的计算是每次可能结果的概率乘以其结果的总和
这是最基本的数学特征。
广义下的定义：一次随机抽样中所期望的某随机变量的取值。
数学定义：
2.引入：
问题1：
先看一个问题：
甲乙两个正常人赌博，丙作为裁判监督，五局三胜，赢家可以获得100元的奖励。当比赛进行到第四局的时候，甲胜了两局，乙胜了一局，但这时赌场遇到了警察的查封，丙见势不妙，立马逃走了，甲乙两人被迫中止了比赛，那么，如何分配这100元？（每局都能分出胜负）
方案1：
每人50元。
这显然是和平解决问题的方式，此时乙会赞成，但是甲一定有意见，显然，自己已经拿下赛点，不可能心甘情愿的平均分钱。
方案2：
按照获胜的概率分。
假设比赛继续进行，那么下一轮：
50%:甲赢，拿下100元。
50%：乙赢，继续比赛。
但是，如果问题就进行到这里，也就没有接下来的期望了。
当然，如果乙在暗中操纵下赢了，那么再下一轮中，
甲乙两人都有50%的概率获胜，拿下100元。
甲乙：？？这怎么算？
再次观察。
假设甲最终在想象中输了，那么他是在什么概率下输的呢？
\(\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}\)
他实际上只有四分之一的概率输。
显而易见，因为每局都能分出胜负，所以他有\(\frac{3}{4}\)的概率赢掉。
那么情况就简单了，我们根据他们的胜率来分钱。
甲分\(100\times \frac{3}{4}=75\)元
乙分\(100\times \frac{1}{4}=25\)元
此游戏完结~
问题2：
一位公司招募员工，几乎没有什么面试，甲乙两个年轻人就意外的获得了一份工作，这时，面试官却说要给他们发入司奖金，每人需要从各自的三个红包中选择一个。
此时，他们已知红包中有一个1000元的，两个500元的。
两位年轻人各自抽取了一个。
他们刚要打开红包，面试官却制止了他们，随机打开每人剩下红包中的一个，相同的，里面都装着500元钱。
于是面试官向他们询问：如果同意你们用手上的红包换取未打开的红包，你会换吗？
乍一看，这是一个无厘头的问题，可能有些意气风发的人便想到坚持自我等诸多大道理，或者暗自猜测面试官在红包上做了什么标记。
但也有些人想把握机会。
凑巧，甲坚持了原来的选择，乙却尝试了机会。
表面上看，这是一个完全机会均等，拼手气的选择。
但真的是这样吗？
稍加理性分析，我们可以得到一个初步的结论，帮助我们做出选择：
如果员工刚开始恰巧选择了1000元，他不交换会得到1000元，而显然有更大概率他刚开始选到了500元，那么他相应的就只能得到500元了。
由此，选择交换会获得更大的收益。
当然，我们可以不仅仅停留在定向判断。
下面定量计算一下：
设为A，B，C三个红包
当员工选择了A红包后，就将三个红包分为两组，第一组为A红包，第二组为B、C红包。很明显1000元在第一组的概率为\(\frac{1}{3}\)，在第二组的概率为\(\frac{2}{3}\)，而面试官打开了B红包，发现B为500元红包，这里其实是帮助员工在第二组里筛选掉了一个错误答案，所以1000元在C红包的概率其实为\(\frac{2}{3}\)。
所以就要换喽
当然，看到是面试官来做这个实验就知道这还是一个面试环节
于是甲就被炒鱿鱼了
但是，当甲走到门口时，面试官灵机一动，告诉他可以再回答一个问题。
于是甲满怀激动地走了过来。
面试官把向两人踢出提出了下一个问题：
如果给你手上的红包，让你换已经打开的呢？（打开的那个是500元）
显然无论如何都是不换的于是两人完美的成为了同事
面试官因招到了人完美的收到了4000元
3.例题1：
刚才的故事就是数学期望的一个简单应用，两个人都有对自己赢钱的期望（理性分析），便成功的解决了问题。
但是对模型：每次可能结果的概率乘以其结果的总和
的使用却并不是很明显
那么
下面给出一道入门题目，可用以上知识解决：
- 题意简叙：
一个01串中每个长度为\(X\)的全1子串可贡献\(X^3\)的分数。
给出n次操作的成功率\(p[i]\)，求期望分数。
分析：
我们可以观察到每次对答案的贡献是三次方级别的。
吼啊，我不会三次方期望啊。
仔细观察，首先发现一次方的期望是很好弄的。
于是设\(a[i]\)表示前i位中第i位为1的长度的期望：
则有
\[a[i]=(a[i-1]+1)\times p[i]\]
tag：即为在i-1的末尾加一个概率为\(p[i]\)出现的1
接着推平方
设\(b[i]\)表示前i位中第i位为1的长度的平方的期望：
则有
\[b[i]=(b[i-1]+2\times a[i-1]+1)\times p[i]\]
\[x^2->(x+1)^2->x^2+2x+1\]
运用这种方法，我们可以在求出\(a[i]\)的基础上推出\(b[i]\)
同理，设\(f[i]\)表示前i位中第i位为1的长度的立方的期望：
则有：
\[f[i]=(f[i-1]+3\times b[i-1]+3\times a[i-1]+1)\times p[i]\]
- 哇塞我要A紫题了！！！
然后在满心欢喜的提交上去后发现wa了。
显然，我们还有没考虑到的地方？
是什么呢？
是最后求得的答案与中间过渡式子的不同性。
其实，前三个式子我们都只考虑第i位，这样做是为了递推下面的式子，但是答案让我们求出最终的期望分数，也就是前n位，这时输出f[n]自然就炸了。
所以，只需把三次方递推式稍微变形一下即可；
\[f[i]=(f[i-1]+3\times b[i-1]+3\times a[i-1]+1)\times p[i]+f[i-1]\times (1-p[i])=f[i-1]+(3\times b[i-1]+3\times a[i-1]+1)\times p[i]\]
这样最终的\(f[n]\)就是答案喽！
code：
//AC记录：https://www.luogu.org/record/21569138
#include<cstdio>
using namespace std;
double a[100005],b[100005],f[100005],p[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf",&p[i]);
a[i]=(a[i-1]+1)*p[i];
b[i]=(b[i-1]+2*a[i-1]+1)*p[i];
f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p[i];
}
printf("%.1lf\n",f[n]);
return 0;
}
学好数学期望，递推AC紫题！(其实这应该算dp
4.例题2：
思考题：
tag：这道题笔者并没有找到题目出处，如有发现者，欢迎在评论区留言！
给定一个无向图，每个点可以等概率地走到与它有边的点
求从1走到n所需要的期望步数
N<=500
分析：
\(F[i]\)表示从i走到n的期望步数
\(F[n]=0\);
\(F[i]=aver\){\(f[j]\)}\(+1\),\((i,j)\)有边
tag：
天哪上面这张图小的洛谷都水印不上了？？
构成n元一次方程组
高斯消元？
5.例题3
https://www.luogu.org/problem/P2911
我怎么开始讲红题了真是trl
- 题意简叙：
三个骰子，每个面的概率均等，显然，三个面相加能得到一个唯一的数，而得到这个唯一的数却有多种不同的组合方法。
现在你需要求出哪个和出现的概率最大。
解法1：
这题的数据范围很小，直接暴力跑三重循环就行了。
解法2：
这里我闲的没事用了与期望相关的知识来简化了一下。但是这里只是定向的判断一下。
直接计算骰子的期望，得：
\[\frac{(a+b+c+3)}{2}\]
但是这个想法却有考虑不周的情况，这里留给读者思考。
6.例题4
题目链接：
https://www.luogu.org/problem/UVA10288
- 题意简叙：
每张***上有一个漂亮图案，图案一共n种，如果你集齐了这n种图案就可以召唤神龙兑换大奖。
现在请问，在理想（平均）情况下，你买多少张***才能获得大奖的？
\(n\leq33\)
分析：
本题我们设已经有了k个图案
令
\[a=\frac{k}{n}\]
设拿到一种新的图案需要t次。
则概率为：
\[a^{t-1}(1-a)\]
则平均需要（已提出了（1-a））:
\[(1-a)(1+2a+3a^2+4a^3+5a^4+...)\]
即为
\[E(1-a)\]
而此时我们需要观察其和\(E(a)\)的关系：
\[E(a)=a+2a^2+3a^3+4a^4+...=E-1-a-a^2-a^3...\]
整理可得
\[E(1-a)=1+a+a^2+a^3=\frac{1}{1-a}\]
然后代换一下
\[E(1-a)=\frac{n}{n-k}\]
这样结论就显而易见了：
假设有k个图案在手，那么平均再买\(\frac{n}{n-k}\) 次就可以再得到一种新的图案，故可得总次数为：
\[(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\frac{1}{n-3}+\frac{1}{2}+1)n\]
但是这样最后可能会得到一个分数，这就导致输出变得并不是那么方便为自己偷懒找理由
7.期望与均值？
期望与均值是两个十分相近的概念，但又可以说是截然不同。
均值往往是在实验中简单的对数据进行平均。
而期望就好像在上帝视角的人。
举个掷骰子的例子：
我们的均值怎么算呢？
显然要掷上一定多的次数来求平均数。
比如，掷了6次，分别为1,5,5,6,3,3，那么均值为
\[\frac{1+5+5+6+3+3}{6}=3.8333333...\]
居然无限循环小数...看来我是自己出数坑自己
可是期望呢？
我们不用掷骰子就能计算出来：
可以看出，两个值是有明显差别的，而且还时刻不同。
但是为什么容易弄混呢？
因为我太弱了在将多个均值求均值后，两者就无限接近了。
8、期望的小性质：
- 设X是随机变量，C是常数，则\(E(CX)=C\times E(X)\)
简单证明一下：
设x 的多个随机变量为
\[Ca_1,Ca_2,Ca_3\]
对应的出现概率为
\[p_1,p_2,p_3\]
那么对应的求期望的式子
\[E(CX)=C(a_1\times p_1 +a_2\times p_2 +a_3\times p_3 )\]
(C提出来)
由于：
\[E(X)=a_1\times p_1 +a_2\times p_2 +a_3\times p_3\]
所以
\[E(CX)=C\times E(X)\]
下面的可以自行思考，都不难
设X，Y是任意两个随机变量，则有\(E(X+Y)=E(X)+E(Y)\)。
设X，Y是相互独立的随机变量，则有\(E(XY)=E(X)\times E(Y)\)。
设C为常数，则\(E(C)=C\)。
9、期望的应用
***问题
在买***中，大多数人相信基本上是没法中奖的，但还是有少数人幻想，于是就再这里简要分析一个***问题的期望.
设一张***为2元，每售\(1000000\)张开奖，假设中奖号码为\(342356\)，则每张***有一个对应的六位数号码，奖次如下：（中奖不叠加）
末位相等,安慰奖：奖励4元，中奖概率0.1%
后两位相等,幸运奖：奖励20元，中奖概率0.01%
后三位相等,手气奖：奖励200元，中奖概率0.001%
后四位相等,一等奖：奖励2000元，中奖概率0.0001%
后五位相等,特等奖：奖励20000元，中奖概率0.00001%
某大佬：咦我六位都相等，快给我200000元！！！
***公司:你没看你这一项没有吗？你只是特等奖（我是不会告诉你再给钱就亏了
那到底为什么亏了呢
我们来用简单的概率知识来计算一下，对于每一位购买***的用户，公司可能支出为：
\[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元！
回到刚才大佬的疑问，显然，如果按照开奖规律继续的话，公司会少赚200000元！！
这显然是一笔不小的损失
***公司：我这怎么给员工发工资？！
dalao:
由此可见，***公司售卖***会让买家有惊现不同的体验（奖次不同），但即使是随机生成***号码，卖得多了所支出的钱一定在期望值附近，而能保证稳定的收入，而且***单价低，还有可能中那么多奖，买的人多，这样***市场才得以持续下去。
10、条件期望
这种期望的求解一般是在有一定条件下的。废话
如下题：
假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
分析：
第一眼，我的答案是3
至于如何得出的，在这里就不卖关子了，因为上面的答案是错的！
思考一下，为什么呢？
我们再读一下题：
假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
求在骰子只出现过偶数的条件下扔骰子次数的期望。
只出现过偶数的条件
只出现过偶数
只出现
只
抽丝剥茧
细细的考虑一下，题目所说的并不是指出现奇数就pass再扔，而是出现奇数就终止了操作！！！
所以把条件这样转换后，就可以得到正确答案：\(\frac{3}{2}\) 了
什么？你问怎么得到的？
那我把题意转换一下：
假设你不断扔一个等概率的六面骰子，直到扔出1,3,5，6停止。求骰子最后一次是6次数的期望。
这样再结合前面的知识，大家应该都明白了吧。
这类问题属于数学期望中较有拓展的知识，考察的概率较低，感兴趣者可作为兴趣钻研。其实也不难
n.后记：
期望的定义等少数内容为了精准参考了百度百科即其他大佬的blog等,本文如有错误，欢迎大佬指正
京公网安备 11010502036488号