概率论

前言

近几天在刷题的时候遇到了好多道概率相关题目，为了复习一下概率相关知识，也是为了HDYZ未来的oier们能够在未来遇到概率相关问题时有一份百科全书式的参考文献和难易梯度设置较为合理的题单...因而，写下本篇概率论相关Wiki。

本篇Wiki将分为两个部分 $Section 1 相关概念$ 和 $Section 2 练习题单$ 。

需要注意的是，我将题单全部放在了最后面，如果想要每学到一个部分就做两道题的话，可以在阅读完相关内容后直接滑动至题单部分练练手喵！

在公式的推导和题目的解答方面，我尽量写的不是那么需要注意力。当然因为本人专业程度确实有限，如果本篇Wiki上存在一些专业上的问题，也希望大家能够积极联系我，大家一起来完善本篇Wiki，造福后人喵！

概率论理论内容

这一部分中有大量的Latex公式内容，他们也恰是本篇Wiki的灵魂所在，如果有公式没有渲染出来，麻烦大家手动刷新一下页面~ $￣︶￣*$)

引入：

首先我们考虑这样一个问题：Rhine 在玩一个抛硬币的游戏

那么在正常情况下，他抛到正面和反面的次数应该是几乎相等的。虽然抛 $n$ 次硬币可能有较大的相对误差，但随着抛硬币的次数不断增加，正反面次数的相对误差会逐渐减小。

形式化的：

\[ \frac{cnt_{结果为正面}}{cnt_{总投掷次数}} \to \frac{1}{2} \]

那么我们定义，当发生的事件总数趋于正无穷时，发生事件 A 的次数除以发生的事件总数总会趋于一个定值，称为事件 A 发生的概率，我们记为 $P(A)$ 。

在上面的例子中，事件一共有两种：即抛到正面和抛到反面。所以存在：

\[ P(正面) = P(反面) = \frac{1}{2} \]

在这里，函数 $P$ 一般称为概率函数。

从以上例子出发，我们再来规定以下数学符号(在之后的介绍中，我们都会利用以下的数学语言进行标记)：

样本空间：$\Omega$ 指明随机现象所有可能出现的结果。在本例中，即为 Rhine 在 $n$ 次投掷中所有可能投掷出的结果。值得注意的是：OI 中一般只关注离散概率空间，即 $\Omega$ 中的元素个数有限。

事件：$\omega $ 指明我们所探讨的事件，也就是 $\Omega$ 中的元素。在本例中，即为Rhine在第 $n$ 次投掷中投掷出了正面$/$反面

随机变量

我们再来引入一个重要概念 - 随机变量

随机变量是一种函数，它的函数参数是我们样本空间中的某个事件

比如我们在这里再让 Rhine 进行一个投骰子的游戏...

那么我们令 $X(\omega)$ 表示状态 $\omega$ 的点数

则有： $X(点数为1) = 1$ ， $X(点数为3) = 3$ 。

我们还可以计算出随机变量(函数的函数值)等于某个值的概率，比如在如上例子中，则存在 $P( X=1 )= \frac{1}{6}$。_{(超级美观对不对！！！)}

需要声明的是：随机变量还可以进行加减乘除等初级运算

我们再扩展一下 Rhine 投骰子的例子。

现在 Rhine 又得到了一个灌了铅的骰子（没有丢掉原来的正常骰子啊），优越性在于其投出点数 $1$ 和点数 $6$ 的概率是投出其他结果的两倍。

那么我们按照上方的标记方法，令 $P_1$ 表示之前就有的正常骰子的概率函数，$P_2$ 表示新得到的灌铅骰子的概率函数。

那么现在我们让 Rhine 把正常骰子和灌铅骰子各投掷一遍，令 $P_{3}(\omega_1 \omega_2)$ 表示：正常骰子投出的结果为 $\omega_1$ 而灌铅骰子投出的结果为 $\omega_2$ 。

那么显然的，我们可以发现对于所有的 $P_{3}(\omega_1 \omega_2)$ 都存在

\[ P_{3}(\omega_1 \omega_2) = P_{1}(\omega_1) \cdot P_{2}(\omega_2) \]

然而...这一结论真的对于所有的随机变量情况都成立吗？

我们给出以下例子：

现在 Rhine 换回了两个正常骰子_{(作弊被抓包了)}

我们现在规定事件 $X$ 表示投出的两个骰子的点数之和，规定事件 $Y$ 表示投出的两个骰子的点数之积，则存在

\[ P(X=2) = \frac{1}{36} \\ P(Y=1) = \frac{1}{36} \\ (投出两个骰子的结果均为 1 )\\ \]

