跳转至

概率与统计

事件

一些定义

随机试验 指的是在相同条件下，对某个随机现象进行大量重复观测。

随机试验满足以下条件：

  • 可以在相同条件下重复进行
  • 出现的所有可能结果不止一个，但事先已知
  • 每次试验总是出现可能结果之一，但试验前无法预知结果

基本事件（样本点） 是随机试验的每一种可能的结果，一般用 \(e\) 来表示。

全体基本事件构成的集合成为样本空间 ，有样本空间 \(S = \{e_1,e_2,\cdot \cdot \cdot \,\,\}\)。

随机事件 \(A\) 是样本空间 \(S\) 的一个子集。当且仅当 \(A\) 中某个基本事件发生，称随机事件 \(A\) 发生。

对立事件 \(\bar{A}\) 是由 \(A\) 不发生所构成的事件。

显然：

  • \(A=S \Leftrightarrow A是必然事件\)
  • \(A=\varnothing \Leftrightarrow A是不可能事件\)

注意：随机试验不保证出现的结果是有限的，样本空间可以包含无穷个基本事件。

事件的运算

  1. \(A \subseteq B\)
  2. \(A = B\)
  3. \(A \cap B \; (AB) \quad \cap_{i = 1}^{n}=A_1 \cap A_2 \cap \cdot \cdot \cdot \cap A_n\)
  4. \(A \cup B \; (A+B) \quad \cup_{i = 1}^{n}=A_1 \cup A_2 \cup \cdot \cdot \cdot \cup A_n\)
  5. \(A-B \Leftrightarrow 随机事件A发生，随机事件B不发生\)

概率模型

古典概型

古典概型中各个基本事件出现概率相等

\[ P(A)=\frac{card(A)}{card(S)} \]

几何概型

几何概型中基本事件有无限个，每个基本事件概率相等

\[ P(A)=\frac{A事件对应的面积}{总面积} \]
Example

估计 \(\pi\) 的值

对于边长为2正方形，其内接圆的半径为1

加载失败了喔

在这个正方形内均匀地随机撒点，点距离中心的距离不超过 \(1\) 的概率为 \(\frac{\pi}{4}\)

则

\[ \pi \approx \frac{与中心距离不超过1的点的个数}{总点数} \cdot 4 \]

条件概率与贝叶斯公式

条件概率指的是“\(B\) 事件发生的情况下，\(A\) 事件发生的概率” 记为 \(P(A|B)\)

可以得到条件概率公式：

\[ P(A|B)=\frac{P(AB)}{P(B)} \]

推出贝叶斯公式:

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

其中：

  • \(P(A|B)\) 是后验概率。后验概率是在观察到数据或证据之后，对事件发生概率的更新信念。它结合了先验概率和新观察到的数据，提供了更准确的事件发生概率。
  • \(P(B|A)\) 是似然度。似然度是在给定参数或假设下，观察到数据的概率。它衡量了在特定假设下，数据出现的可能性。
  • \(P(A)\) 是先验概率。在观察到任何数据之前，对事件发生概率的初始信念或判断。它反映了我们对事件发生概率的先验知识或假设。
  • \(P(B)\) 是边缘概率。名称源于其在概率分布表格中的位置。

数学期望

数学期望简称期望，是试验中每次可能的结果乘以其结果概率的总和。形式化地，期望值是随机变量输出值的加权平均数，权重即为各个事件对应的概率。

掷一枚骰子，用随机变量 \(X\) 表示朝上的面的点数，则

\[ E(x) = 1 \times \frac{1}{6} + 2 \times \frac{1}{6} + 3 \times \frac{1}{6} + 4 \times \frac{1}{6} + 5 \times \frac{1}{6} + 6 \times \frac{1}{6} = 3.5 \]

期望具有线性性质，即 \(E(aX+bY) = aE(X)+bE(Y)\)。

概率分布

概率分布表述随机变量取值的概率规律。

伯努利试验是一个只有两个可能结果（成功和失败）的随机实验。

以下设实验成功的概率是 \(p\)

两点分布

又称伯努利分布、两点分布

明显其期望值:

\[E(x) = p \times 1 + (1-p) \times 0 = p\]

几何分布

在伯努利试验中，得到一次成功所需的试验次数是 \(X\)。在 \(k\) 次试验中，第 \(k\) 次才能成功的概率是

