排列组合面试问题

Question

排列组合面试问题

21

这是一个很反直觉的例子：

想象一个装有球的罐子，其中三分之二的球是一种颜色，另外三分之一是另一种颜色。一个人从罐子里抽出了5个球，并发现有4个是红色的，1个是白色的。另一个人从罐子里抽出了20个球，并发现有12个是红色的，8个是白色的。哪个人应该更有信心认为罐子里有三分之二的红色球和三分之一的白色球，而不是相反的？每个人应该给出什么样的赔率？

我知道正确答案，但可能不太明白赔率计算。有人能解释一下吗？

- Nick

请重新开启。严格来说，这与编程无关，但至少有一定的相关性。 - dsimcha

另外，请说明我们是否可以假设球桶中的球数与抽取的数量相比非常大，如果不是，球桶中有多少个球。 - dsimcha

dsimcha，题目的副本中没有指定球的数量。 - ʞɔıu

让我说，我认为这是一个特别糟糕的面试问题。这些概念非常容易理解，但在面试的情况下，涉及到的计算有点太长而且繁琐了。 - Daniel Daranas

@Daniel：如果繁琐但直接的贝叶斯计算是最简单的计算，那么这将是正确的。但在概率论中，我们永远不知道，也许有一个聪明的观察可以避免计算并使问题变得微不足道。 - Federico A. Ramponi

显示剩余5条评论

5个回答

14

假设事件A是3个球中有2个是红色的概率为2/3，那么¬A就是3个球中有2个是白色。假设事件B是第一个观察者看到5个球中有4个是红色的概率，假设事件C是第二个观察者看到20个球中有12个是红色。

应用简单的组合学原理，我们可以得到：

P(B|A) = (5选4)(2/3)⁴(1/3)¹ = 80/243
P(B|¬A) = (5选4)(1/3)⁴(2/3)¹ = 10/243

因此，根据贝叶斯定理，第一位观察者对A的真实性有8/9的置信度。

对于第二位观察者：

P(C|A) = (20选12)(2/3)¹²(1/3)⁸ = 125970 * 2¹²/3²⁰
P(C|¬A) = (20选12)(1/3)¹²(2/3)⁸ = 125970 * 2⁸/3²⁰

因此，再次根据贝叶斯定理，第二位观察者对A的真实性有16/17的置信度。

因此，观察者二更有把握认为三分之二的球是红色的。关键在于理解贝叶斯定理的工作原理。事实上，唯一重要的是观察到的红球和白球数量的差异。其他所有因素（尤其是所抽取的总球数）都会在方程式中相互抵消。

- Adam Rosenfield

Adam，如果你还没有看过使用赔率和可能性比进行计算的方法，请看一下我的帖子。希望你会喜欢它。 - A. Rex

3

我假设一个假设相对于另一个的'先验'概率为1/2，并且两个人在取出球后再将其重新插入（提取是彼此独立的）。

正确答案是第二个观察者应该比第一个更有信心。我的先前答案由于计算中的微小错误而错误，非常感谢Adam Rosenfield进行的更正。

让2/3R 1/3W表示“罐中包含2/3红球和1/3白球”的事件，让4R,1W表示“提取4个红球和1个白球”。然后，使用贝叶斯定理，

P [2/3R 1/3W | 4R,1W] = P [4R,1W | 2/3R 1/3W] P [2/3R 1/3W] / P [4R,1W] = (2/3) ^ 4 (1/3) ^ 1 (1/2) / P [4R,1W]

现在，由于2/3R 1/3W和1/3R 2/3W根据假设是互补的，

P [4R,1W] = P [4R,1W | 2/3R 1/3W] P [2/3R 1/3W] + P [4R,1W | 1/3R 2/3W] P [1/3R 2/3W] = (2/3) ^ 4 (1/3) ^ 1 (1/2) + (1/3) ^ 4 (2/3) ^ 1 (1/2)

因此，

P [2/3R 1/3W | 4R,1W] = (2/3) ^ 4 (1/3) ^ 1 (1/2) / {(2/3) ^ 4 (1/3) ^ 1 (1/2) + (1/3) ^ 4 (2/3) ^ 1 (1/2)} = 2 ^ 4 / (2 ^ 4 + 2) = 8/9