但是！我们却能够发现

\[ P(X=2 ， Y=1) = \frac{1}{36}\\ 或而言之： P(X=2 ， Y=1) \ne \frac{1}{36} \cdot\frac{1}{36} \]

也就是说 $P_{3}(\omega_1 \omega_2) = P_{1}(\omega_1) \cdot P_{2}(\omega_2)$ 这一公式并不是总能够成立。

我们认为，这个公式成立当且仅当随机变量 $X$ 和 $Y$ 是独立的。

所以我们给出随机变量独立的概念。

随机变量 X 和 Y 独立，意味着 Y 的取值不对 X 的取值产生影响。

比如说两次抛骰子的点数之间就没有影响，但抛两个骰子时，点数的和与点数的积之间就存在着一定的关联。

更为形式化的：

我们认为随机变量 $X$ 和 $Y$ 独立，当且仅当对于任意值 $x, y$ , 都有

\[ P(X=x 且Y=y) = P(X=x) \cdot P(Y=y)\\ 这与两个随机变量独立互为充要条件，形式化的:\\ P(X=x 且Y=y) = P(X=x) \cdot P(Y=y) \Leftrightarrow 事件X和Y独立 \]

我们稍作改动，即为课本上的：

\[ P(AB) = P(A)\cdot P(B) \Leftrightarrow 事件A和B独立 \]

也就是说，两个独立的事件都发生的概率是它们各自发生的概率的积。

那么...不独立的事件该怎么办呢？

我们引入新的记号，记 $P(A\mid B )$ 表示在 $B$ 发生的条件下 $A$ 发生的概率。

那么很快啊，我们就能发现

\[ P(AB) = P(A\mid B ) \cdot P(B) \]

当 $A$ 和 $B$ 两个事件相互独立时， $P(A\mid B ) = P(A)$

这样，上面的所有式子都可以互相推出了！

贝叶斯公式

~~哎，Rhine_River,你咋说了半天都是必修二课内知识啊...~~

经过上面的证明，我们可知

\[ P(AB) = P(A\mid B ) \cdot P(B)\\ P(AB) = P(B\mid A) \cdot P(A) \]

那么我们可以得到

\[ P(A\mid B) = \frac{P(B\mid A)\cdot P(A)}{P(B)} \]

这个是极为巧妙的！因为他给了我们一个由 $P(B\mid A)$ 和 $P(A)$ 而推出 $P(A\mid B)$ 的工具。

在现实生活中，当我们遇见了一个预先发生的事件 $A$ ,其本身的发生概率和 $B$ 无关啊，我们称 $P(A)$ 为 $A$ 的先验概率。而 $B$ 却是基于 $A$ 发生的事件其发生概率完全依赖于$A$ 是否发生。

而贝叶斯公式提供了一种通过 $B$ 的结果计算 $P(A\mid B)$ 的方式，其中 $P(A\mid B)$ 被称为 $A$ 的后验概率。它的实际应用是，通过一些已知的“线索”，计算原始事件发生的概率。

什么，你还没get到这一公式的巧妙之处？以下！

Rhine现分别有 $2$ 个HZOI的题单和 $3$ HYOI的题单，在每个HZOI的题单里分别有 $7$ 个紫题和 $3$ 个蓝题，在每个HYOI的题单里有 $1$ 个紫题和 $9$ 个蓝题。现已知闭着眼从 5 个题单中，点击开了一个题单，在里面抽出了一道题...糟糕，是紫题啊_{(根本不会做呜呜呜)}。问这个紫题来自HYOI题单的概率是多少?

思考一下喵~

题解

期望

对于一个随机变量 $X$ 我们可以求解出其期望

利用期望我们可以计算样本通常收敛在什么值的范围

实质上就是其每个事件的概率乘上其价值之和。

形式化的：

\[ E X =\sum_{\omega\in \Omega }^{} X(\omega)\times P(\omega) \]

而这个函数还有一些特别的性质，比如它是一个线性函数..._{（那就很好玩了捏）}

这里不过多赘述，直接给出形式化内容：

\[ E (X+Y)=\sum_{\omega\in \Omega }^{} (X(\omega)+Y(\omega))\times P(\omega)=EX+EY \]

注意：期望的线性性质是不需要保证随机变量相互独立的。

呐呐呐...随机变量相互独立的时候有没有什么特殊性质呢？

当然有：

\[ E (XY)= E(X)\times E(Y) \]

也就是说，两个独立事件同时发生的期望即为这两个事件分别发生的期望的和。

在简要的证明之前，我还是想要给出一个例子