\[P(X = k) = p(1 - p) ^ {k - 1}\\\]
\[那么\quad E(X) = {\sum_{k = 1}^{\infty}}kp(1-p)^{k-1} = \frac{1}{p}\]

二项分布

是用于描述“进行 \(n\) 次伯努利试验，成功的次数”的模型。

其中

\[P(X = k) = C_{n}^{k}p^k(1-p)^{n-k}\]
\[E(X) = np\]

其证明过程较为复杂

一般地，可以证明：

如果 \(X \sim B(n, p)\)，那么 \(E(X) = np\)， \(D(X) = np(1-p)\)。

下面我们对均值进行证明。

令 \(q = 1 - p\)，由 \(kC_n^k = nC_{n-1}^{k-1}\)，可得

\[E(X) = \sum_{k=0}^{n} kC_n^k p^k q^{n-k} = \sum_{k=1}^{n} nC_{n-1}^{k-1} p^k q^{n-k} = np \sum_{k=1}^{n} C_{n-1}^{k-1} p^{k-1} q^{n-1-(k-1)}.\]

令 \(k - 1 = m\)，则

\[E(X) = np \sum_{m=0}^{n-1} C_{n-1}^m p^m q^{n-1-m} = np (p + q)^{n-1} = np.\]

超几何分布

用于描述“抽样不放回”的模型。

设随机变量 \(X\) 服从超几何分布，则 \(X\) 可以解释为从包含 \(M\) 件次品的 \(N\) 件产品中，不放回地随机抽取 \(n\) 件产品中的次品数。令 \(p = \frac{M}{N}\)，则 \(p\) 是 \(N\) 件产品的次品率，而 \(\frac{X}{n}\) 是抽取的 \(n\) 件产品的次品率，我们猜想 \(E\left(\frac{X}{n}\right) = p\)，即 \(E(X) = np\)。

实际上，令 \(m = \max\{0, n - N + M\}\)， \(r = \min\{n, M\}\)，由随机变量均值的定义：

当 \(m > 0\) 时，

\[E(X) = \sum_{k=m}^{r} k \frac{C_M^k C_{N-M}^{n-k}}{C_N^n} = M \sum_{k=m}^{r} \frac{C_{M-1}^{k-1} C_{N-M}^{n-k}}{C_N^n} \tag{1}\]

因为 \(\sum_{k=m}^{r} C_{M-1}^{k-1} C_{N-M}^{n-k} = C_{N-1}^{n-1}\)，所以

\[E(X) = \frac{M}{C_N^n} \sum_{k=m}^{r} C_{M-1}^{k-1} C_{N-M}^{n-k} = \frac{M C_{N-1}^{n-1}}{C_N^n} = \frac{nM}{N} = np\]

当 \(m = 0\) 时，注意到 \((1)\) 式中间求和的第一项为 \(0\)，类似可以证明结论依然成立。

一些定理

  1. 对于随机正整数 \(x\)，有：
\[ E(x) = \sum_{i = 1}^{+\infty} P(x \geq i) \]

例题

P1654 OSU!

osu 是一款群众喜闻乐见的休闲软件。

我们可以把 osu 的规则简化与改编成以下的样子:

一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\)，失败对应 \(0\)， \(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(x\) 个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\)，具体见样例解释）

现在给出 \(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。

\(n \leq 1 \times 10 ^ 5\)

有连续 \(x\) 个 \(1\)，多出一个 \(1\)，贡献由 \(x^3\) 变为 \((x+1)^3\)。

贡献增加 \(3x^2+3x+1\)。

维护 \(Ex_i\) 表示 \(x\) 的期望值（典型两点分布）

\[ Ex_i = p_i(Ex_{i-1}+1) \]

维护 \(Ex2_i\) 表示 \(x^2\) 的期望值

\[ Ex2_i = p_i(Ex2_{i−1}+2 \times Ex1_{i−1}+1) \]

维护 \(f_i\) 表示答案

\[ f_i = f_{i−1}+p_i(3 \times Ex2_{i−1}+3 \times Ex_{i−1}+1) \]
实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n;
double p[N], Ex[N], Ex2[N], f[N];
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    for (int i = 1; i <= n; i++)
    {
        Ex[i] = p[i] * (Ex[i - 1] + 1);
        Ex2[i] = p[i] * (Ex2[i - 1] + 2 * Ex[i - 1] + 1);
        f[i] = f[i - 1] + p[i] * (3 * (Ex[i - 1] + Ex2[i - 1]) + 1);
    }
    cout << fixed << setprecision(1) << f[n];
    return 0;
}
P4316 绿豆蛙的归宿