对于 P[2/3R 1/3W | 12R，8W] 的相同计算（即使用（2/3）¹²（1/3）⁸ 而不是（2/3）⁴（1/3）¹），现在得到的结果为16/17，因此第二个观察者的置信度高于第一个观察者。

- Federico Ramponi

关于重新插入 - 如果球的数量很大（可能是同样有效的假设），则不必要。 - Jason S

不应该有 P[4R, 1W | 2/3R 1/3W] = (2/3)^4 * (1/3)^1 * (5 choose 4) 吗？而且我不确定您是如何得出50%先验分布的。 - FryGuy

@FryGuy，50%（或任何其他已知数字！）的先验条件是做出决策的必要前提...如果我事先告诉你“有2/3个红球，100%确定”，那么问题就很简单，两个人都可以同样自信...这里缺少太多数据，我认为。 - Daniel Daranas

检查一下你的算术 - 你的推理是正确的，但如果你输入数字，第一个观察者应该得到8/9，第二个观察者应该得到16/17。 - Adam Rosenfield

@Adam Rosenfield：啊！有一个2^1神奇地变成了1。一分钟后更正。非常感谢！ - Federico A. Ramponi

2

P[2/3R 1/3W | 4R, 1W] = (2/3)^4 * (1/3)^1 * (1/2) / { (2/3)^4 * (1/3)^1 * (1/2) + (1/3)^4 * (2/3)^1 * (1/2) } = 2^4 / (2^4 + 1) = 16/17

= ⅔^4*⅓ / (⅔^4*⅓ + ⅓^4*⅔)
= 16/243 / (16/243 + 2/243)
= 16/18

在编程方面，P(⅔R⅓W | 12R8W)确实等于16/17，因此12R8W可以更加自信。

- bobince

1

如果是这样，那么这个问题为什么会违反直觉呢？更多的采样=更高的置信度，特别是当你的样本与你的期望一致时。 - z -

@Daneil Daranas：你对“310^11的质因数”问题的评论真是太搞笑了。不幸的是，这个问题根本不需要计算，如果你知道理论，它就很容易。你说得没错，这是一个糟糕的编程问题，但它并不“太长而繁琐”，你可以*直觉地得出答案。 - A. Rex

@A. Rex 那么，是Federico（同等概率）正确还是bobince（一个比另一个更可能）正确呢？而且在没有任何计算的情况下，“推理”是什么呢？ - Daniel Daranas

确实，没错 - 我保留了分母不变只是为了明确表明16/17>16/18。 - bobince

@yx：我认为这种违反直觉的情况源于第一位观察者拥有一个“更倾向于”2/3红假设的样本（他拥有更大比例的红球）。但请记住，第二位观察者拥有更大的样本，两个事实都必须被考虑在内。 - Federico A. Ramponi

显示剩余6条评论

0

呵呵。也许我完全错了，但是答案不应该是第二个人吗？

一个人看到的比例是：4:1 4/5 : 1/5

另一个人看到的比例是3:1 3/4 : 1/4

所以简单的问题是谁更接近2/3 : 1/3？因此答案是观察者二。

也许我犯了两个错误，并且对于我认为实际上很直观的事情进行了漫长的解释，但请原谅我的耐心。

- Ajeet Ganga

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- A. Rex · Accepted Answer

Eliezer Yudkowsky（艾利泽尔·尤德科夫斯基）有一篇（非常长，但很好的）关于Bayes定理的解释。在页面的70%处，有一个段落开始 "你面前有一个书包"，解释了这个问题的核心。

要点是只有抽出的红球和白球数量之间的差异才是重要的。因此，与其他人所说的相反，你不必进行任何计算。（这是以合理的假设(a)袋中装的球是可重复取样，或者(b)袋子里有很多球为前提的。那么球的数量并不重要）。以下是论据：

我们回顾一下Bayes' 定理：P(A|B) = P(B|A)* P(A)/P(B)。（关于语言学术语的注意事项：P(A) 是 先验概率 ，P(A|B) 是后验概率。B是你做出的一些观察结果，术语反映了你在观察之前和之后的信心。）这种形式的定理是可以的，@bobince 和 @Adam Rosenfield 正确地应用了它。但是，直接使用这种形式会使你容易受到算术错误的影响，并且它实际上并没有传达Bayes定理的核心。Adam在他的帖子中提到（我在上面也提到了），重要的是抽出的红球和白球数量之间的差异，因为“在方程式中其他的都会被抵消掉”。我们如何在不进行任何计算的情况下看到这一点？

