【复习】概率期望复习笔记

胡乱整理了有关期望的一些东西。

为什么自己老是学了就忘呢……

定义

什么“所有情况的概率加权平均值blabla”,一般用处不大?

或者形式化一点,$ \rm \mathbb{E}(X)=\sum_i(~\Pr(X=i)\cdot i~) $

期望的线性性

唔,这个地方其实应用是很广泛的。大概就是对于两个事件 $\rm X,Y$,$\rm \mathbb{E}(aX+bY)=aE(X) +bE(Y)$ 。

对于这东西的证明大概如下:

期望经典模型

容斥模型

有 $n$ 个随机变量 $\rm X[1…n]$,每个随机变量都是从 $\rm 1…S$ 中 随机一个整数,求 $\rm max(X[1…n])$ 的期望。

根据期望的线性性可以得到:

这个容斥技巧好像还是挺常见的吧?

等价模型

实际上是取球问题,大概思路就是取每一个球是独立的,这一点在期望的线性性上体现得比较明显:

放球问题 I

箱中有 $n$ 个球 $1…n$,你要从中拿 $m$ 次球,拿了后不放回,求取出的数字之和的期望 。

还是期望的线性性:

这个地方个人理解的为什么 $\Pr(X=i)=\dfrac{m}{n}$,是考虑首先显然每个球平等,且摸到之后贡献为 $1$,所以可以知道有 $\sum_{i=1}^{n}\mathbb{E}(X=i)=m$,那么由于每个球都一样,所以 $\Pr(X=i)=\mathbb{E}(X=i)=\dfrac{m}{n}$。

放球问题 II

箱中有 $n$ 个球 $1…n$,你要从中拿 $m$ 次球,拿了后放回,求取出的数字之和的期望 。

考虑无论放回不放回,拿到 $i$ 的概率都是 $\dfrac{1}{n}\times m$ ,所以和第一问结果一样。

放球问题 III

箱中有 $n$ 个球 $1…n$,你要从中拿 $m$ 次球,拿了后以 $p_1$ 的概率放回,以 $p_2$ 的概率放回两个和这个相同的球,求取出的数字之和的期望。

这个地方可能有点绕。但是就是“球球平等”的思想。虽然有点难理解,但是考虑 问题 I 中我们推导的过程只用了「球球平等」这一条,所以可知这样也是对的。

随机游走

…就是游走模型。大概就是说假设一个点的出度为 $k$,他么他有 $\dfrac{1}{k}$ 的概率走到周围其他点。

链上游走

在一条 $n$ 个点的链上随机游走,求从一段端走到另一端的期望步数

考虑分阶段进行。根据线性性,$ \mathbb{E}(T)=\sum_{i=1}^{n-1} \mathbb{E}(X_i)$。其中 $\mathbb{E}(X_i)$ 表示从 $i$ 第一次走到 $i+1$ 的期望步数。

然后我们列方程,考虑一步转移走到了 $ i+1$ 还是 $i-1$ :

解出来得

完全图游走

在一个 $n$ 个点的完全图上游走,求从一个点到另一个点期望步数。

完全图的话,每个点走到每个点的概率都是 $\dfrac{1}{n-1}$。于是这个题就有好多种不同的解法,比如用一个推论“概率为 $P$ 的事件期望 $\dfrac{1}{P}$ 次后发生”,就可以直接证明 $\mathbb{E}(t) = n-1$。

完全二分图游走

在一个 $2n$ 个点的完全二分图上游走,求一个点走到另一个点的期望步数。

解方程的思想,分类讨论是在同侧还是异侧。

记 $\mathbb{E}_a$ 表示在同侧的期望步数, $\mathbb{E}_b$ 表示在异侧的期望步数。那么考虑有:

然后解出来 $\mathbb{E}_b=2\cdot n-1,\mathbb{E}_a=2\cdot n$ …为什么感觉很不对的样子呢…但是这么列方程肯定是没错的。

菊花图游走

在一张 $n$ 个点的菊花图上游走,求从根走到另一个点的期望步数。

考虑一共有三种情况:

1、叶子走到根 $\mathbb{E}(a)=1$ 。

2、根走到叶子 $\mathbb{E}(b)=\dfrac{1}{n-1}+\dfrac{n-2}{n-1}\times (\mathbb{E}(c)+1)$。

3、叶子走到叶子 $\mathbb{E}(c)=1+\mathbb{E}(b)$。

