3.概率论知识—下-灵析社区

英勇黄铜

3.5全概率公式

全概率公式如下，其中 X, Y 为随机变量。

基于【全概率公式】，我们可以通过概率 DP 求 X 的概率。下面我们通过一个例题看一下具体是怎么做的。

例题

以下三件事哪件的概率更大

  • 投掷 6 枚骰子至少一个是 6
  • 投掷 12 枚骰子至少两个是 6
  • 投掷 18 枚骰子至少三个是 6

思路参考: 全概率公式 + 概率DP

假设我们要求投掷 n 枚骰子，至少 m 枚是 6 的概率。

如果 m 是 0，则概率是 1，因为不论最终多少枚是 6，都符合“至少 0 枚是 6”的情况。

如果 m 大于 n，则概率是 0，因为不可能投掷出 6 的个数比骰子的个数还多。

当 0 < m < n 时，我们考虑其中一枚骰子的两种情况：

(1) 该骰子是 6，概率 1/6，则剩下的 n - 1 枚骰子需要至少 m - 1 枚是 6

(2) 该骰子不是 6，概率 5/6，则剩下的 n - 1 枚骰子需要至少 m 枚是 6

综合以上分析，再结合全概率公式

我们可以用概率DP的方式解决，算法如下

状态定义
dp[i][j] := 投掷 i 枚骰子，至少 j 个是 6 的概率

初始化
dp[i][0] = 1.0
dp[i][j] = 0 (j > i)

答案
dp[6][1]
dp[12][2]
dp[18][3]

状态转移
dp[i][j] = 1/6 * dp[i - 1][j - 1] + 5/6 * dp[i - 1][j]

下面编程计算 dp[n][m]

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<double>> dp(n + 1, vector<double>(m + 1, 0.0));
    for(int i = 0; i <= n; ++i)
        dp[i][0] = 1.0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= min(i, m); ++j)
            dp[i][j] = 1 / 6.0 * dp[i - 1][j - 1] + 5 / 6.0 * dp[i - 1][j];
    cout << dp[n][m] << endl;
}

计算结果:

dp[6][1] = 0.665
dp[12][2] = 0.619
dp[18][3] = 0.597。

因此第一个事件的概率更大。

3.6全期望公式

全期望公式如下，其中 X, Y 为随机变量，公式的形式与全概率公式差不多。


公式告诉我们在求 X 的均值（期望）时可转化为求 X 在 Y = yi ( i = 1, 2, ...）条件下的条件期望 E_{X|Y = yi}(X|Y = yi) 再加权求和。

基于【全期望公式】，我们可以通过期望 DP 求 X 的期望。下面我们通过一个例题看一下具体是怎么做的。

例题

8 个男人和 7 个女人订了电影院的一排座，一排刚好有 15 个座位。

问：平均有多少个相邻座位是异性？

思路参考 1: 全期望公式 + 期望 DP

定义 f(x, y) 表示 x 个男，y 个女排一排，相邻座位是异性的平均个数。当 x, y 任意一个为 0 的时候，值为零：f(x, 0) = 0, f(0, y) = 0

当 x > 0, y > 0 时，考虑最左边的座位，它有两种可能性，一种是男的，概率 p1 = x/(x+y), 另一种是女的，概率 p2 = y/(x+y)

(1) 如果最左边是男的:

则期望的相邻座位是异性的个数分为两部分，第一部分是 f(x-1 , y)，第二部分是最左边男人的相邻座位，当相邻位置为女人时，可以贡献 1，概率为 y/(x-1+y)。

(2) 如果最左边是女的:

则期望的相邻座位是异性的个数分为两部分，第一部分是 f(x , y-1)，第二部分是最左边女人的相邻座位，当相邻位置为男人时，可以贡献 1，概率为 x/(y-1+x)。

综合以上若干条，再结合全期望公式

可以写出 f(x, y) 的转移方程。

f(x, y) = p1 * (f(x - 1, y) + y / (x - 1 + y)) 
          + p2 * (f(x, y - 1) + x / (y - 1 + x))

下面通过期望 DP 的方式解决以上问题，算法如下

状态定义

dp[i][j] := i 个男人，j 个女人的情况，相邻座位是异性的个数的期望

初始化
dp[i][0] = 0
dp[0][j] = 0

答案
dp[8][7]

状态转移
dp[i][j] = i / (i + j) * (dp[i - 1][j] + (j / (i - 1 + j)))
           + j / (i + j) * (dp[i][j - 1] + (i / (j - 1 + i)))

下面编程计算 dp[8][7]，代码如下

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 8, m = 7;
    vector<vector<double>> dp(n + 1, vector<double>(m + 1, 0));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            dp[i][j] = (double)i / (i + j) * (dp[i - 1][j] + ((double)j / (i - 1 + j)))
                        + (double)j / (i + j) * (dp[i][j - 1] + ((double)i / (j - 1 + i)));
        }
    cout << dp[n][m] << endl;
}

计算结果为 dp[8][7] = 7.46667

思路参考2: 单独考虑每个相邻座位

一共有 14 个相邻座位。对于每个相邻座位，我们要考虑的都是【从 8 个男人和 7 个女人中选两个人放这个相邻座位的左右两边，这两个人是否为异性】这件事。

假设这个概率为 p，则一个相邻座位可以形成的异性的个数的期望就是 E = p，14 个相邻座位中为异性的期望个数就是 p * 14。

考虑一个相邻作为的左边这个座位：

  • 左边座位是男人的概率为 8/15，在此情况下右边座位是女人的概率为 7/14。
  • 左边座位是女人的概率为 7/15，在此情况下右边座位是男人的概率为 8/14。