我们可以使用赔率比和似然比的概念。什么是赔率比？好吧，我们不再考虑P(A)和P(¬A)，而是考虑它们的比率P(A)：P(¬A)。两者都可以从对方中恢复出来，但是赔率比的算法更加美好，因为我们不必标准化。此外，在其备用形式中，“领会”Bayes定理更容易。

那么，我们说不必标准化，备用形式是什么？好吧，我们来计算一下。Bayes定理表明后验赔率为

P(A|B) : P(¬A|B) = (P(B|A)* P(A) / P(B)) : (P(B|¬A)* P(¬A) / P(B))。

P(B)是一个标准化因子，使概率总和为1；但我们正在使用赔率，在这里，2:1 和 4:2 的比例是相同的，所以P(B)可以消除。我们得到了一个容易分解的表达式：

在贝叶斯定理中，对于事件B已经发生，事件A发生的概率为P(A|B)，A不发生的概率为P(¬A|B)。根据贝叶斯公式，可以得到后验比率等于似然比乘以先验比率，即P(A|B) : P(¬A|B) = (P(B|A) * P(A)) : (P(B|¬A) * P(¬A)) = (P(B|A) : P(B|¬A)) * (P(A) : P(¬A))。当进行一系列相互独立的实验时，先验比率每次都会被似然比所修正。如果一个事件有x : y的先验比率，随着r个红球和w个白球的抽取，最终的后验比率将为(x : y) * (2^(r-w) : 1)。因此，重要的是红球和白球的数量差异。重点在于，如果你理解上述加粗的方程式，那么这个问题就非常简单。同样重要的是，你可以确信自己没有搞错任何算术，因为你只需要做很少的计算。
所以这是个糟糕的编程问题，但它确实是一个好的测试加粗的方程式。仅供练习，让我们将其应用于另外两个问题：
我随机选择两个硬币之一，一个是公平的硬币，另一个是双面都是正面的假硬币，每个硬币被选中的概率均为50%。我把它抛了三次，结果都是正面。它是真硬币的概率是多少？
先前的比例是真：假=1：1，如问题所述。实际硬币出现三次正面的概率是1/8，而假硬币则是1，因此似然比值为1:8。因此后验比值=先验比值*似然比值=1：8。因此，它是真硬币的概率是1/9。
此问题还提出了一个重要的警告：每个可能的观测结果有可能具有不同的似然比值。这是因为B的似然比值是P(B|A)：P(B|¬A)，它与¬B的似然比值不一定相关，后者是P(¬B|A)：P(¬B|¬A)。不幸的是，在所有上述示例中，它们都是相互倒置的，但在这里，它们不是。
实际上，假设我将硬币抛一次，结果是反面。那么它是真硬币的概率是多少？显然是1。贝叶斯定理如何体现？对于这个观测结果，似然比值是用真硬币和假硬币得到该结果的概率之比，即1/2:0=1:0。也就是说，看到单个反面会降低硬币是假的可能性，这符合我们的直觉。
以下是来自Eliezer页面的问题：在你面前有一个书包，里面装着1000个扑克筹码。我一开始就拥有两个这样的书包，一个包含700个红色和300个蓝色的筹码，另一个包含300个红色和700个蓝色的筹码。我抛了一个公平的硬币来确定使用哪个书包，因此你在你面前的书包是红书包的先验概率为50%。现在，你随机取样，在每个筹码后进行替换。在12次采样中，你得到了8个红色和4个蓝色的筹码。这是主要由红色筹码组成的书包的概率是多少？（你不需要精确计算 - 粗略估计就足够了。）先验概率为红:蓝=1:1。似然比为7:3和3:7，因此后验概率为(7:3)^8 * (3:7)^4 = 7^4 : 3^4。在这一点上，我们只需估计7:3为2:1，得到2^4 : 1 = 16 : 1。最终答案更大，所以它肯定大于95%左右；正确答案约为96.7%。与大多数人的答案相比，他们的答案在70-80%范围内。
我希望您同意，在这种情况下，当以这种方式查看时，问题变得非常简单且具有直观性。