「数学」概率与期望基础及简单套路笔记

概率与期望

本文是关于OI中基础概率与期望的讲解

前置知识

随机变量 : 随机的变量(逃),大概是在样本空间中的随机一个变量,下文中若无特殊说明,随机变量均为离散型随机变量

P(X) : 表示 X 事件发生的概率

E(X) : 一个离散性随机变量的期望值数学期望)是试验中每次可能的结果乘以其结果概率的总和,也就是

E(X)=\sum P(X=i) * i

其中 i 枚举的是 X 的所有可能情况

独立事件 : 两个事件 X Y 独立的 当且仅当 P(A\text{ 且 } B)=P(A) \times P(B) ,这里的 A \text{ 且 } B 表示 A B 两个事件都会发生的事件,这个乘法也被叫做独立事件的乘法原则

注: P(A\text{ 且 } B)=P(A) \times P(B) 是独立事件的 定义 而非独立事件的 性质

期望的性质

  1. 期望值 E 是线性函数,也就是对于任意的随机事件 X, Y 与任意的实数 a, b ,都有

\mathrm { E } ( a X + b Y ) = a \mathrm { E } ( X ) + b \mathrm { E } ( Y )

证明是十分显然的:

\begin{align}E(X+Y)&=\sum_{i} \sum_{j} P(X=i\text{ 且 } Y=j)(i+j)\\&=\sum_{i} \sum_{j} P(X=i\text{ 且 } Y=j)\times i + \sum_{i} \sum_{j} P(X=i\text{ 且 }Y=j) \times j\\&=E(X)+E(Y)\end{align}

这个东西是整个概率dp的基础

  1. 一般情况下,两个随机变量的积的期望值不等于这两个随机变量的期望值的积

当且仅当 两个随机变量是独立变量时,有 E(X\text{ 且 } Y)=E(X)\times E(Y)

常用技巧

前缀和 技巧,可以处理一些不好直接处理的情况

对于随机变量 X ,都有 P(X=K) = P(X\le K)-P(P\le K - 1) 或者 P(X=K) = P(X\ge K)-P(P\ge K + 1)

下面是一个应用这个性质的好例题

n 个随机变量 X_{1\cdots n} ,每个随机变量都是从 1\cdots S 中的随机⼀个整数,求 \max (X_{1\cdots n}) 的期望

Y=\max (X_{1\cdots n}) ,那么就是要求 E(Y) ,也就是

\begin{align} E ( Y ) &= \sum _ { i \in S} i \times P ( Y = i ) \\ &= \sum _ { i\in S } i ( P ( y \le i ) - P ( y \le i - 1 ) ) \\ &= \sum _ { i\in S } i \left( \left( \frac { i } { s } \right) ^ { n } - \left( \frac { i - 1 } { s } \right) ^ { n } \right) \end{align}

到这里就处理完了

这里还有一个广为人知的性质:

对于概率为 p 的事件 X 期望 1\over p 次后发生

Y X 尝试了 Y 次后发生,对于概率 P(Y=i) ,转化为 P(Y=i)=P(Y\ge i)-P(Y\ge i + 1)

对于 P(Y\ge i) ,只用考虑前 i - 1 次失败了,后面的和这个概率没有关系,即 P(Y\ge i)=(1-p)^{i-1}

那么

\begin{align}P(Y=i)&=P(Y\ge i)-P(Y\ge i + 1)\\&=(1-p)^{i-1}-(1-p)^{i}\end{align}

其实到这里就不要再化简了,因为

\begin{align}E(Y)&=\sum_{i \in \mathbb{N}^+} P(Y=i)\times i\\&=\sum_{i \in \mathbb{N}^+}\left((1-p)^{i-1}-(1-p)^{i}\right)\times i\end{align}

其中对于每一个 (1-p)^k 都会被 k k+1 算一遍,所以

\begin{align}E(Y)&=\sum_{i \in \mathbb{N}^+}\left((1-p)^{i-1}-(1-p)^{i}\right)\times i\\&=\sum_{i \in \mathbb{N}^+}(1-p)^i\\&=\lim_{i\to \inf}{1-(1-p)^{i}\over 1-(1-p)}\\&={1\over p}\end{align}

这个在生活中也是经常被无意中用到的...

