「OI之路」03数学-15概率论

概率论

一些概率论中比较有用的不等式及证明

概念

一些定义

定义连续型随机变量为在实数域或区间上取连续值的随机变量,若不连续则为离散型
概率函数(又叫分布律),为随机变量取某个元素的概率的函数

概率分布函数是概率函数的前缀和
在连续型中,不存在概率函数,定义概率密度函数f满足 $概率分布函数F(x)=\int_{-\infty}^x f(t) dt$

连续型随机变量的数学期望,要求概率密度函数的积分(即概率分布函数)收敛

期望

经典柿子:$E(x)=\int_{0}^{\infty} P(x \ge t) dt-\int_{-\infty}^{0} P(x \le t) dt$
若变量X和Y独立, $E(XY)=E(X)E(Y)$
任意两个变量X和Y都满足 $E(X+Y)=E(X)+E(Y)$

经典的几个方法,证明一个经典问题,思想很有用

经典题:OSU

期望有个套路的转化,恰好到达的状态的概率*步数之和,等价于所有未到达的状态(状态中包含步数)的概率之和,这个你可以通过「把当前概率推到上面的步数个祖先上」理解

方差

方差记为 $D(x)或Var(x)=E[(E(x)-x)^2]=E[E^2(x)+x^2-2xE(x)]=E(x^2)-E^2(x)$
协方差记为 $Cov(X,Y)=E[(X-EX)(Y-EY)]=E(XY)-E(X)E(Y)$

运算律:$D(cX)=c^2 D(X),D(X \pm Y)=D(X)+D(Y) \pm 2Cov(X,Y)$

经典模型

A NOIP2018初赛某题

[0,1]上随机变量A、B,问E(|A-B|)
设 $X=max-min,E(X)=Emax(A,B)-Emin(A,B)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}$
另外, $D(X)=E(X^2)-E^2(X)=E(min^2+max^2-2min \times max)-1/9=1/6+5/6-2*(1/4)-1/9=1/18$

B 将1随机分为n份第k小段的期望

这里随机的严谨定义为 $n-1个[0,1]上随机变量,划分为n段$
如果k=1, $E=\int_0^{1/n} (1-nx)^{n-1} dx=\frac{1}{n^2}$
k>1考虑数学归纳法
$$
\begin{aligned}
& 已知 V1,V2..Vi,则 (V_{i+1}-V_i) \leq … (V_n-V_i)\\
& V_{i+1}=V_i+\frac{1- (\sum_{i=1}^i V_i)-(n-i)V_i }{(n-i)^2}\\
& 可得 V_k=\frac{1}{n} \sum_{i=1}^k \frac{1}{n-i+1}
\end{aligned}
$$
如果没看懂:某文章zhihu

C n个随机实数的第k小的期望

只讨论在[0,1]间随机的情况,其他直接放缩就好了

众所周知最大可以直接积分,最小翻转一下( $E(min x)=\frac{1}{n+1}$),看到地震后的幻想乡的题面,发现k任意也可以求

有两种方法:A,B;B比较简单说B,就是 $\sum_{all} \frac{1}{all} a_{p_k}=\sum_{all} \frac{1}{all} [新变量s \leq a_{p_k}]$

将所有点取值情况投影到数轴,对于某种投影,共$(n+1)!$种情况,有 $k \times n!$ 种合法,即 $\frac{k}{n+1}$

注意到每种投影的概率不同,但因为权值相同,所以没有影响

D n个随机不重整数的第k小的期望

设值域为$[1,m]$,要求$O(1)$
$$
\sum_{i=1}^m i*C_{i-1}^{k-1} C_{m-i}^{n-k}*\frac{1}{C_m^n},拆开组合数得C_n^k*k* \sum_{i=1}^m \frac{C_{m-n}^{i-k}}{C_m^i},然后就不会怎么化了……
\\正确的做法是\sum_{i=1}^m k*C_i^k C_{m-i}^{n-k}*\frac{1}{C_m^n},组合数卷积得 \frac{k}{C_m^n}*C_{m+1}^{n+1}=k*\frac{m+1}{n+1}
$$

E 一个经典的杀人模型转化+容斥

PKUWC2018 猎人杀uoj390「UNR #3」百鸽笼

F 一类通过差分解决转移方向问题的期望dp

XSY2472 string KMP及[CTSC2006]歌唱王国loj2145「SHOI2017」分手是祝愿CF1264C Beautiful Mirrors with queries

直接列式子可能可以,但转移方向会有点问题,发现期望式子向某个方向延伸很短,考虑跨过某过程所需期望(即差分)来设状态能让转移单向

G 一种dag上删除的期望模型

给出一个dag,选择一个点就会把自己和所能到达的所有点删除,每次随机选择一个没有被删除的点删除,问期望步数

考虑一个点被选择的概率,等价于对期望的贡献,设有k个点可到达自己,感性理解一下应该和别的点无关,$\frac{1}{k+1}$

非概率生成函数题单

CF258D Little Elephant and Broken Sorting

$f(a,b)表示a>b的概率,每次只修改2n个值,O(n^2)$ code

CF605E Intergalaxy Trips

$f(x)$表示x到n的期望时间,然后做期望题不急着考虑转移,而是考虑最后满足怎样的关系式

注意到转移只会从期望值小的到大的,那么设a为按f从小到大排序的编号,则一定满足:

$f(a_i)=1+\sum_{j=1}^i f(a_j)p(a_i,a_j)\prod_{t=1}^{j-1}(1-p(a_i,a_t))$,将i=j的部分移到左边,就是可以转移的东西了

