-1.灌水

这里阅读应该效果更佳

想了解更多关于数论的内容，可戳这里

感谢@command_block 大佬提出宝贵建议

也感谢洛谷及UVA的相关题目

如果有小瑕疵可以在评论区提出

内容可能有点多~~但很简单~~ ，望大家耐心食用

0.前言：

数学期望当前在OI中是一个类似于数论方面门槛的知识，在竞赛中有考察。本文将详细的讲解此内容，但也不是只纠缠于简单的概念，而会解决一些题目.可能这样介绍的知识对于大佬来说还是比较基础，但对像我这样的萌新来说通俗易懂，所以请各位口下留情。

1.什么是期望?

日常生活中，我们每做一件事，都有对它的期望，这里的期望不仅仅只结果的胜负之类，也可以与状态有关。但在OI中，一般指的就是达到结果的期望，最朴素的计算是每次可能结果的概率乘以其结果的总和

这是最基本的数学特征。

广义下的定义：一次随机抽样中所期望的某随机变量的取值。

数学定义：

2、期望的小性质：

设X是随机变量，C是常数，则 $E (C X) = C \times E (X)$

简单证明一下：

设x 的多个随机变量为

$C a_{1}, C a_{2}, C a_{3} . . . C a_{n}$

对应的出现概率为

$p_{1}, p_{2}, p_{3} . . . p_{n}$

那么对应的求期望的式子

$E (C X) = C <munderover> \sum i = 1 n </munderover> (a_{i} \times p_{i})$

(C提出来)

由于：

$E (X) = <munderover> \sum i = 1 n </munderover> (a_{i} \times p_{i})$

所以

$E (C X) = C \times E (X)$

~~下面的可以自行思考，都不难~~

设X，Y是任意两个随机变量，则有 $E (X + Y) = E (X) + E (Y)$ 。
设X，Y是相互独立的随机变量，则有 $E (X Y) = E (X) \times E (Y)$ 。
设C为常数，则 $E (C) = C$ 。

3.期望与均值？

期望与均值是两个十分相近的概念，但又可以说是截然不同。

均值往往是在实验中简单的对数据进行平均。
而期望就好像在上帝视角的人。

举个掷骰子的例子：

我们的均值怎么算呢？

显然要掷上一定多的次数来求平均数。

比如，掷了6次，分别为1,5,5,6,3,3，那么均值为

$\frac{1 + 5 + 5 + 6 + 3 + 3}{6} = 3.8333333...$

~~居然无限循环小数…看来我是自己出数坑自己~~

可是期望呢？

我们不用掷骰子就能计算出来：

可以看出，两个值是有明显差别的，而且还时刻不同。

但是为什么容易弄混呢？

因为~~我太弱了~~在将多个均值求均值后，两者就无限接近了。

4.引入：

问题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元~~

这其实是一个著名的三门问题，也称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论，这个问题因在数学逻辑推理上合理，但违背直觉而闻名于世

5、期望的应用

***问题

在买***中，大多数人相信基本上是没法中奖的，但还是有少数人幻想，于是就再这里简要分析一个***问题的期望.

设一张***为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:

由此可见，***公司售卖***会让买家有惊现不同的体验（奖次不同），但即使是随机生成***号码，卖得多了所支出的钱一定在期望值附近，而能保证稳定的收入，而且***单价低，还有可能中那么多奖，买的人多，这样***市场才得以持续下去。

提示区：下面两道题目为初级期望，大佬可跳过食用，直接到高次期望

6.例题1

https://www.luogu.org/problem/P2911

题意简叙：

三个骰子，每个面的概率均等，显然，三个面相加能得到一个唯一的数，而得到这个唯一的数却有多种不同的组合方法。

现在你需要求出哪个和出现的概率最大。

解法1：

这题的数据范围很小，直接暴力跑三重循环就行了。

解法2：

这里我~~闲的没事~~用了与期望相关的知识来简化了一下。但是这里只是定向的判断一下。

直接计算骰子的期望，得：

$\frac{(a + b + c + 3)}{2}$

但是这个想法却有考虑不周的情况，这里留给读者思考。

7.例题2：

思考题：

tag：这道题笔者并没有找到题目出处，如有发现者，欢迎在评论区留言！

