基础概念

• 样本点：随机试验中可能发生的结果
• 样本空间：所有样本点的集合，记作 $\Omega$
• 概率：记作 $P(A)$ ，即事件 $A$ 发生的概率，满足 $P(A) \in \R 且 0\leq P(A) \leq 1$

概率模型

古典模型

即各个事件出现的概率相等。此时 $P(A) = \frac{A 包含的基本事件总数}{基本事件总数}$ 。典型的例子包括抛硬币、掷骰子等。

例：一年有 365 天，每个人出生日期都是随机的。班里有 30 名同学，则存在两位同学生日相同的概率是多少？

解： 每个人的生日有 365 种可能性，基本事件总数即为 $365^{30}$ 。等概率随机即满足古典概型。显然直接计算概率需要考虑只有两个同学生日相同、只有三个同学生日相同等情况，计算复杂。考虑转化。

我们不妨计算上述命题的逆命题，即不存在两位同学生日相同的概率有多少。此时每位同学的生日都互不相同，所有可能的情况即为 $A^{30}_{365}$ 种。则该逆命题的概率为 $P(不存在两位同学生日相同) = \frac{A^{30}_{365}}{365^{30}}$ 。

则原问题的答案为 $P(存在两位同学生日相同) = 1 - \frac{A^{30}_{365}}{365^{30}}$ 。

几何概型

如果每个事件发生的概率只与构成该事件区域的长度（面积或体积或度数）成比例，则称这样的概率模型为几何概率模型，简称为几何概型。^1

简单来说，在几何概型下，随机试验的所有可能结果（即基本事件总数）为 $\infty$ 且每个事件发生的概率均等。典型的例子包括在一个几何区域内随机取一点进行实验、一个人到单位的时间（在 8:00 ~ 9:00 之间的任意时刻）等。

例：0 时刻时甲乙两人开始等车，甲的车在前 60 min 内随机时刻会到，乙的车在前 120 min 内随机时刻会到。求甲比乙早上车的概率。

解： 设甲的车在 $X$ 时刻会到，乙的车在 $Y$ 时刻会到。则满足 $0 \leq X \leq 60$ ，$0 \leq Y \leq 120$ 。

显然我们要计算的是 $X < Y$ 的概率。不妨用坐标系来表示 $X,Y$ ：

那么，我们要求的 $X < Y$ 可以分为两部分： $0 \leq Y \leq 60$ 时和 $60 < Y \leq 120$ 时。显然第二个区间永远满足 $X < Y$ 。

对于 $0 \leq Y \leq 60$ 时，显然我们可以将图像化为两个三角形。对于上半部分的三角形，永远满足 $X < Y$ 。

综上， $X < Y$ 在坐标轴图像上表现为图中的阴影区域。让我们来计算一下其发生的概率：

$$P(甲比乙早上车) = P(X < Y) = \frac{60 \times 60 + \frac{1}{2} \times 60 \times 60}{60 \times 120} = \frac{3}{4} = 75\%$$

即有 75% 的概率甲比乙早上车。

条件概率

即事件 $A$ 在事件 $B$ 发生的条件下发生的概率，记作 $P(A|B)$ 。要计算条件概率，我们需要引入两个概念：

• 联合概率 表示两个事件共同发生的概率，记作 $P(A \cap B)$ 或 $P(A,B)$ 或 $P(AB)$ ；
• 边缘概率 表示某个事件发生的概率，记作 $P(A)$ 。

条件概率 $P(A|B) = \frac{P(A \cap B)}{P(B)}$ 。特别地，若 $A$ 、$B$ 为两个独立事件，则 $P(A \cap B) = P(A) \times P(B)$ ，则 $P(A | B) = P(A)$ ， $P(B|A) = P(B)$ 。

例 1 ：一对夫妻生了两个孩子，第一个孩子是女孩，求第二个孩子是女孩的概率。

解 1 ： 显然这两个事件是独立事件，故 $P(第二个孩子是女孩)= \frac{1}{2}$ 。

例 2 ：一对夫妻生了两个孩子，其中一个孩子是女孩，求另一个孩子也是女孩的概率。

解 2 ： 存在四个基本事件：（男，男）、（男，女）、（女，男）、（女，女）。

则 $P(一个孩子是女孩|另一个孩子也是女孩) = \frac{P(一个孩子是女孩 \cap 另一个孩子也是女孩)}{P(另一个孩子是女孩)} = \frac{\frac{1}{4}}{\frac{3}{4}} = \frac{1}{3}$ 。

贝叶斯公式

$$P(A|B) = \frac{P(A \cap B)}{P(B)} = \frac{P(B | A) \times P(A)}{P(B)}$$

推导证明显然。

例：某种疾病发病率为 $0.01\%$ ，通过某种检测方式可以检测该疾病。若某人患病，则检测结果为阳性的概率为 $99\%$ ；若没有患病，则检测出阳性的概率是 $1\%$ 。求某人检测结果为阳性时患病的概率。

解： 根据题意，易得

$$P(患病|检测阳性) = \frac{P(患病 \cap 检测阳性)}{P(检测阳性)}$$

即

$$P(患病|检测阳性) = \frac{P(检测阳性|患病) \times P(患病)}{P(检测阳性)} = \frac{0.99 \times 0.0001}{0.99 \times 0.0001 + 0.9999 \times 0.01} \approx 0.98\%$$

应用

看电影

在一个电影院举办针对儿童的六一儿童节免费观影活动，有两个影院放映不同的电影，观影儿童通过投掷硬币决定进入哪一个电影院，投到正面的进入 A 影院，反面的进入 B 影院。 两个影院都能容纳 $n$（$0 \leq n \leq 1000$）个人,预计有 $2n$ 个儿童观影。如果一个影院人满了，则接下来的儿童直接进入另一个影院无需投掷硬币。

