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

概率论

概念

概率

如果随机变量是实数意义即为连续型,否则为离散型

要特别注意题目求的是不是条件概率,记$P(A|B)$表示已知B发生的前提下,A发生的概率

贝叶斯公式:$P(AB)=P(A|B)P(B)=P(B|A)P(A)$,理解不难,适当变形(例如已知结果发生问途径的概率)

期望

定义式:$E(x)=\sum_{t} P(x=t)t$

经典式子:$E(x)=\int_{0}^{\infty} P(x \ge t) dt-\int_{-\infty}^{0} P(x \le t) dt$

期望的线性性:任意两个变量X和Y都满足 $E(X+Y)=E(X)+E(Y)$

如果求A的期望,想办法把A拆成若干个变量的和然后求每个变量的期望的和

比较经典的应用:

  1. 期望逆序对数,只需要考虑两个变量间期望贡献,再求和;

  2. 期望虚树大小,只要考虑每条边出现在虚树中的概率;

  3. 恰好到达的状态的概率*步数之和,等价于所有未到达的状态(状态中包含步数)的概率之和(理解的话可以想成把终止状态的步数分摊到上面每个未结束状态上,如果要数学理解可以看概率生成函数)

期望的乘法

若变量X和Y独立, $E(XY)=E(X)E(Y)$

值得一提的是,例如$E(X)=3Y,E(XY)=E(3Y^2)$是正确的,怀疑的可以写下式子,可见这方面还是很灵活的,可以多多培养直觉

经典问题

  1. 经典题:OSU

  2. 掷骰子问题:几个经典方法

  3. 处理$E(x^k)$的常用方法是化成$\sum_{i=0}^k S_2(k,i)i! E(C_x^i)$。

    以刚刚的掷骰子问题,使用无限和式为例,记$x=步数$,记$p \in (0,1)$为失败概率:
    $$
    f_k=E(C_x^k)=\sum_{x=0}^{\infty} C_{x+1}^k p^{x}(1-p)=\sum_{x=0}^{\infty} (C_{x}^{k-1}+C_x^k) p^{x}(1-p)
    \\
    f_k=p\sum_{x=0}^{\infty} C_{x}^{k-1} p^{x-1}(1-p)+p\sum_{x=0}^{\infty} C_x^k p^{x-1}(1-p)
    =p(f_k+[k=1]\frac{1-p}{p} +f_{k-1})
    \\
    f_0=1,f_1=\frac{1}{1-p},f_{k>1}=\frac{p}{1-p} f_{k-1}
    $$

方差

方差记为 $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 n个随机实数的第k小的期望

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

众所周知最小随便积分($E(minx)=\int_0^1 P(min \ge x)dx=\int_0^1 (1-x)^ndx=\frac{1}{n+1}$),最大翻转一下$E(maxx)=1-E(minx)=\frac{n}{n+1}$

看到地震后的幻想乡的题面,发现k任意也可以求,找到两种方法:A,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}$。注意到每种投影的概率不同,但因为权值相同,所以没有影响

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

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}=\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}$

CF280C Game on TreeCF235D Graph Game

非概率生成函数题单

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

CF1153F Serval and Bonus Problem:积分处理期望线性运用于连续随机变量

题意:给出一个长度为L的线段,在上面随机出n条线段,问被覆盖至少k次的面积的期望,$n \le 2e3$

一眼秒但过不去样例自闭1h,看题解才发现题意其实是随机两个没有大小关系的端点来确定哪个是左端点的

做法:显然L没有意义当做长度1最后乘L即可,容斥f恰g至,期望线性性,$g_i=\sum_{j=i}^n C_j^i f_j=C_n^i \int_0^1 2^ix^i(1-x)^idx$

二项式定理得$g_i=C_n^i2^i \sum_{j=0}^i C_i^j(-1)^j \int_0^1x^{i+j}dx$,应该可以FFT优化,似乎也有不少其他做法