Rhine 现在有一个骰子和一个正面写着 $1$ 背面写着 $2$ 的硬币。现在他想要得出同时投出两者的期望。

这里这两者互为独立事件，那么我们则可以计算出

\[ E(XY) = E(X)\times E(Y) = 3.5+1.5 = 4 \]

好了，下面是简要证明：_{（不要觉得自己看不懂形式化就不去理解，下方的形式化已经打好了注释，相信你没问题哒！）}

\[ E (XY)\\ = \sum_{\omega \in \Omega}^{} X(\omega)Y(\omega)\cdot P(\omega)(期望函数的线性性质)\\ =\sum_{x,y}^{}xy\cdot P(X=x \wedge X=y) (仔细想一下为什么)\\ =\sum_{x,y}^{}xy\cdot P(X=x )\times P(X=y)(基于事件独立的拆分)\\ =\sum_{x}^{}x\cdot P(X=x)\times \sum_{y}^{}y\cdot P(X=y)(乘法交换律)\\ = E(X)\times E(Y) \]

方差

对于一个随机变量 $X$ 我们还可以求出其方差

和统计学的方差近似的是，方差可以用来衡量一个随机变量值的均匀程度，变量值分布越均匀则方差越小。

实质上就是随机变量 $X$ 与其期望 $E(X)$ 之间差的平方的期望。

形式化的：

\[ V(X) = E(X-E(X)^2) \\ 或者更为简明的：\\ V(X) ={\sum_{\omega\in\Omega} (x_i-E(X))^2} \cdot p_i \]

实际上就是对于概率空间 $\Omega$ 中的每一个事件 $\omega$ 计算其权值 $x_i$ 与全概率空间 $\Omega$ 的期望 $E(X)$的差的平方再乘上其概率。

