概率论
理论内容
前言
当发生的事件总数趋于正无穷时，发生事件 \(A\) 的次数除以发生的事件总数会趋于一个定值，称为事件 \(A\) 发生的概率 \(P(A)\)。
概率是数据的固有属性。
概率
把所有事件的集合称为概率空间 \(\Omega\)，其中的元素（即事件）为 \(\omega\)。
随机变量是一种函数，其参数是概率空间中的某个事件。
随机变量可以进行加减乘运算。
我们认为随机变量 \(X\) 和 \(Y\) 独立，当且仅当对于任意值 \(x,y\)，都有 \(P(X=x\) 且 \(Y=y)=P(X=x)· P(Y=y)\)。
\(P(AB)=P(A)·P(B)\Leftrightarrow A\) 与 \(B\) 独立。
\(P(A|B)\) 表示在 \(B\) 发生的条件下 \(A\) 发生的概率，则有 \(P(AB)=P(A|B)·P(B)\)。
贝叶斯公式
\(P(A|B)=\dfrac{P(B|A)P(A)}{P(B)}\)
\(P(A|B)\) 称为 \(A\) 的后验概率，可以用于计算原始事件发生的概率。
题目中，我们令 \(A\) 表示要求的概率的事件（即所求概率要发生的事件），\(B\) 为已知的事件（即已发生的事件），然后套用贝叶斯公式。例：
注意，\(A\) 的发生不依赖于 \(B\) 而 \(P(A|B) \not= P(A)\) 的原因是在此种情况下，\(A\) 已经坍缩完毕（已经发生），真实的 \(P(A)\) 要不是 \(0\) 要么是 \(1\)。\(B\) 是 \(A\) 坍缩产生的一些信息，假如 \(B\) 是仅有的信息，则把 \(A|B\) 可以视为 \(A\) 的不完全坍缩（该事件还未完全发生），概率自然会发生变化。
期望与方差
- 期望
对于随机变量 \(X\)，它的期望 \(E X=\sum\limits_{\omega\in\Omega}X(\omega)P(\omega)\)。
相关公式：
- 方差
随机变量 \(X\) 的方差 \(V X=E((X-E X)^2)\)，可以用来衡量一个随机变量值的均匀程度，变量值分布越均匀方差越小。
此外，\(V X=E(X^2)-(E X)^2\)。
例题
基础模型
- P9963 [THUPC 2024 初赛] 前缀和
- Problem 1
求抛出硬币连续 \(n\) 次正面期望的抛出的次数。
用 \(f(x)\) 表示已经连续抛出了 \(x\) 个 \(1\)，期望再抛几次可以完成要求，则有 \(f(x)=\dfrac{f(x+1)+f(0)}{2}+1\)。
考虑，递推时用 \(f(0)\) 表示结果，解方程即可。
概率 dp 和期望 dp 经常会出现转移关系成环的情况，无法直接转移，朴素做法是暴力高斯消元。
但上题属于特殊情况，这种方法称为主元法。
- Problem 2
求将 \(n\) 个面骰子每个点数都掷出一次的期望。
\(f(i)\) 表示掷出 \(i\) 种点数的期望步数，则答案为 \(f(n)\)。
掷出 \(i\) 种点数后，每次掷骰子掷出新点数的概率都是 \(\dfrac{n-i}{n}\)，所以期望再掷 \(\dfrac{n}{n-i}\) 才能掷出第 \(i+1\) 种点数。
则有转移式 \(f(i+1)=f(i)+\dfrac{n}{n-i}\)，所以有 \(f(n)=nH_n\)，其中 \(H_n=\sum\limits_{i=1}^n\dfrac{1}{i}\)，\(H_n\) 为调和数。
- P3802 小魔女帕琪
每个长度为 \(7\) 的连续段元素互不相同的概率是一样的，直接计算前 \(7\) 个元素互不相同的概率，再乘上连续段个数即可。
因为不要求顺序，所以前 \(7\) 个元素互不相同的概率为 \(\dfrac{7!\prod\limits_{i=1}^7a_i}{n^\underline{7}}\)
- [AGC049A] Erasing Vertices