解方程可以得到 $,$$\mathbb{E}(b)=2\cdot n-3,\mathbb{E}(c)=2\cdot 2-2$ 。

树上游走

在一棵 $n$ 个点的树上游走,问从根走到 $x$ 的期望步数。

唔,其实有好多不同版本,也可以就是从 $y$ 走到 $x$ 的期望步数,因为游走问题是不存在有根树的,所以直接把 $y$ 拽起来当根也没什么问题。然后就是考虑链做法里面的思想,设 $f_u$ 表示 $u$ 第一次走到他父亲的期望步数,然后就有方程

前者是走上去的,后者是不小心走下去的。然后期望的线性性加起来即可。

然后就是高消时间了

呃,或许这个是可以 up and down 的?好像不行,我傻了。

期望思考题

A

构造一张 $200$ 个点的无向图,使得上面从 $\rm S$ 走到 $\rm T$ 的随机游走期望步数 $\geq 100,0000$。

考虑是一条链的时候大概有 $O(n^2)$ 的期望步数,在一张完全图上有 $O(n)$ 的期望步数,于是就可以考虑在 $\rm S$ 上连出一张 $100$ 个点的完全图,然后在一条链连到 $T$,就是 $n^3$ 的期望步数。具体实现似乎需要微调的亚子233.

B

(1)

随机一个长度为 $n$ 的排列 $p$,问前 $i$ 个数字中 $p_i$ 是最大数字的概率。

…算都不用算就知道是$\dfrac{1}{i}$ 。

(2)

随机一个长度为 $n$ 的排列 $p$,问前 $i$ 个数字中 $p_i$ 是最大数字的 $i$ 的个数的平方的期望。

首先设 $x_i$ 表示第 $i$ 个数是不是前 $i$ 个数中最大的数字,那么 $x_i=0/1$。那么总个数 $\rm S=\it\sum x_i$,总个数的平方的期望就是 $\mathrm{\mathbb{E}(S^2)}=\mathrm{ E}((\sum x_i)^2)$,之后就开始化式子:

以上用的都是期望的线性性。然后最后考虑用(1)中的结论,$\Pr(x_i=1)=\dfrac{1}{i}$,就可以得到:

这东西显然是有平凡的通项公式,但是懒得推了233。

C

随机一个 $1\sim n$ 的排列,求 $i$ 在 $j$ 前面的概率。

这显然是 $\dfrac{1}{2}$ 。

D

(1)

随机一个长度为 $n$ 的排列,求一个长为 $m$ 的 子序列 $s[1…m]$ 在该排列中出现的概率。

考虑对称性,$n$ 排列对 $m$ 序列随机,也可以看做 $m$ 序列对 $n$ 排列随机。其实怎么想无所谓——更直观的是考虑重排 $s$,对于每一个随机序列,都有且仅有一种 $s$ 的重排方式会在其中作为子序列。所以答案就是 $\dfrac{1}{m!}$ 。

(2)

随机一个长度为 $n$ 的排列,求一个长为 $m$ 的连续子序列 $s[1…m]$ 在该排列中出现的概率。

思考同样的结论放在(2)里面到底多算了哪些情况。首先就是我们要乘上一个 $\dfrac{1}{\binom{n}{m}}$,因为现在不能从 $n$ 中随便选出 $m$ 个位置来放,只能选择相邻的 $m$ 项。但是这还不够,因为我们还少算了以每个元素开头的连续子序列情况,所以应该再乘上 $n-m+1$,于是答案就是

说句题外话,从不等关系来讲,会有 $\dfrac{(n-m+1)!}{n!} \leq \dfrac{1}{m!}$,因为(2)的方案数一定小于等于(1),那么(2)发生的概率一定小于等于(1)。然后移个项就会有 $(n-m+1)!m!\leq n!$ 这种东西;或者从组合意义上来讲,会有 $(n-m+1)!\leq \dfrac{n!}{m!}$,即“ $n-m+1$ 个不同元素的排列数小于等于从 $n$ 个不同元素里面选出 $n-m$ 个元素进行排列的方案数”。

By the way,当且仅当 $n=m$ 时等号成立。

呃,似乎并不是很有意思,我还以为能推出什么有意思的东西来着233

E

给一个序列,每次随机删一个元素,问第 $i$ 个元素和第 $j$ 个元素相邻的概率。

然而是个组合题。