求排在队尾的两个儿童同时进入同一个影院的概率。

解法一

考虑通过组合数学求解。

显然直接计算进入同一个影院的概率较为复杂，不妨转化为求解进入不同影院的概率。则一个影院内儿童的所有可能情况有 $C^{n - 1}_{2n - 2}$ 种可能，另一个影院的儿童也随之确定。又因为总事件数为 $2^{2n - 2}$ ，故概率为

$$P(在队尾的两个儿童进入不同影院) = \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}}$$

则所求概率为

$$P(在队尾的两个儿童进入相同影院) = 1 - \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}}$$

又

$$\begin{align} \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}} &= \frac{(2n - 2)!}{(n - 1)! \times (n - 1)!} ÷ 4^{n - 1}\\ &=\frac{(2n - 2)!}{(n - 1)! \times (n - 1)!} \times \frac{1}{4^{n - 1}}\\ &=\frac{2n - 2}{4(n - 1)} \times \frac{2n - 3}{4(n - 2)} \times \cdots \times \frac{n}{4 \times 1} \end{align}$$

故程序如下：

int main() {
    int n;
    cin >> n;
    n >>= 1;  // 输入为2n
    double ans = 1.0;
    for(int i = 1; i < n; i++)
        ans = ans * (i + n - 1) / (i << 2);  // 时间复杂度O(n)
    printf("%.4lf", 1 - ans);
    return 0;
}

解法二

考虑使用动态规划。

定义 $f_{n,m}$ 表示影院 A 剩下 $n$ 个位置，影院 B 剩下 $m$ 个位置时最后两个儿童进入同一个影院的概率。

考虑状态转移。显然 $f_{n,m}$ 由 $f_{n - 1,m}$ 或 $f_{n, m - 1}$ 转移而来，则 $f_{n,m} = \frac{1}{2} \times f_{n - 1, m} + \frac{1}{2} \times f_{n, m - 1}$ 。即当前状态为先前两个状态随机 50% 决定。

显然，对于 $0 < n \leq 1$ 或 $0 < m \leq 1$ ，$f_{n,m} = 0$ 。即当剩余座位 $\leq 1$ 时两个人不能同时进入一个影院。

同理，当 $n = 0$ 或 $m = 0$ 时，两人必须进入同一个影院，即 $f_{n,m} = 1$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;

int n;
double f[N][N];

int main() {
    scanf("%d", &n);
    n /= 2;
    for (int i = 2; i <= n; i++) {
        f[i][0] = f[0][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = 0.5 * (f[i - 1][j] + f[i][j - 1]);
        }
    }
    printf("%.4lf", f[n][n]);
    return 0;
}

Sushi

现有$N(1 ≤ N ≤ 300)$个盘子，编号为$1,2,3,…,N$。第$i$个盘子中放有$a_i(1≤a_i ≤3)$个寿司。

接下来每次执行以下操作，直至吃完所有的寿司。从第$1,2,3,…,N$个盘子中任选一个盘子，吃掉其中的一个寿司。若没有寿司则不吃。

若将所有寿司吃完，请问此时操作次数的数学期望是多少？

考虑概率 DP 。我们设状态 $f_{i,j,k,l}$ 代表剩余 1、2、3、0 个寿司的盘子的数量为 $i,j,k,l$ 时期望的操作数。

注意到 $l = n - i - j -k$ ，故优化为 $f_{i,j,k}$ 。时间复杂度 $O(300^3) = 2.7 \times 10^7 < 10^8$ ，能过。

考虑状态转移。容易发现对于每一个状态都是由上一个状态吃掉某盘中的一个寿司得来的。故易得

$$f_{i,j,k} = f_{i,j,k} \times \frac{n - i - j -k}{n} + f_{i - 1,j,k} \times \frac{i}{n} + f_{i + 1,j - 1,k} \times \frac{j}{n} + f_{i,j - 1,k+1} \times \frac{k}{n} + 1$$

移项通分，得

$$f_{i,j,k} = f_{i-1,j,k} \times \frac{i}{i + j +k} + f_{i + 1,j - 1,k} \times \frac{j}{i + j + k} + f_{i,j + 1,k - 1} \times \frac{k}{i + j + k} + \frac{n}{i + j + k}$$

考虑初始状态。显然当所有盘子的寿司都为空时期望操作数为 $0$ ，即 $f_{0,0,0} = 0$ 。

考虑答案。显然答案为 $f_{b_1,b_2,b_3}$ ，其中 $b_i$ 代表初始状态时有 $i$ 个寿司的盘子数量。

需要注意的是，本题为了满足无后效性需要从 $k$ 到 $i$ 倒序枚举。

#include <bits/stdc++.h>
using namespace std;
const int N = 310;

double f[N][N][N];
double n, a[N];
int b[10];

int main() {
    scanf("%lf", &n);
	for (int i = 1; i <= n; i++) {
        scanf("%lf", &a[i]);
		b[(int)a[i]]++;
	}
    f[0][0][0] = 0;
    for (int k = 0; k <= n; k++) {
        for (int j = 0; j <= n; j++) {
            for (int i = 0; i <= n; i++) {
                if (!(i || j || k)) continue;
                if (i >= 1) f[i][j][k] += f[i - 1][j][k] * (double)i / (double)(i + j + k);
                if (j >= 1) f[i][j][k] += f[i + 1][j - 1][k] * (double)j / (double)(i + j + k);
                if (k >= 1) f[i][j][k] += f[i][j + 1][k - 1] * (double)k / (double)(i + j + k);
                f[i][j][k] += (double)n / (double)(i + j + k);
            }
        }
    }
    printf("%.15lf\n", f[b[1]][b[2]][b[3]]);
	return 0;
}