1
2
3
fo(i,0,n) fo(j,0,i) add(g[i], C[i][j]%MOD*(j&1?MOD-1:1)%MOD*invm(i+j+1)%MOD );
fo(i,0,n) g[i]=g[i]*C[n][i]%MOD*qpower(2,i)%MOD;
ll ans=0;fo(i,k,n) fo(j,i,n) add(ans, ((j-i)&1?MOD-1:1)*C[j][i]%MOD*g[j]%MOD );write(ans*L%MOD);

bzoj2554 Color:条件概率做期望

$$
很自然地先考虑两种颜色,只关心一种颜色当前个数,e_i=\frac{e_{i-1}+e_{i+1}}{2}+\frac{1}{ \frac{2i(n-i)}{n(n-1)} },e_0=e_1=1,手动解方程即可
\\
多个颜色想用上述做法必须考虑条件概率,枚举颜色,ans+=最后是这种颜色的概率*最后是这种颜色前提下的期望步数
\\
算概率的话考虑到一定满足\sum_{ \sum a_i=n } p_{a_i}=1可知p_i=i/n,当然也可以p_i=\frac{p_{i-1}+p_{i+1}}{2}
\\
关键是条件概率下的期望(可以抱着学习的心态看):\\
E_i=\frac{1}{ \frac{2i(n-i)}{n(n-1)} }+\frac{p_{i-1}e_{i-1}+p_{i+1}e_{i+1}}{p_{i-1}+p_{i+1}},即考虑从那里开始做,满足条件的概率,来确定对期望的贡献
$$

1
2
3
4
5
6
e[n-1][1]=1;//不知为何只能在darkbzoj通过
fd(i,n-1,2)
e[i-1][0]=e[i][0]*(2*i)/(i-1)-e[i+1][0]*(i+1)/(i-1)-1.0*n*(n-1)/(n-i)/(i-1),
e[i-1][1]=e[i][1]*(2*i)/(i-1)-e[i+1][1]*(i+1)/(i-1);
assert(e[1][1]!=e[2][1]);double E=(n/2+e[2][0]-e[1][0])/(e[1][1]-e[2][1]);
fo(id,0,25) ans+=(e[cnt[id]][0]+e[cnt[id]][1]*E)*cnt[id]/n;printf("%.1lf",ans);

Fibonacci’s Nightmare:递推式与期望的小例题

题意:$a_0=1,a_n=a_i+a_j,其中i和j在[0,i)中随机选择,求D(a_n),n \le 1e6$
$$
记S_n=\sum_{i=0}^n a_n ,E(a_n)=\frac{1}{n^2} E(\sum_{i,j \in [0,n)} a_i+a_j)=\frac{2}{n} E(S_{n-1}) \\E(S_n)=E(S_{n-1})*\frac{n+2}{2}=C_{n+2}^2,E(a_n)=n+1 \\E(a_n^2)=\frac{1}{n^2} E( \sum_{i,j \in [0,n)} (a_i+a_j)^2 )=\frac{2}{n} \sum_{i,j \in [0,n)} E(a_i^2)+\frac{2}{n^2} E( S_{n-1}^2 )\\E(S_{n}^2)=E( S_{n-1}^2+a_{n}^2+2a_nS_{n-1} ),此时只能带入E(a_n)=\frac{2}{n} E(S_{n-1})(保留自变量) \\得到E(S_{n}^2)=E(S_{n-1}^2)+E(a_n^2)+\frac{4}{n}E( S^2_{n-1}),O(n)
$$
神仙加强——coj16G

概率生成函数

$$
对于非负整数集上离散变量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$

硬币游戏:对每个串,求出这种串是最早出现的概率,$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的概率清零,类似将概率收集到z^0的感觉;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、「集训队作业2018」喂鸽子

AGC038E题解,喂鸽子也差不多,值得一提的是存在$O(n^2k)$的优美做法,但貌似没法优化我惯用(即前者题解中那种)的做法,因为主要针对$(\sum_{i=0}^{k}\frac{x^i}{i!})^c$

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