给定一个无向图，每个点可以等概率地走到与它有边的点
求从1走到n所需要的期望步数
N<=500

分析：

$F [i]$ 表示从i走到n的期望步数
$F [n] = 0$ ;
$F [i] = a v e r$ { $f [j]$ } $+ 1$ , $(i, j)$ 有边

tag：

构成n元一次方程组
高斯消元？

8.例题3

题目链接：

https://www.luogu.org/problem/UVA10288

题意简叙：

每张***上有一个漂亮图案，图案一共n种，如果你集齐了这n种图案就可以~~召唤神龙~~兑换大奖。

现在请问，在理想（平均）情况下，你买多少张***才能获得大奖的？

$n \leq 33$

分析：

本题我们设已经有了k个图案

令

$a = \frac{k}{n}$

设拿到一种新的图案需要t次。

则概率为：

$a^{t - 1} (1 - a)$

则平均需要（已提出了（1-a））:

$(1 - a) (1 + 2 a + 3 a^{2} + 4 a^{3} + 5 a^{4} + . . .)$

即为

$E (1 - a)$

而此时我们需要观察其和 $E (a)$ 的关系：

$E (a) = a + 2 a^{2} + 3 a^{3} + 4 a^{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$

但是这样最后可能会得到一个分数，这就导致输出变得并不是那么方便~~为自己偷懒找理由~~

从下面开始是高次期望

9.例题4：

下面给出一道入门题目，可用以上知识解决：（真的，不要看它是紫题，其实不难）

戳

题意简叙：

一个01串中每个长度为 $X$ 的全1子串可贡献 $X^{3}$ 的分数。

给出n次操作的成功率 $p [i]$ ，求期望分数。

分析：

我们可以观察到每次对答案的贡献是三次方级别的。

吼啊，我不会三次方期望啊。

仔细观察，首先发现一次方的期望是很好弄的。

于是设 $a [i]$ 表示前i位中第i位为1的长度的期望：

则有

$a [i] = (a [i - 1] + 1) \times p [i]$

$t a g$ ：即为在i-1的末尾加一个概率为 $p [i]$ 出现的1

接着推平方

设 $b [i]$ 表示前i位中第i位为1的长度的平方的期望：

则有

$b [i] = (b [i - 1] + 2 \times a [i - 1] + 1) \times p [i]$

$t a g$ :期望的线性延伸：

$x^{2} - > (x + 1)^{2} - > x^{2} + 2 x + 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~~

$t a g :$ 这题还可以扩展到k次，也就是 $X^{k}$ ，用二项式定理 $O (n k^{2})$ 解决

觉得不够快？食用NTT对其加速可以达到 $O (n k l o g_{k})$

10、例题5

最后一道题目

但这应该是个经典问题吧

和上面一道UVA题目有一点点像

行了不废话了放链接

https://www.luogu.org/problem/P4550

题意简叙：

n个数1~n，第k次取数需要k元，每次取数对于所有数概率均等（ $\frac{1}{n}$ ）,问取完n个数的期望花费

分析：

这个题意千万别理解错了，不是买到k需要k元，而是第k次买需要k元。可能是题面就模糊，但是结合一下样例和难度颜色应该也能看出来

这道题是那题的升级版，要用到高次的期望，但输出不用那么麻烦了。

首先第一步很好转化吧，设用了x步，则花费为

$<munderover> \sum i = 1 x </munderover> i = \frac{(x^{2} + x)}{2}$

现在就转换成要求上式的期望。

有了前面那题的基础现在考虑起来就简单了

维护一个线性期望 $a$ ，平方期望 $f$ （都是数组）

好吧再清楚地表达一下：

$a [i]$ 表示找完i个数之后还需要的次数的期望

$f [i]$ 表示找完i个数之后还需要的次数平方的期望

不难想到最后的答案是 $\frac{a [0] + f [0]}{2}$

下面就开始考虑状态转移（dp？）

先来考虑 $a [i]$

$a [i] = ?$

情况1，买到买过的

买过的是i个，概率为 $\frac{i}{n}$ ,花费就相当于记在买到i时候的账上了（从i账上查），得到花费为 $a [i] + 1$

可得到式子 $\frac{i}{n} (a [i] + 1)$

情况2，买到没买过的

没买过的是 $n - i$ 个，概率为 $\frac{n - i}{n}$ ,花费就相当于记在买到i+1时候的

账上了（从i+1账上查），因为当前多买了一个，得到花费为 $a [i + 1] + 1$

可得到式子 $\frac{n - i}{n} (a [i + 1] + 1)$

两种情况一合并，得：

$a [i] = \frac{i}{n} (a [i] + 1) + \frac{n - i}{n} (a [i + 1] + 1)$

这时就发现了，推着推着出现了i+1，自然而然的想到了倒推

边界 $a [n] = 0$ ~~都得全了还买什么~~

但是这个式子固然能做，是不是麻烦了点？

那么把它化简看看能出来什么…

……&%&（）……&……&%……&%……*&%

一顿猛算后发现：

$a [i] = a [i + 1] + \frac{n}{n - i}$

当然如果熟练了，直接心算都没毛病啦~~

然后考虑 $f [i]$

唉有了前面osu的铺垫这还不是轻而易举？

跟推a的时候一个思路，新的或旧的，唯一就把平方拆开就行喽

$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 [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)$

然后两边同除 $\frac{n - i}{n}$

$f [i] = \frac{i}{n - i} (2 \times a [i] + 1) + f [i + 1] + 2 \times a [i + 1] + 1$

就简单一些了。

代码中精度转换注意一下，不要丢失

end

code：

#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、其他推荐题目

P1850 换教室 ————2016NOIPTG题目，dp+期望，值得一做
P3802 小魔女帕琪————也挺好，入门的分析

12、条件期望(略微进阶)

这种期望的求解一般是在有一定条件下的。废话

如下题：

假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。

分析：

第一眼，我的答案是3

至于如何得出的，在这里就不卖关子了，因为上面的答案是错的！

思考一下，为什么呢？

我们再读一下题：

假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。

求在骰子只出现过偶数的条件下扔骰子次数的期望。

只出现过偶数的条件

只出现过偶数

只出现

只

~~抽丝剥茧~~

细细的考虑一下，题目所说的并不是指出现奇数就pass再扔，而是出现奇数就终止了操作！！！

所以把条件这样转换后，就可以得到正确答案： $\frac{3}{2}$ 了

什么？你问怎么得到的？

那我把题意转换一下：

假设你不断扔一个等概率的六面骰子，直到扔出1,3,5，6停止。求骰子最后一次是6次数的期望。

这样再结合前面的知识，大家应该都明白了吧。

这类问题属于数学期望中较有拓展的知识，考察的概率较低，感兴趣者可作为兴趣钻研。~~其实也不难~~

n.总结&&后记：

其实期望看上去挺高深的东西，仔细研究一下也不难~

主要就是最基础的式子，然后高次的推导，其实很多题就是dp结合了数学期望方面的理论

找到了方向（其实上来基本就有方向）一顿猛推还挺有成就感，最后潇洒的码上几行极短的代码A掉。

唯一可能有难度的就是引用了二项式等知识（and条件期望？）

但这些也不怎么是事啦！

其实，后面某些题的做法还有一个名字叫概率dp

所以恭喜您又学了一种dp！

期望的定义等少数内容为了精准参考了百度百科即其他大佬的blog等,本文如有错误，欢迎大佬指正

感谢您的阅读，点赞、评论是一种美德

数论小白都能看懂的数学期望讲解

-1.灌水

0.前言：

1.什么是期望?

2、期望的小性质：

3.期望与均值？

4.引入：

问题1：

方案1：

方案2：

但是，如果问题就进行到这里，也就没有接下来的期望了。

问题2：

所以就要换喽

5、期望的应用

***问题

6.例题1

解法1：

解法2：

7.例题2：

分析：

8.例题3

分析：

9.例题4：

分析：

code：

10、例题5

分析：

先来考虑 a [ i ] a[i] a[i]

情况1，买到买过的

情况2，买到没买过的

然后考虑 f [ i ] f[i] f[i]

code：

11、其他推荐题目

12、条件期望(略微进阶)

分析：

n.总结&&后记：

其实，后面某些题的做法还有一个名字叫概率dp

先来考虑 $a [i]$

然后考虑 $f [i]$