概率期望小结

摘要

Tqy 奆奆给我们讲概率啦

概率与期望

概率空间

三元组 . 被称为概率空间:

  1. 样本空间 是一个非空集合
  2. 集合 的元素是 的子集, 是样本空间 的幂集的非空子集,即 .
  3. 概率测度 满足
    • .
    • .

条件概率

定义在 B 条件下 A 的概率为,在事件 B 发生时事件 A 发生的概率

简记为

全概率公式

的一个划分,且 ,则有

贝叶斯公式

对于满足 , 有

推论: 为一个划分

随机变量

一个随机变量是一个从样本空间 到一个可测空间 的一个函数 。一般而言

若对于两个随机变量 , 有

则称 X 和 Y 是独立的。

期望

一个随机变量的数学期望或是均值定义为它取值的平均值:

期望的线性性

对于常数

对于两个独立随机变量 X 和 Y, 有

快速排序期望比较次数

方差

随机变量 X 的方差定义为

因为常量的期望是其本身,所以 .

概率生成函数

对于一个随机变量 , 定义其概率生成函数 (pgf) 为

小练习 1

给定一个从 S 到 T 的 DAG, 每到一个点会从所有出边中等概率选一条边走过去,求从 S 到 T 的期望路径长度。

倒着期望 DP, 表示从 的期望路径长度

复杂度 .

小练习 2

有 n 块布,每次从中等概率随机选一个染色,求所有布都被染色所需的期望染色次数。

表示还剩 块布没染,染完的期望次数

复杂度 .

[BZOJ4318]OSU!

有一个长度为 的序列,第 个位置有 的概率为 , 的概率为 , 一个序列的分数是所有极长连续 的长度的三次方和。求期望分数。

我们不妨先考虑贡献 的分数的情况

那么定义 表示第 个数结尾的极大 1 串的期望贡献,显然

注意,是第 i 个数的期望贡献,其贡献与前一个数结尾的极大 1 串的贡献有关

再考虑 的分数的情况

注意到 ,那么定义 表示第 个数结尾的极大 1 串的期望贡献

再考虑 的分数的情况

所以我们的答案怎么统计呢?你发现了,这样的递推式是关于第 个数结尾的极大 1 串的,却不是关于第 个数的贡献。因此我们尝试在这个递推式中分离出第 个数的贡献。显而易见,第 个数的贡献是

至于 表示的是上一个期望对这一次的贡献,不属于第 个数的贡献

那么答案即为

#include<cstdio>
using namespace std;
const int N=1e5+5;
int n;
double p[N];
double f1[N],f2[N],ans;

int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
    for(int i=1;i<=n;i++)f1[i]=p[i]*(f1[i-1]+1),
        f2[i]=p[i]*(f2[i-1]+2*f1[i-1]+1),ans+=p[i]*(3*f2[i-1]+3*f1[i-1]+1);
    printf("%.1lf",ans);
    return 0;
}

复杂度 .

[BZOJ3270] 博物馆

给定一个 n 个点 m 条边的无向图,有两个人分别从 A 和 B 出发在图中随机游走。每个人都遵循规则:如果当前在点 u 则在当前时间他有 的概率呆在 u 不动,有 的等概率在所有相邻点中选择一个走过去。问两个人走到同一个点所需要的期望时间。 .

我们考虑两个人的位置, 表示 A 在 i,B 在 j 时,他们走到一起的期望时间

由于 ,那么 一共最多有 项,那么对这个式子做一次高斯消元,复杂度 .

构造

考虑一条链的情况

那么前面构造一个团,后面一条链,两者点数对半开,

一个点数为 n 的团的路径长度期望为 .

那么总期望

咕咕

AC 自动机上期望 dp

转移的时候局部高斯消元,整体 DAGDP

SRM614

考虑边界点

模型

在一个分层循环 DAG 上游走,那么在某一层破环为链,转化为线性的期望 DP

HDU4035

树形 dp,

对于叶结点,递归向上维护 abc
那么由子结点的 abc 维护当前结点的 abc 就可以只 dfs 维护 abc 即可

LOJ2125

考虑最后一个 1(需要翻转的位置),这个位置必翻转其本身

假设 P1,p2,,pk 需要翻转,这是指一个翻转方案,已经保证了答案的正确性

那我们就要求这些位置翻转奇数次,其他位置翻转偶数次

那么我们维护仍需要翻转的个数,dp[i] 表示仍需要翻转 i 次的期望次数

注意 我们维护的是翻转方案序列,已经保证了答案的正确性

小练习 3

做异或差分, ,那么区间翻转(区间异或)转化为端点异或,那么就可以向之前一样 DP 啦

CTSC2017

当前的胜率只和前后的确定位置(结果)有关

概率矩阵乘法

小练习 4

根据期望的线性性,我们求经过每一条边的期望次数再求和即可

两边的子树随机选,然后就可以算出经过一条边的概率,即期望次数


  转载请注明: Sshwy's Blog 概率期望小结

 上一篇
后缀自动机初步 后缀自动机初步
摘要 在 XRY 大佬倾力指点下,我学会了 SAM,也是很神仙了 后缀自动机(Suffix Automaton)是能够识别某一字符串的后缀的自动机,在处理后缀与子串问题上有广泛的运用 后缀自动机形式化定义后缀自动机是一种有限状态自动机,对
2019.02.14
下一篇 
字符串小结 字符串小结
KMP 复杂度的证明咕咕 一道题 给一个串, 支持插入删除最后面的字符, 求循环节的长度。这里的循环节是整个串的循环节,任意一个都可以. 求循环节就相当于求 Next 指针,考虑 Next 指针的构建过程。当前的 Next 指针是建立在
2019.02.12
  目录