考虑每个数是什么时候被删除的,按删除顺序组成一个序列。因为是随机删除,所以删除序列也是随机的。接着考虑删除序列里面 $[i…j]$ 这段区间的排列总方案数是 $(j-i+1)!$,当且仅当 $[i+1…j-1]$ 都被删除且 $i,j$ 还没被删除时合法,这样的方案数是 $(j-i+1-2)!\cdot P_2^2$,于是概率就是

F

给定⼀棵树,将他的边随机⼀个顺序后依次插⼊,求 $u,v$ 期望什么时候连通。

考虑两个点连通只与他们之间的边数有关。设这个数量为 $k$ ,可以知道答案为

即用线性性枚举「恰好第 $i$ 次连通」。

G

给 $1…n$ 这 n 个数,每次随机选择⼀个还在的数并且删掉他的所有约数,求期望⼏次删完

跟 CF280C 那题本质上很相似。考虑一个数被删掉当且仅当他的倍数被删掉,同时只会有自己被删掉时产生 $1$ 的贡献,所以可以知道答案就是 $\mathbb{E}(X)=\sum \dfrac{1}{\lfloor\frac{n}{x}\rfloor}$ 。

H

给定 $n$ 个硬币,第 $i$ 个硬币的价值为 $w_i$,每次随机取⾛⼀个硬币,获得的收益是左右两个硬币的价值的乘积,求期望总价值。

想了一会儿之后发现是个弱智题。

考虑这个问题里面的单位决策数应该是 $O(n^2)$ 级别的二元组 $(i,j)$,也就是考虑对每一组 $(i,j)$ 分别算概率,发现这个概率就是 $i,i+1,i+2\cdots j$ 中随机删数,$[i+1,j-1]$ 在 $i,j$ 之前被删掉的概率,于是就可以直接算了。

I

有 $n$ 个数 $a[1…n]$,每次等概率选出两个数,然后合并成⼀个新的数放回来,得到的收益是新的数的值,求总收益的期望。

自然是考虑分别计算每个数期望被选到的次数。然后对这个东西用线性性展开可以知道,可以分别求每个数在每一次合并中被选到的概率,那么就是

即每次选择两个堆合并、选到 $x$ 那个堆的概率。

J

给定⼀个数列 $w[1…n]$,随机⼀个排列 $h$,如果 $h[i]$ ⽐ $h[i-1]$ 和 $h[i+1]$ 都⼤,就获得 $w[i]$ 的收益,求期望收益。

自己想的方法是暴力组合,考虑用线性性展开之后,变成分别对每个数算自己成为最大值的概率,发现这个概率就是

然后可以展开得到

然后一个比较神奇的事情,后面那个 $\sum$ 是有闭形式的。即:

然后相乘之后可知…$\Pr(X=\max)$ 就是 $\frac{1}{3}$ 。实际上也可以从更感性的角度来理解,三个数里面,成为最大的数概率自然是 $\frac{1}{3}$ 。

K

有 $n$ 个⿊球,$m$ 个⽩球,每次等概率取出⼀个球(不放回),将取出来的球的颜⾊写成⼀个 $01$ 序列,求 01 的期望出现次数。

子任务编号分值$\max\{n,m\}$特殊性质
$\rm Subtask1$$5$$\leqslant 20$\
$\rm Subtask2$$30$$\leqslant 300$\
$\rm Subtask3$$25$$\leqslant 5000$\
$\rm Subtask4$$10$$\leqslant 5\cdot 10^6$$n=m$
$\rm Subtask5$$15$$\leqslant 10^6$\
$\rm Subtask5$$15$$\leqslant 10^{9}$\

5pts 做法

枚举所有可能的颜色排列,复杂度 $O(n\cdot 2^n)$。

20pts 做法

设 $X$ 表示出现次数,那么有

考虑这个 $X=i$ 怎么算,本质上是求 $01$ 排列有多少种方案存在恰好 $i$ 个 01,也就只需要计算 $i$ 个相隔距离 $\geq 1$ 的 $0$ 的方案数。这个地方想了一会儿没找到什么闭形式,于是打算直接 $dp$ 。

设 $f_{i,j,k,0/1}$ 表示前 $i$ 位有 $j$ 个 $0$ ,其中有 $k$ 个 $01$ ,且第 $i$ 位放了 $0/1$ 的方案数,那么有转移

然后算就好了,时空复杂度均为 $O(n^3)$ 。

60pts 做法