给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 \(k\) 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

  • 对于 \(20\%\) 的数据，保证 \(n \leq 10^2\)。
  • 对于 \(40\%\) 的数据，保证 \(n \leq 10^3\)。
  • 对于 \(60\%\) 的数据，保证 \(n \leq 10^4\)。
  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)， \(1 \leq m \leq 2 \times n\)， \(1 \leq u, v \leq n\)， \(0 \leq w \leq 10^9\)，给出的图无重边和自环。
实现 
 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e5 + 10, MAXM = 2e5 + 10;
int n, m, head[MAXN], oud[MAXN];
double f[MAXN];
struct edge
{
    int v, w, nxt;
} e[MAXM];
inline void addedge(int u, int v, int w)
{
    static int edge_cnt = 0;
    e[++edge_cnt] = {v, w, head[u]};
    head[u] = edge_cnt;
    oud[u]++;
}
double dfs(int u)
{
    if (f[u] != -1)
        return f[u];
    f[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v, w = e[i].w;
        f[u] += dfs(v) + w;
    }
    return f[u] /= oud[u];
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w, addedge(u, v, w);
    fill(f + 1, f + 1 + n, -1);
    f[n] = 0;
    cout << fixed << setprecision(2) << dfs(1);
    return 0;
}
P1850 [NOIP 2016 提高组] 换教室

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 \(2n\) 节课程安排在 \(n\) 个时间段上。在第 \(i\)（ \(1 \leq i \leq n\)）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 \(c_i\) 上课，而另一节课程在教室 \(d_i\) 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 \(n\) 节安排好的课程。如果学生想更换第 \(i\) 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 \(i\) 个时间段去教室 \(d_i\) 上课，否则仍然在教室 \(c_i\) 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 \(i\) 节课程的教室时，申请被通过的概率是一个已知的实数 \(k_i\)，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 \(m\) 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 \(m\) 门课程，也可以不用完这 \(m\) 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 \(v\) 个教室，有 \(e\) 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第 \(i\)（ \(1 \leq i \leq n-1\)）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

实现 
 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
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
const double inf = 0x3f3f3f3f;
struct node
{
    int v, w;
};
int c[N], d[N];
double p[N], f[N][N][2];
int mp[N][N];
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m, num, e;
    cin >> n >> m >> num >> e;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    for (int i = 1; i <= num; i++)
        for (int j = 1; j < i; j++)
            mp[i][j] = mp[j][i] = inf;
    for (int i = 1; i <= e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = mp[v][u] = min(mp[u][v], w);
    }
    for (int k = 1; k <= num; k++)
        for (int i = 1; i <= num; i++)
            for (int j = 1; j <= num; j++)
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            f[i][j][0] = f[i][j][1] = inf;
    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; i++)
    {
        f[i][0][0] = f[i - 1][0][0] + mp[c[i - 1]][c[i]];
        for (int j = 1; j <= min(m, i); j++)
        {
            f[i][j][0] = min(f[i - 1][j][0] + mp[c[i - 1]][c[i]],
                             f[i - 1][j][1] + mp[c[i - 1]][c[i]] * (1 - p[i - 1]) + mp[d[i - 1]][c[i]] * p[i - 1]);
            f[i][j][1] = min(f[i - 1][j - 1][0] + mp[c[i - 1]][c[i]] * (1 - p[i]) + mp[c[i - 1]][d[i]] * p[i],
                             f[i - 1][j - 1][1] + mp[d[i - 1]][d[i]] * p[i] * p[i - 1] + mp[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + mp[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + mp[c[i - 1]][c[i]] * (1 - p[i - 1]) * (1 - p[i]));
        }
    }
    double ans = inf;
    for (int i = 0; i <= m; i++)
        ans = min(ans, min(f[n][i][0], f[n][i][1]));
    cout << fixed << setprecision(2) << ans;
    return 0;
}