比如抛硬币正面朝上的概率是 1\over 2 ,期望抛两次硬币就能抛到正面(

拿球问题

期望的线性性的小应用

Easy 1

箱⼦⾥有 n 个球 1\cdots n ,你要从⾥⾯拿 m 次球,拿了后放回,求取出的数字之和的期望

令选的球为 X_{1\cdots m} Y=\sum X_{i}

\begin{align}E(Y)&=E(\sum X_i)\\&=\sum E(X_i)\\&=\sum P(X_i=i) \times i\\&=\sum {m\over n} \times i\\&={m\over n}\times {n \times (n+1)\over 2}={m\times (n + 1) \over 2}\end{align}

Easy 2

箱⼦⾥有 n 个球 1\cdots n ,你要从⾥⾯拿 m 次球,拿了后不放回,求取出的数字之和的期望

令选的球为 X_{1\cdots m} Y=\sum X_{i}

不同的是,这个 X_i 可能是取不到的(,于是令

\begin{align}X_i=\left\{ \begin{array} { l } { i }\;\;\;\;\text{choose }i \\ { 0 }\;\;\;\;\text{otherwise} \end{array} \right.\end{align}

由于期望是线性函数,只需要考虑 E(X_i) 即可,即

E(X_i)=P(X_i=i)\times i

注意到 P(X_i=i) 就是 i 被选的概率,也就是

\begin{align}P(X_i=i)&={C_{n-1}^{m-1}\over C_n^m}\\&={m\over n}\end{align}

这个东西和 Easy 1 中是一样的,所以说对于 E(Y) 的计算可以直接照搬上面的过程

Easy 3

终于到这个问题的最终形式了

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

根据上面的结论,可以猜测答案也是 m\times (n+1)\over 2

这里就提供一种感性理解的方式,核心思想就是对于每个球,都有 球球平等

每个球都有概率被选中,都有同样的概率被放回去,也都有同样的概率放回两个,所以说选中第 i 个的概率始终是 m\over n

所以说无论以怎样的方法放回去,无论是放回去多少个,只要保证对于 每一个 球可以这样操作,那就球球平等

这个球也并非只代表本题的球,也可以代表抽象的东西(

随机游走

先解释随机游走的概念:

对于一个出度为 q ,出边为 \text{Out}_{1\to q} 的点 i ,每次通过它的第 1\to q 条出边走到与它相邻的点的概率为 1\over q

感性理解也就是对于一次随机游走,点 i 一定 会走到一个与它相邻的点(除非没有出边与其相连),走向与它相邻的点的概率是相等的

n 个点的链上随机游⾛,求从⼀端⾛到另⼀端的期望步数

令答案为 Y X_i 表示从 i 开始随机游走,走到 i+1 的步数,那么显然有

Y=\sum_{i=1}^{n-1} X_i

所以 Y 的期望为

\begin{align}E(Y)&=E(\sum_{i=1}^{n-1} X_i)\\&=\sum_{i=1}^{n-1}E(X_i)\end{align}

接下来就是要考虑 E(X_i) 的值

对于 X_i 来说,它可以走一步到 X_{i+1} ,也可以先后退再走到 X_{i+1} ,根据这个就可以推出来一个递推式

\begin{align}E(X_i)&={1\over2}\times 1 + {1\over2}\times\left(1+E(X_{i-1})+E(X_i)\right)\\&= 1 +{1\over2}\times E(X_{i-1})+{1\over2}\times E(X_i)\\E(X_i)&=2+E(X_{i-1})\end{align}

由于 E(X_1)=1 这个东西的和其实就是 (n-1)^2

完全图

n 个点的完全图上随机游⾛,求从一个点⾛到另⼀个点的期望步数

每次有 1\over n-1 的概率走到终点,期望 n-1 次走到终点

完全二分图

2n 个点的完全二分图上随机游⾛,求从一个点⾛到另⼀个点的期望步数

X 同侧点 要走的步数, Y 异侧点 要走的步数

同侧点可以转化为异侧点的问题,于是只需要考虑异侧点就好了

异侧点可以被一步走到或者是走错变成同侧点的问题,就是

\begin{align}E(Y)&={1\over n}\times 1+{n-1\over n}\times \left(E(X) +1\right)\\E(X)&=E(Y)+1\end{align}

E(X)=E(Y)+1 代入第一个式子,就可以解出 E(X) E(Y)

菊花图

n 个点的菊花图上随机游⾛,求从⼀个点⾛到另⼀个点的期望步数

注:菊花图就是 2\to n 个点均 有且仅有 一条与 1 的连边

显然这个要分三种情况:

  1. 两个点都在 2\to n
  2. 起点为 1 ,终点在 2\to n
  3. 终点为 1 ,起点在 2\to n

令三种情况的步数分别为 X,Y,Z

3 中情况中起点 只能 1 走,所以说 E(Z)=1

就像上面二分图的情况讨论即可

\begin{align}E(X)&=1+E(Y)\\E(Y)&={1\over n-1} \times 1+{n-2\over n-1}\times (E(X)+1)\end{align}

这个貌似与上面完全二分图看起来很像

其实一个菊花图就相当于一个 \{1|n-1\} 的完全二分图

n 个点的树上随机游⾛,求从根⾛到 x 的期望步数

令答案为 Y X_x 表示从 x 开始随机游走,走到 \text{father}_x 的步数,那么显然有

E(Y)=\sum E(X_i)

\text d_x x 的度数,那么有

\begin{align}E(X_i)={1\over \text d_i}\times 1+\sum_{\text{father}_y=i}{1\over \text d_i}\left(1+E(X_y)+E(X_i)\right)\end{align}

然后 树形DP 算一下这个就好了

构造

构造⼀张 200 个点的⽆向图,使得上⾯从 S ⾛到 T 的随机游⾛期望步数 \ge 1000000

现在需要构造出一个期望步数为 \text O(n^3) 级别的图

考虑长度为 n 的链的期望步数是 \sum E(X_i) 其中 E(X_i)=E(X_{i-1}) + 2 ,如果能将 E(X_1) 变为 O(n) 级别,就能完美完成

完全图做得到, 于是就让点数为 100 的完全图后接点数为 100 的链就好了, 起点就在完全图上的任意一个点, 重点就在链的端点

经典套路

  1. 每次随机⼀个 [1,n] 的整数,问期望⼏次能凑⻬所有数

Y 为凑齐所有数的次数, X_i 表示已经抽了 i 个数,再抽中一个不同的数的个数,那么有

P(X_i)={n-i\over n}

根据上面的结论,它的期望是

E(X_i)={n\over n - i}

所以

\begin{align}E(Y)&=E(\sum_i X_i)\\&=\sum_i E(X_i)\\&=\sum_i {n\over n - i}=\sum_i \frac n i\end{align}

  1. 随机⼀个⻓度为 n 个排列 p ,求 p[1\cdots i] p[i] 是最⼤的数的概率

脑筋急转弯题目(逃

参考上面的球球问题,每个数都是平等的,所以说每个数都有当最大的机会(,于是答案就是

1\over i

下面是通过理性证明分析这个问题:

考虑全部排列共有 i! 种,接下算合法的序列的方案数就好了

其实合法的序列相当于第 i 个位置被固定为最大值,其他 i-1 个数随便排列,也就是 (i-1)! 种方案

于是就有

\begin{align}P(p[i]=\max(p[1\cdots i])&={(i-1)!\over i!}\\&={1\over i}\end{align}

问满⾜上⾯那个题的 i 的个数的平⽅的期望

这个就不像上面那么直观了......

但是还是直接套模板就好了

Y 为为满足题目的 i 的个数,然后把 Y 拆成几个 X 的和

X _ { i } = \left\{ \begin{array} { l } { 1 } \quad p[i]=\max(p[1\cdots i]) \\ { 0 } \quad \text{otherwise} \end{array} \right.

拆一下式子

\begin{align}E(Y^2)&=E\left(\left(\sum_{i} X_i\right) ^ 2\right)\\&=E\left(\sum_{i\neq j}(X_i\times X_j)+\sum_{i}X_i^2\right)\\&=\sum_{i\neq j}E(X_i\times X_j)+\sum_{i}E(X_i^2)\end{align}

由于 X_i 的值只能是 1 0 ,所以 X_i^2=X_i ,其中 E(X_i) 我们已经在上一问中求出来了,值为 {1\over i}\times 1

于是只要考虑 E(X_i\times X_j) 的值就好了

实际上 X_i,X_j 独立变量,因为 X_i 的取值 不会 影响到 X_j 的取值,那么就有

\begin{align}E(X_i\times X_j)&=E(X_i)\times E(X_j)\\&={1\over ij}\end{align}

  1. 对于长度为 n 的任意的排列 p ,求 i j 后面的概率

每个数是平等的,于是答案为 1\over 2

  1. 随机⼀个⻓度为 n 的排列 p ,求它包含 w[1\cdots m] 作为⼦序列/连续⼦序列的概率

子序列:

考虑排列组合

p 共有 n! 种排列,考虑其中合法的数量

相当于 n 个中选 m 个,然后剩下的全排列 (n-m)! ,总的可行数就是 C_n^m\times (n-m)!

于是概率就为

C_n^m\times (n-m)!\over n!

连续子序列(子区间):

对于前 n 个, 存在子区间的概率为:

(n-m)!\over n!

共有 n-m+1 种可能的放法, 故答案为

(n-m+1)!\over n!

  1. n 堆⽯头,第 i 堆个数为 a[i] ,每次随机选⼀个⽯头然后把那⼀整堆都扔了,求第 1 堆⽯头期望第⼏次被扔

1 + \sum _ { i = 2 } ^ { n } P ( A_i < A_1 )

其中 P(A_i < A_1) = {A_i \over A_i + A_1}


咕咕咕 未完待续

坚持原创技术分享,您的支持将鼓励我继续创作!