发现继续沿用对着每个 $i$ 求贡献的做法。发现本质上就是从长为 $n+m$ 的序列里面选出 $i$ 个不相邻的 0 的方案数。考虑转化一下这个问题。首先可以转化成从 $1\sim n +m$ 里面选择 $i$ 个不相邻的数的方案数。之后考虑对于选出来的数 $a_1,a_2,a_3\cdots a_i$ ,从小到大排序后一定满足

考虑令

发现这样随便选择两个相邻的 $b_{k},b_{k+1}$ 都会有

也就是从 $1\sim n+m-i$ 中选择可以相邻的 $\{b\}$ 的方案数等于在 $1\sim n+m$ 中选择不能相邻的 $\{a\}$ 的方案数。于是可以知道有 $i$ 个 $01$ 时的方案数就是

注意到因为序列其他位置的方案数也要考虑,所以需要再乘上一个剩下未知的方案数。但是注意到,剩下位置可能还会存在 $01$ ,所以 $f_i$ 本质上算的是「至少 $i$ 个的方案数」。设 $g_i$ 表示「恰好 $i$ 个的方案数」,那么可知:

因为有二项式反演:

然后就可以获得一个时空复杂度均为 $O(n^2)$ 的做法。

70pts 做法

有特殊性质 $n=m$。可以通过进一步对上一个做法用组合恒等式来化简,或者直接找规律,可以发现当 $n=m$ 时,$g_i=\binom{n}{i}^2$。于是就可以线性做了。

85pts 做法

并不会,有人来教教我吗?不过似乎二项式反演是可以做到 $\log^2$ 的?这可能需要什么多项式科技。

100pts 做法

发现对于期望,只需要算出所有情况下 $01$ 数量的总和,除以全部的合法排列数即可。考虑这个总和也是可以分开算的,即可以算对于每个可能出现的 01 计算与之对应的有多少贡献。于是答案就是:

化简一下可以得到答案为

复杂度 $O(\log n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
const int P1 = 550 ;
const int P2 = 5050 ;
const int P3 = 100010 ;

int n, m ;
int ans1 ;
int ans2 ;
int ans3 ;
int fac[P3] ;
int inv[P3] ;
int comb[P2][P2] ;
int f[P3], g[P3], h[P3] ;
int dp[P1 * 2][P2][P2][2] ;

int expow(int a, int b){
int res = 1 ;
while (b){
if (b & 1)
res = (ll)res * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return res ;
}

int main(){
cin >> n >> m ;
dp[1][1][0][0] = 1 ;
dp[1][0][0][1] = 1 ;
for (int i = 1 ; i <= n + m ; ++ i)
for (int j = 0 ; j <= m ; ++ j)
for (int k = 0 ; k <= m ; ++ k){
add(dp[i + 1][j][k][1], dp[i][j][k][1]) ;
add(dp[i + 1][j][k + 1][1], dp[i][j][k][0]) ;
add(dp[i + 1][j + 1][k][0], dp[i][j][k][0]) ;
add(dp[i + 1][j + 1][k][0], dp[i][j][k][1]) ;
}
for (int i = 1 ; i <= m ; ++ i)
h[i] = addn(dp[n + m][m][i][0], dp[n + m][m][i][1]) ;
for (int i = 0 ; i <= n + m ; ++ i) comb[i][0] = 1 ;
for (int i = 1 ; i <= n + m ; ++ i)
for (int j = 1 ; j <= i ; ++ j)
comb[i][j] = addn(comb[i - 1][j - 1], comb[i - 1][j]) ;
for (int i = 1 ; i <= m ; ++ i)
f[i] = (ll)comb[n + m - i][i] * comb[n + m - 2 * i][m - i] % P ; // comb[n + m][m] ;
for (int i = 1 ; i <= m ; ++ i)
for (int j = i ; j <= m ; ++ j)
(!(j - i & 1)) ? add(g[i], (ll)f[j] * comb[j][i] % P) : dec(g[i], (ll)f[j] * comb[j][i] % P) ;
for (int i = 1 ; i <= m ; ++ i) add(ans1, 1ll * h[i] * (ll)i % P) ;
for (int i = 1 ; i <= m ; ++ i) add(ans2, 1ll * g[i] * (ll)i % P) ;
ans3 = (ll)n * m % P * expow(n + m, P - 2) % P ;
ans1 = (ll)ans1 * expow(comb[n + m][m], P - 2) % P ;
ans2 = (ll)ans2 * expow(comb[n + m][m], P - 2) % P ;
printf("%d %d %d\n", ans1, ans2, ans3) ;
}