因此一个相邻座位能够形成异性的概率为

14 个相邻座位中，异性的个数的期望为 8/15 * 14 = 7.46667。

随机模拟验证结果

import numpy as np
import operator
from multiprocessing import Pool
from functools import reduce

persons = [1] * 8 + [0] * 7

def run():
    l = np.random.permutation(persons)
    ans = 0
    for i in range(len(l) - 1):
        if l[i] != l[i + 1]:
            ans += 1
    return ans

def test(T):
    np.random.seed()
    y = (run() for _ in range(T))
    n = reduce(operator.add, y)
    return n / T

T = int(1e6)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("{:.6f} pairs of adjacent are the opposite sex".format(t))

模拟结果

7.467305 pairs of adjacent are the opposite sex
7.466081 pairs of adjacent are the opposite sex
7.470136 pairs of adjacent are the opposite sex
7.465220 pairs of adjacent are the opposite sex
7.465871 pairs of adjacent are the opposite sex
7.467655 pairs of adjacent are the opposite sex
7.464980 pairs of adjacent are the opposite sex
7.467260 pairs of adjacent are the opposite sex

3.7贝叶斯公式

我们有一个假设 H，可能成立可能不成立，也就是 H 是有一定概率成立的，记为 P(H)。例如我们有三个盒子，名称分别为 a，b，c。现在随机取出一个盒子，我们可以猜测该盒子的名称，如果我们猜 a，这就构成了一个假设：随机抽到的盒子的名称是 a。因为盒子共有 3 个，且盒子是随机取的，我们可以认为 P(H) = 1/3，这个概率称为先验概率。先验概率是根据经验来的，前面的例子的 1/3 就是一个经验值。

现在我们得到了一条证据 e，这个证据一般是某个实验的观察值。还是以三个盒子举例，a, b, c 三个盒子内均有一些球，其中 a 中有 10 个黑球，b 中有 10 个白球，c 中有 5 个黑球 5 个白球。我们可以针对盒子名称做实验：抽出一个球看颜色。假设看到的颜色是白色，我们就得到了一条证据：随机抽出一个球的颜色是白色。根据实际情况，证据 e 可能加强假设 H 成立的可能性，也可能削弱假设 H 成立的可能性。我们想知道的是当我们拿到证据 e 之后，假设 H 成立的概率是多少，这个概率记为 P(H|e)，称为后验概率，后验概率是根据数据（也就是证据）来的。

下面这个根据先验概率 P(H) 和证据 e，计算后验概率 P(H|e) 的公式称为贝叶斯公式。

拿到一个贝叶斯公式的概率问题，首先要确定“假设是什么”及“证据是什么”，然后再代入公式。这样就不容易出错了。

例题: 不公平的硬币

有 10 枚硬币，其中有 1 枚是不公平的，随机抛出正面的概率为 0.8，另外 9 枚都是公平的，也就是随机抛出正面的概率是 0.5。

现在从 10 枚硬币中随机取出 1 枚，随机地抛了 3 次，结果为"正正反"。求该硬币为不公平硬币的概率。

思路参考

根据题目描述，假设 H 是 "该硬币为不公平硬币"，证据 e 是 "随机抛出该硬币 3 次的结果为正正反"

现在我们要求的是当我们有了证据 e 的条件下，假设 H 成立的概率是多少，也就是 P(H|e)

贝叶斯公式如下

其中 P(H) 是先验概率，根据业务理解，也就是本题给的条件，是 1/10。相应地 P( H ) 就是 9/10。

P(e|H) 是当假设 H 成立时，在一次观察中获得证据 e 的概率。也就是如果该硬币为不公平硬币，随机抛3次得到正正反的概率。

有了以上概率值，我们就可以根据贝叶斯公式计算后验概率 P(H|e) 了

模拟验证结果

import numpy as np
from multiprocessing import Pool

def flip(p):
    # 如果投掷结果为正，返回 True
    return np.random.rand() < p

def test(ps):
    np.random.seed()
    N = 0 # 记录实验结果为"正正反"的次数
    n = 0 # 记录实验结果为"正正反"时，不公平硬币的次数
    T = int(1e7)
    for _ in range(T):
        # 随机取到的硬币，如果 idx 为 9 则取到不公平硬币
        idx = np.random.randint(0, 10)
        p = ps[idx]
        # 实验: 投 3 次，如果结果为"正正反"则记录
        if not flip(p):
            continue
        if not flip(p):
            continue
        if flip(p):
            continue
        N += 1
        if idx == 9:
            n += 1
    return n / N

p1 = 0.5 # 公平硬币出正面的概率为 0.5
p2 = 0.8 # 不公平硬币出正面的概率为 0.8
ps = [p1] * 9 + [p2] # 10 枚硬币，其中 1 枚为不公平硬币
args = [ps] * 8
pool = Pool(8)
ts = pool.map(test, args)
for i in range(len(args)):
    t = ts[i]
    print("P(不公平硬币|投掷结果为\"正正反\"): {:.6f}".format(t))

模拟结果

P(不公平硬币|投掷结果为"正正反"): 0.102335
P(不公平硬币|投掷结果为"正正反"): 0.102071
P(不公平硬币|投掷结果为"正正反"): 0.102196
P(不公平硬币|投掷结果为"正正反"): 0.102102
P(不公平硬币|投掷结果为"正正反"): 0.102111
P(不公平硬币|投掷结果为"正正反"): 0.102182
P(不公平硬币|投掷结果为"正正反"): 0.102154
P(不公平硬币|投掷结果为"正正反"): 0.102363


阅读量：168

点赞量：0

收藏量:0