数概率

【Puzzle】有放回抽样还是无放回抽样

字数统计: 2.1k字   |   阅读时长: 9分
,

摘要: 《概率50题》有放回与无放回抽样

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

这是概率面试题连载第 22 期，我们继续看 《Fifty challenging problems in probability with solutions》 中的一道题。

往期的内容整理在这篇文章里；或者看这个 github 仓库。

本题是关于贝叶斯公式的，有了前面几期关于不公平的硬币的题目的铺垫，这道题就简单了。

Should-You-Sample-with-or-wothout-Replacement

Two urns contain red and black balls, all alike except for color
Urn A has 2 red balls and 1 black
Urn B has 101 red and 100 black
An urn is chosen at random, and you win a prize if you correctly name the urn on the basis of evidence of two balls drawn from it
After the first ball is drawn and its color is reported, you can decide whether or not the ball shall be replaced before drawing the second
How do you order the second drawing, and how do you decide the urn?

有两个桶，名称分别为 A 和 B，桶内有红色和黑色的球，其中

  • A 桶有 2 个红球和 1 个黑球。
  • B 桶有 101 个红球和 100 个黑球。

随机选出一个桶放到你面前，然后从中抽样两个球，基于这两个球的颜色猜该桶是 A 还是 B。

你可以选择有放回抽样或者无放回抽样，也就是你可以决定在抽取第二个球之前，是否将抽出的第一个球放回去再抽第二次。

问：为了使得猜中桶名的概率最大，应该有放回抽样还是无放回抽样，猜中的概率是多少。

思路参考

本题的目标是根据抽样两个球的结果，来猜当前是哪个桶。有两种获取证据的方式，一种是有放回抽样抽两个球，另一种是无放回抽样抽两个球。我们要选择使得猜中概率更大的那个抽样方式。

按照【不公平的硬币】系列问题积累的方法论，我们应该首先分析证据和假设有哪些，然后算似然值，然后推公式计算。

(1) 假设和证据

首先我们看都有哪些可能的证据。由于抽样两个球，且球的种类有红和黑，因此无论有放回抽样还是无放回抽样，观察到的证据都可能有 ”两红”、”一红一黑”、”两黑” 这三种，分别记为 e1, e2, e3。

然后我们看都有哪些可能的假设。由于有 A 和 B 这两种桶，因此针对随机取出的桶有两种假设：桶名为 A 和 桶名为 B，分别记为 H1, H2

有哪些证据和假设都与抽样是否有放回无关。

(2) 先验概率

由于一共两个桶，随机抽取一个，因此抽到的桶的名称的先验概率均为 1/2，与抽样是否有放回无关。

(3) 似然值

  • 有放回抽样

对于 A 桶，有放回抽样两个球，得到 e1, e2, e3 三种证据的概率分别为

对于 B 桶，有放回抽样两个球，得到 e1, e2, e3 三种证据的概率分别为

  • 无放回抽样

对于 A 桶，无放回抽样两个球，得到 e1, e2, e3 三种证据的概率分别为

对于 B 桶，无放回抽样两个球，得到 e1, e2, e3 三种证据的概率分别为

(4) 推导 P(T)

其中 P(ei|Hj) 是我们之前算好的似然值，P(Hj) 是之前算好的先验概率。

(5) 计算

我们分别计算在有放回抽样和无放回抽样 2 次时，预测正确的概率 P(T)

  • 有放回抽样
  • 无放回抽样

蒙特卡洛模拟

代码风格与 【Puzzle】不公平的硬币3 中的类似。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import numpy as np
from multiprocessing import Pool

class Box:
    def __init__(self, nR, nB, t):
        # 当前子在盒子中的
        self.nR = nR
        self.nB = nB
        # 抽出未放回的
        self.mR = 0
        self.mB = 0
        self.t = t

    def sample_with_replacement(self):
        if np.random.randint(0, self.nR + self.nB) < self.nR:
            return "R"
        else:
            return "B"

    def sample_without_replacement(self):
        if np.random.randint(0, self.nR + self.nB) < self.nR:
            self.nR -= 1
            self.mR += 1
            return "R"
        else:
            self.nB -= 1
            self.mB += 1
            return "B"

    def reset(self):
        self.nB += self.mB
        self.mB = 0
        self.nR += self.mR
        self.mR = 0

    def sample(self, method):
        if method == "with":
            return self.sample_with_replacement()
        else:
            return self.sample_without_replacement()

class Model:
    def __init__(self, boxs, method):
        self.boxs = boxs
        self.method = method
        # mapping 记录每种证据下两种盒子种类的次数
        # 共有 6 个参数
        self.mapping = {"RR": np.array([0, 0])
                       ,"RB": np.array([0, 0])
                       ,"BB": np.array([0, 0])
                       }

    def update(self, e, idx):
        """
        根据数据 (e, idx) 更新 mapping 的参数
        数据的含义是证据 e 对应硬币种类 idx
        """
        self.mapping[e][idx] += 1

    def train(self):
        """
        随机生成数据训练
        """
        n_train = int(1e5)
        for i in range(n_train):
            idx = np.random.randint(0, len(self.boxs))
            box = self.boxs[idx]
            # 抽取两次，获取证据
            e = [box.sample(self.method), box.sample(self.method)]
            if e[0] == "B" and e[1] == "R":
                e[1], e[0] = e[0], e[1]
            e = "".join(e)
            self.update(e, box.t)
            box.reset()
        for k, v in self.mapping.items():
            print("证据 {} 下的A桶有{}个, B桶有{}个".format(k, v[0], v[1]))
        print("===训练结束===")

    def predict(self, e):
        """
        根据证据 e 猜盒子种类，返回 0 或 1
        """
        return np.argmax(self.mapping[e])

    def test(self, T):
        correct = 0
        np.random.seed()
        for _ in range(T):
            # 随机选盒子
            idx = np.random.randint(0, len(self.boxs))
            box = self.boxs[idx]
            # 抽取 2 次，获取证据
            e = [box.sample(self.method), box.sample(self.method)]
            if e[0] == "B" and e[1] == "R":
                e[1], e[0] = e[0], e[1]
            e = "".join(e)
            # 根据证据猜硬币种类
            if self.predict(e) == box.t:
                correct += 1
            box.reset()
        return correct / T

class Solver:
    def __init__(self, method):
        self.method = method
        self.boxs = [Box(2, 1, 0), Box(101, 100, 1)]
        self.ans = -1

    def __call__(self):
        model = Model(self.boxs, self.method)
        model.train()
        T = int(1e7)
        args = [T] * 8
        pool = Pool(8)
        ts = pool.map(model.test, args)
        self.ans = sum(ts) / len(ts)

solver1 = Solver("with")
solver1()
print("有放回时，P(T): {:.6f}".format(solver1.ans))
solver2 = Solver("without")
solver2()
print("无放回时，P(T): {:.6f}".format(solver2.ans))

模拟结果

1
2
3
4
5
6
7
8
9
10
证据 RR 下的A桶有22280个, B桶有12755个
证据 RB 下的A桶有21997个, B桶有24808个
证据 BB 下的A桶有5561个, B桶有12599个
===训练结束===
有放回时，P(T): 0.596081
证据 RR 下的A桶有16452个, B桶有12755个
证据 RB 下的A桶有33433个, B桶有25112个
证据 BB 下的A桶有0个, B桶有12248个
===训练结束===
无放回时，P(T): 0.623070
Share