还没理解吗？_{(别害怕，这个确实很难理解的说ヾ(•ω•`))}那数列中计算方差你肯定是会的，对吧！我们来看对于一个数列的方差，我们以如下方式计算：

\[ 对于一个序列\left \{ a_1,a_2,a_3\dots a_n \right \} \\ 我们计算其方差：V(A) = \frac{\sum_{i=1}^{n}(a_i - \overline{a} )^2}{n} \\ 那么，现在我们把数列中的每个元素更换为概率空间中每个事件的权值，\\平均数更换为其期望，\\ 最后除以 n 取平均数改为对每个平方差乘以其概率(其实就是再求了一边期望) \]

不可否认的是上述对于方差的解释是极为不严谨的，但是~如果能帮助到您理解方差这一概念...或许其存在也是可以接受的了。

当然，方差还有更为简单的计算方式：

\[ V(X) = E(X^{2}) - E^{2}(X)即：**平方的期望减去期望的平方** \]

对于其证明...为了让大家都能看得懂，我们从方差的定义出发，通过几次代数变换来推导出本公式。_{（我尽量写的大家都能看懂哈）}也希望大家可以从如下推导过程中领悟到一些方差和期望的基本运算。

首先的，我们从方差的定义出发，在上面我们将方差 $V(X)$ 定义为随机变量 $X$ 与其期望 $E(X)$ 之间差异的平方的期望，即：

\[ V(X) = E(X-E(X)^2) \]

这里，我们再利用完全平方公式进行拆分

\[ V(X) = E[X^2-2XE(X)+E(X)^2] \]

利用上文我们提到过的期望的线性性质再进行一步化简

\[ V(X) = E(X^2)-E[2XE(X)]+E[E(X)^2] \]

那么我们再引入一个关于期望的定义 $E(C)= C(C为一常数)$ 这个是极易理解的，毕竟常数的期望肯定是自己嘛...就好像对一个数求平均数，那肯定也是自己啊。

那么我们又能发现，对于一个事件，其期望一定为一个常数_{（同一个事情，那它的期望肯定不会有变化啊）}。那么我们就能够得出 $E[E(x)]=E(X)$ ，利用这个定理，我们分别来拆分第二个式子 $E[2XE(X)]$ 和第三个式子 $E[E(X)^2]$

\[ ②：E[2XE(X)] = 2E[X\cdot E(x)] = 2E(X)\cdot E[E(X)](线性变换)\\ 我们再根据上文提到的定理把E(X)作为常数提出来\\ E[2XE(X)] = 2E(X)\cdot E(X) = 2E(X)^2\\ 好，我们乘胜追击，再拿下第三个式子\\ ③：E[E(X)^2] = E(X)^2 \]

那么我们把第二个式子和第三个式子做合并操作，即可得到：

\[ V(X) =E(X^2) - 2E(X)^2 +E(X)^2 = E(X^{2}) - E^{2}(X) \]

以上，得证。

概率论相关题目

以下每道题都只会放一些简要题解，如果没有看懂的话...点击超链接可以看一下详细题解，如果还是没有看懂的话，可以联系我喵~

但还是建议大家点击 点我看详解 之前好好想一想喵，看自己能不能写出来再去看详解...

概率

T1 扔硬币

_{~这道题会不会有点太水了...}_{~不过没关系我们可以慢慢来嘛}

一道很简单的概率DP类题目我们可以利用 $F[i][j]$ 来表示：投出了 $i$ 个硬币后，有 $j$ 个为正面朝上的概率。随之而至的我们便可以将其拆分集合(这次投出了正面/反面)得到动态转移方程。

没看懂？点我看详解

T2概率与组合数学相谈

实际上我们观察可以发现，其帕琪七重奏的触发条件是一个序列，例如：$\left\{1，2，3，4，5，6，7 \right\}$ 或者 $\left\{3，5，2，1，4，6，7 \right\}$ 对吧~

那我们先利用组合数学只是求出出现一个序列的概率，之后乘上序列的数量（一个由$7$ 个数组成的序列当然有 $7! = 5040$ 个喵），之后我们直接再乘上会有多少个 $7$ 个数组成的序列即可求出概率。

没看懂？点我看解析

T3 P5249 LnOI2019 加特林轮盘赌

又是一道概率DP类题目我们可以利用 $F[i][j]$ 来表示：共有 $i$ 个人，标号为 $j$ 的人生还到最后的概率。之后我们再观察一下整体流程可以发现 : 如果当前第一个人没有死掉，那么后面的人都向前走一步即可，如果当前第一个人不幸罹难了...所有人还是向前走了一步，但此时转移来源总人数就要减去 $1$ 了。以此，分情况写出转移方程即可

再加以限制条件，$\sum_{j=1}^{n} F[n][j] = 1$ 与我们刚刚推出的转移方程进行一下消元即可求解。

没看懂？点我看详解

期望

T1 吃寿司

没接触过期望DP的话可能有点不是很能理解题意，但是别怕，这里是题意及样例解释

解释完了样例，我们再回归原题，发现每个盘子上的寿司数量很小(只有 $3$ )，再我们设置状态表示 $F[i][j][k]$ 来表示有 $i$ 盘有 $1$ 个寿司，有 $j$ 盘有 $2$ 个寿司，有 $k$ 盘有 $3$ 个寿司，有 $n-i-j-k$ 盘有 $0$ 个寿司。随之而至的我们便可以将其拆分集合(这次随机到的盘子里有0/½/3个寿司)得到动态转移方程。

没看懂？点我看详解

T2 前缀和

其实...还是一个抛硬币问题:假设有一枚硬币，它抛到正面的概率是 $p$ 。那么，这枚硬币第一次抛到正面时恰好抛了 $t$ 次的概率就是 $p(1 − p)^{t−1}$ ，也就是 $P(x_i = t)$ 。则 $y_i$ 就表示一枚硬币第 i 次抛到正面时所抛的次数。其落在 [l, r] 内的 $y_i$ 数量即为第 $l$ 次到第 $r$ 次抛硬币之间的正面数量，其期望值即为 $p(r − l + 1)$ 。

没看懂？点我看详解

T3 ZS Shuffles Cards

~~偷偷告诉你们，这道题是我从 “HZOI2024 冲刺 NOIP2024 400pts 计划” 上看到的。(定点狙击ing)~~ _{(太恐怖了)}

首先的，别看这道题是黑，但其实和上一道题一个难度哒！设计一个一维DP即可！

需要注意的是：每次抽到鬼牌后，并不会清空集合 $S_i$ ,只会把抽过的牌再加回去。

我们发现每次抽到的牌是否可以产生贡献，只和当前集合内所拥有的牌相关。那么我们设计状态 $f_i$ 表示当前集合内已经有了 $i$ 张牌时期望操作轮数(我们记洗牌一次为一轮)。。随之而至的我们便可以将其拆分集合(这次摸到的牌是鬼牌/没摸到过的牌)得到动态转移方程。以上，暴力跑出每一轮的期望步数即可！

没看懂？点我看详解

后记

就这样了喵，好累...吃饭去了。

感谢观看，如果本篇Wiki存在一些问题，或者大家有什么想要和我说的话，都可以写在下方评论区喵！~~觉得我写的不错的话就在下方评论区夸我两句呗~~

请大家一定...拼命寻找生长的意义！

By Rhine