机器算法验证 - 硬概率问题：在给定以下抽奖规则的情况下，如何计算在袋子中仅选择 < 70% 的弹珠的概率？ - 吾爱随笔录

硬概率问题：在给定以下抽奖规则的情况下，如何计算在袋子中仅选择 < 70% 的弹珠的概率？

机器算法验证可能性

2022-03-20 06:29:57

想象一下，我的袋子里有 100 个弹珠。每颗大理石都有独特的标签。我想一次从那个袋子里抽出 9 个弹珠。我称之为选择。一旦我画了 9 个弹珠，我就把它们放回去。我做了 50 个这样的选择（换句话说，我画了 9 个弹珠并将它们放回 50 次）。

我需要知道在此过程中选择不超过 70% 的弹珠的概率。在我看来，这个概率百分比应该是 100%——选择 70% 或更多弹珠的概率。

1个回答

让我们一般地解决这个广义的Coupon Collector的问题，绘制 $m=9$ 在......之外 $n=100$ 球 $r=50$ 次。

如果 $E(i;r)$ 是事件，正是 $i$ 之后看到了不同的球 $r$ 抽签，然后——以此为条件——下一次抽签的机会 $k$ 还没有看到的球是通过计算其中的比例来找到的 $\binom{n}{m}$ 可能的样本包括已经看到的个球和尚未看到的个球。任何这样的样本都由已经看到的子集和未见过的个球 $m-k$ $k$ $m-k$ $i$ $k$ $n-i$

Pr (k ∣ E (i; r)) = \frac{(\binom{i}{m - k}) (\binom{n - i}{k})}{(\binom{n}{m})} .

$\Pr(k\mid E(i;r)) = \frac{\binom{i}{m-k}\binom{n-i}{k}}{\binom{n}{m}}.$

通过对可能的值求和，每个值乘以次抽签中准确地看到个不同的球。 $i=0, 1, \ldots, n$ $\Pr(E(i;r))$ $k$ $r+1$

这个更新规则，首先观察在第一次抽签中将获得次快速计算，因此最多需要的努力和只有的存储。 $m$ $(m+1)(n+1)$ $O((r-1)(m+1)(n+1))$ $O(n)$

以下是的概率分布以及沿途的一些里程碑。 $r=50$

我们可以跟踪沿途观察到迅速下降到几乎，因此最好绘制它的对数： $70$ $1$ $0$

次后这个机会只有，符合你的直觉。 $50$ $3.162808\times 10^{-51}$

其它你可能感兴趣的问题

上一篇通过数据集上的概率分布生成训练数据意味着什么下一篇高斯过程只是多元高斯分布吗？