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

ShineEternal

2019-07-26 10:27:42

Personal

# -1.灌水 [这里阅读应该效果更佳](https://blog.csdn.net/kkkksc03/article/details/99619790) - 想了解更多关于数论的内容,可戳[这里](https://45475.blog.luogu.org/linear-equation-group) ![](https://i.loli.net/2019/08/13/JVikyN6KT3WhsrF.jpg) 感谢@command_block 大佬提出宝贵建议 也感谢洛谷及UVA的相关题目 如果有小瑕疵可以在评论区提出 内容可能有点多~~但很简单~~ ,望大家耐心食用 # 0.前言: 数学期望当前在OI中是一个类似于数论方面门槛的知识,在竞赛中有考察。本文将详细的讲解此内容,但也不是只纠缠于简单的概念,而会解决一些题目.可能这样介绍的知识对于大佬来说还是比较基础,但对像我这样的萌新来说通俗易懂,所以请各位口下留情。 --- # 1.什么是期望? 日常生活中,我们每做一件事,都有对它的期望,这里的期望不仅仅只结果的胜负之类,也可以与状态有关。但在OI中,一般指的就是达到结果的期望,最朴素的计算是**每次可能结果的概率乘以其结果的总和** 这是最基本的数学特征。 广义下的定义:一次随机抽样中所期望的某随机变量的取值。 数学定义:![](https://i.loli.net/2019/08/13/dgYoKerEswl6nCF.png) # 2、期望的小性质: - 设X是随机变量,C是常数,则$E(CX)=C\times E(X)$ 简单证明一下: 设x 的多个随机变量为 $$Ca_1,Ca_2,Ca_3...Ca_n$$ 对应的出现概率为 $$p_1,p_2,p_3...p_n$$ 那么对应的求期望的式子 $$E(CX)=C\sum_{i=1}^{n}(a_i\times p_i)$$ (C提出来) 由于: $$E(X)=\sum_{i=1}^{n}(a_i\times p_i)$$ 所以 $$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$。 # 3.期望与均值? 期望与均值是两个十分相近的概念,但又可以说是截然不同。 - 均值往往是在实验中简单的对数据进行平均。 - 而期望就好像在上帝视角的人。 举个掷骰子的例子: 我们的均值怎么算呢? 显然要掷上一定多的次数来求平均数。 比如,掷了6次,分别为1,5,5,6,3,3,那么均值为 $$\frac{1+5+5+6+3+3}{6}=3.8333333...$$ ~~居然无限循环小数...看来我是自己出数坑自己~~ 可是期望呢? 我们不用掷骰子就能计算出来: ![](https://i.loli.net/2019/08/13/tAKIfgyuY6xRZrD.png) 可以看出,两个值是有明显差别的,而且还时刻不同。 但是为什么容易弄混呢? 因为~~我太弱了~~在将多个均值求均值后,两者就无限接近了。 # 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}$。 #### 所以就要换喽 ~~当然,看到是面试官来做这个实验就知道这还是一个面试环节~~ ~~于是甲就被炒鱿鱼了~~ ![](https://i.loli.net/2019/08/13/IDQE7OWJugRGPVd.jpg) --- 但是,当甲走到门口时,面试官灵机一动,告诉他可以再回答一个问题。 于是甲满怀激动地走了过来。 面试官~~把~~向两人~~踢出~~提出了下一个问题: 如果给你手上的红包,让你换已经打开的呢?(打开的那个是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元!! ~~这显然是一笔不小的损失~~ 彩票公司:我这怎么给员工发工资?! ![](https://i.loli.net/2019/08/13/k3ewWJhVqpGPFS6.jpg) dalao: ![](https://i.loli.net/2019/08/13/RKk2D7MGLTZcmI8.jpg) 由此可见,彩票公司售卖彩票会让买家有~~惊现~~不同的体验(奖次不同),但即使是随机生成彩票号码,卖得多了所支出的钱一定在期望值附近,而能保证稳定的收入,而且彩票单价低,还有可能中那么多奖,买的人多,这样彩票市场才得以持续下去。 --- 提示区:下面两道题目为初级期望,大佬可跳过食用,直接到高次期望 --- # 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]=aver${$f[j]$}$+1$,$(i,j)$有边 tag:![](https://cdn.luogu.com.cn/upload/pic/65911.png) - 构成n元一次方程组 - 高斯消元? # 8.例题3 题目链接: 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$$ 但是这样最后可能会得到一个分数,这就导致输出变得并不是那么方便~~为自己偷懒找理由~~ --- **从下面开始是高次期望** # 9.例题4: 下面给出一道**入门**题目,可用以上知识解决:(真的,不要看它是紫题,其实不难) [戳](https://www.luogu.org/problem/P1654) - 题意简叙: 一个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]$$ $tag$:期望的线性延伸: $$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了。 ![](https://i.loli.net/2019/08/13/nr152QKgxqmH3Xv.jpg) 显然,我们还有没考虑到的地方? 是什么呢? 是最后求得的答案与中间过渡式子的不同性。 其实,前三个式子我们都只考虑**第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: ```cpp //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~~ ![](https://i.loli.net/2019/08/13/Ba9VxM6gkp3CvqQ.jpg) $tag:$这题还可以扩展到k次,也就是$X^k$,用二项式定理$O(nk^2)$解决 觉得不够快?食用NTT对其加速可以达到$O(nklog_k)$ # 10、例题5 最后一道题目 但这应该是个经典问题吧 和上面一道UVA题目有一点点像 行了不废话了放链接 https://www.luogu.org/problem/P4550 - 题意简叙: n个数1~n,第k次取数需要k元,每次取数对于所有数概率均等($\frac{1}{n}$),问取完n个数的期望花费 --- ### 分析: **这个题意千万别理解错了,不是买到k需要k元,而是第k次买需要k元。可能是题面就模糊,但是结合一下样例和难度颜色应该也能看出来** 这道题是那题的升级版,要用到高次的期望,但输出不用那么麻烦了。 首先第一步很好转化吧,设用了x步,则花费为 $$\sum_{i=1}^{x}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: ```cpp #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等,本文如有错误,欢迎大佬指正 **感谢您的阅读,点赞、评论是一种美德**