每次取出未拓展且最小的,更新其他未拓展的即可,$O(n^2)$

概率生成函数

$$
对于非负整数集上离散变量X,其概率生成函数为F(z)=E(z^X)=\sum_{i=0}^{\infty} P(X=i) z^i \\
显然F(1)=1,F’(1)=E(X),F^{(k)}(1)=E(X^{\underline k}),D(x)=F’’(1)+F’(1)-(F’(1))^2 \\
$$

还需要掌握求展开$z^A e^{Bz}转OGF后带入z=1的答案$:
$$
f(A,B)=\sum_{i=0}^{\infty}\frac{B^i}{i!} (i+A)!=\sum_{i=A} i^{\underline A} B^{i-A},下降幂的自然思路是i^{\underline A}=(i-1)^{\underline {A-1}}*A+(i-1)^{\underline A}
\\
f(A,B)=A*f(A-1,B)+B*f(A,B),f(0,B)=\frac{1}{1-B},f(A,B)=\frac{A}{1-B}f(A-1,B)=\frac{A!}{(1-B)^{A+1}}
$$

[CTSC2006]歌唱王国,求期望E、方差D

请先思考后再展开

对这类问题通用的部分:设F表示恰好结束,G表示尚未结束,$F+G=1+zG$

首先要知道$F’(1)$,求导得$F’+G’=G+zG’,F’(1)=G(1)$,其实就是上面那个期望的转化

然后也要知道$F’’(1)$,二次求导得$F’’+G’’=G’+G’+zG’’,F’’(1)=2G’(1)$

然后考虑本题的特性,在所有未结束状态后面拼上str保证结束,那么当提前结束时,有效的只是其某个border

$G*(z/m)^{L}=\sum_{i \in str的border} F*(z/m)^{L-i},G=\sum m^i*F*z^{-i}$

$G(1)=\sum m^i$;求导得$G’=\sum m^i(F’z^{-i}+F*(-i)z^{-i-1}),G’(1)=\sum m^i(F’(1)-i)$

YMD的论文题1、SDOI2017硬币游戏

题意:m种数字的概率不相同,数字i的概率为$P_i$,给出n个长度分别为$L_i$的串$S_i$,不断给串B末尾加字符,当B包含所有串时结束,问期望长度,$n \le 15,m \le 1e5,L_i \le 2e4$

loj2004「SDOI2017」硬币游戏的区别为,对每个串,求出这种串是最早出现的概率,$n,L \le 3e2$

请先思考后再展开

外面肯定套上min-max容斥,$max = \sum_T min(T) (-1)^{|T|+1}$,即只考虑T内元素,第一个出现时就结束

约定$P_i(l,r)=S_i的子串[l,r]所需概率,a_{i,j,ln}=S_j(L_j-ln+1,L_j)与S_i(1,ln)相等$

设$F_i(z)=最后以S_i结尾$,则$\sum_{i \in T} F_i+G=1+zG$

和上次类似的思想,$\forall i \in T, G*P_i(1,L_i)z^{L_i}=\sum_{j \in T} \sum_{ln} a_{i,j,ln}*F_j*P_i(ln+1,L_i)*z^{L_i-ln},G(1)=\sum_{j \in T} \sum_{ln} \frac{ a_{i,j,ln}F_j(1) }{P_i(1,ln)}$

这n条方程和$\sum_{i \in T} F_i(1)=1$组成n+1个变量的方程组;$O(n^2L)求a+O(2^nn^3)高斯消元$

至于硬币游戏,是本题意的弟弟版本,发现就是不需要min-max容斥,然后求$F_i(1)$,$O(n^2L+n^3)$,code

YMD的论文题2

题意:一个n面的骰子,有个初始为0的计数器,当投出奇数计数器清零,否则计数器加一且如果为n(保证偶)则结束,问结束时计数器的期望

请先思考后再展开

$$
\\ F(z)+G(z)=1+G(z)*\frac{z}{2}+G(1)/2,即1/2的概率清零;F(z)=G(z)*z/n
\\ F(1)=1 \rightarrow G(1)=n,F+G=1+Gz/2+n/2,F(z)=\frac{(n+2)z}{(2-n)z+2n}
\\ 然后求导,因为层数较多就不写过程了,总之的确可以得到F’(1)=\frac{2n}{n+2}
$$

「ZJOI2019」开关

已知三种做法,和上面那些明显不同,感觉也是挺有适用性的一种设状态方式,详情


下面进入做水题练手时间,手握强大工具,和其他做法的思维难度对比鲜明

hdu4652 Dice

请先思考后再展开

可能差分法也能做?
$$
\\ 对于询问1,颜色本质相同,G*(z/m)^n=\frac{F}{m}(\sum_{i=1}^n (z/m)^i),E=G(1)=\frac{1}{m}*(\frac{1-m^{n+1}}{1-m}-1)\\ 对于询问2,G*z^n*\frac{P_m^n}{m^n}=F*\sum_{i=1}^n \frac{P_{m-i}^{n-i}}{m^{n-i}} z^{n-i},G(1)=\sum_{i=1}^n \frac{m^i}{m^{\underline i}}
$$
记得特判op=0,m=1;另外不知为啥不能用快读,code

牛客挑战赛31D 雷的打字机

请先思考后再展开

设$G_i(z)=以字符i结尾,G=1+\sum G_i$,易得$G_i=(G-G_i)p_iz,G_i=G*\frac{p_iz}{1+p_iz},G=\frac{1}{1-\sum \frac{p_i}{1+p_i}}$,线性求n个数的逆元见套路集锦

AGC038E Gachapon

题解

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/3e6e.html
转载请注明出处,谢谢!