·
关注 发布在 Towards Data Science · 14 分钟阅读 · 2023 年 3 月 4 日
--
图片由 Tamanna Rumee 提供，来源于 Unsplash
数学的世界充满了迷人的难题和悖论，它们挑战我们对周围世界的理解。优惠券收集者问题就是这样一个难题，这个古老的问题让数学家和统计学家们几代人以来都为之着迷。优惠券收集者问题如下：
考虑一个涉及收集 n 种独特优惠券的竞赛。每个谷物盒子里都有一张优惠券，每张优惠券在给定盒子中出现的概率相同。在你打开多少个盒子之前，你能确保每种类型的优惠券至少有一张？这个看似简单的问题有一个复杂的答案，并且在从计算机科学到金融等领域中都有应用。在本文中，我们将深入探讨优惠券收集者问题，探索其框架，并讨论其许多迷人的含义。
在解决这个问题之前，让我们重新回顾一下几何随机变量的一些性质。这将提供一个有效的机制来计算描述问题解决方案架构的各种参数。定义：如果随机变量 X 的概率质量函数如下所示，则称 X 遵循参数为 p 的几何分布：
直观上，几何随机变量表示为获得成功所需的独立试验次数的分布，假设成功的概率保持不变，即 p。因此，找到 P(X = k) 等同于找到需要 k 次试验才能获得成功的概率，即在第一次成功之前有 k — 1 次失败。因此，所需的概率为：
几何随机变量在现实世界问题中有许多应用，例如建模赢得游戏所需的尝试次数或在呼叫中心联系客户所需的电话次数。优惠券收集者问题也可以有效地使用几何随机变量建模（具体来说，是一组独立的、不完全相同分布的几何变量的总和，我们稍后会看到）。几何随机变量具有以下性质：
可选证明： 首先，我们将确定几何随机变量的期望值。回顾一下，随机变量的期望值类似于其值的加权平均值，加权由其概率质量函数给出。可以证明，几何随机变量的期望值是其参数 p 的倒数，即成功的概率。证明如下：
要评估上述表达式，我们使用了一个小技巧。已知 p 是一个连续参数，其值在 0 和 1 之间（因为它是概率的度量）。如果我们可以将其建模为一个常数公比 r 的几何级数，那么求和一个无限级数就会变得非常简单。然后，
我们需要找到一种方法，将给定的无限级数和转换为可以使用上述表达式轻松评估的几何级数。为此，我们回顾一下 x^i 的导数是 i*x^(i−1)，这与上述形式非常相似，只需将 x 替换为 1 — p。因此，我们得到：
我们可以将导数移出求和，因为导数的和等于和的导数。因此，
我们现在可以使用无限几何级数和来得到：
上述结果在大多数概率教材中是标准的。对于本文而言，理解如何使用上述结果比理解结果的推导过程更为重要。因此，我们已经证明几何随机变量的期望值是其参数 p 的倒数。现在，我们继续找出几何随机变量的方差。数学稍微复杂，如果你只是对解决给定问题感兴趣，可以选择跳过这一部分。
计算几何分布的方差：我们使用以下方差公式：
我们现在继续计算 E(X(X − 1))：
就像之前一样，我们观察到 x^i 对 x 的二阶导数是 i*(i − 1)*x^(i−2) 因此：
因此，
因此，我们已经得到了几何分布的方差和期望。
要解决当前问题，我们首先需要对其进行建模，这包括识别其参数、假设和相关变量。
-
参数：问题给出了一个参数，即 n，总独特优惠券的数量。
-
假设：我们假设每个优惠券在给定盒子中出现的概率相等。另一个微妙的假设是我们有无限的盒子可以打开，即我们没有打开盒子的数量限制。
-
变量：为了找到问题的解决方案，我们需要确定在获得每种类型的至少一个优惠券之前必须打开的盒子数量。这要求我们定义适当的变量，以封装解决方案所需的元素。这些变量的性质和属性取决于问题所源自的领域。由于优惠券收集者问题根植于统计学和概率论领域，因此这些变量的性质将是随机的。因此，我们定义随机变量 T，表示收集所有 n 种独特优惠券所需打开的最小盒子数量。我们使用随机变量来解决这个问题，因为 T 的值不一定是确定的。实际上，T 的值可以是从 n 到无限大的任何值。我们能回答的唯一问题是：
• T 的期望（或平均）值是多少？
• T 的方差（或值的平均分布）是多少？
• 打开超过 c 个盒子的概率是多少？换句话说，T > c 的概率是多少？
在对问题的各个元素进行建模之后，我们对其设置、范围和期望有了清晰的了解。现在我们继续解决方案的工作。
我们首先分析 T 的分布。然而，很快会发现 T 的分布相当复杂，不能归入任何已知的概率分布。这是因为即使假设每个优惠券在给定盒子中出现的概率相等，但随着我们收集更多优惠券，找到新优惠券的概率会逐渐减少。考虑一个场景，我们需要收集 100 个独特的优惠券。当我们打开第一个盒子时，由于我们还没有任何优惠券，因此可以保证找到一个新优惠券，即：
然而，当我们打开第二个盒子时，找到新优惠券的概率会略微降低，因为有（1/100）的机会我们可能会找到在第一个盒子中已经找到的相同优惠券。
随着我们继续打开更多盒子，找到新优惠券的概率持续减少（不是严格减少），因为剩下的独特优惠券越来越少。因此，不恒定的概率值使得将 T 分配到一个共同的概率分布变得相当困难。因此，我们采用了分治法，这是一种非常流行的解决概率问题的策略。这涉及将问题分解为复杂性较小的更小部分，并独立处理每个部分。由于 T 测量了收集 n 个独特优惠券所需的时间或盒子数量，我们通过提出 Tᵢ来测量收集第 i 个优惠券所需的时间或盒子数量，从而将其分解。我们可以将 T 表示为所有 Ti 的总和：
这有什么好处？好吧，Tᵢ的分布（与 T 的分布不同）是由一个常数概率值参数化的。让我们理解这意味着什么。
我们可以将每次开盒子视为一系列伯努利试验中的一次试验，其中成功意味着找到一个新的、以前未见过的优惠券。（回忆一下，伯努利试验是一种随机实验，只有两种可能的结果：成功和失败。例如，抛硬币就是一个伯努利试验，其中成功可能定义为正面，失败则定义为反面。）在开始时，我们还没有收集任何优惠券，因此第一次试验的成功概率是 n/n，即 1.0：
在第二次尝试时，还剩下 n-1 个独特优惠券要收集，总共有 n 个优惠券，因此成功的概率是(n-1)/n。这是因为只有一个优惠券会导致失败（即，重复了第一次尝试中收集到的优惠券），而 n-1 个优惠券会导致成功（即，一个还未被收集的新优惠券）。
在第三次尝试时，还剩下 n-2 个独特优惠券要收集，总共有 n 个优惠券，因此成功的概率是(n-2)/n。
同样地，在第四次尝试时，成功的概率是(n-3)/n，依此类推。我们可以推导出公式，以找出收集第 i 个独特优惠券的概率（即，已经收集了 i-1 个独特优惠券的情况下，打开一个盒子找到一个新优惠券的概率）：
回忆一下，Tᵢ测量了收集第 i 个独特优惠券所需的独立试验次数。这听起来很熟悉；是的，它就是几何随机变量！这些试验中的每一个都对应于一个伯努利试验，其中成功意味着在收集了 i-1 个独特优惠券的情况下，找到一个新的、以前未见过的优惠券。因此，
因此，我们可以将 T 视为非同质几何分布的总和：
我们现在可以继续回答之前提出的问题。
为了找出 T 的期望值，我们使用随机变量之和的期望值等于其期望值之和的性质：
由于 Tᵢ是一个几何随机变量：
因此，
其中 H(n)指的是第 n 个调和数：
对于大值的 n，它可以渐近地被近似为：
其中 γ ≈ 0.577215665 是欧拉-马歇罗尼常数。我们可以把它看作是一个估计值，即在多次重复收集优惠券的过程中，收集所有 n 张优惠券所需打开的盒子的平均数量。例如，假设你想从一组促销谷物盒中收集所有 100 种独特的优惠券，并且你计划每次买一个盒子，直到你收集齐全。公式 n * H(n) 将估计为完成收集所需购买的平均盒子数量，假设每个盒子有同等的机会包含任意一种 100 种优惠券。以下 python 代码可以帮助我们计算这个值：
import math
def coupon_collectors(n):
res = 0
for i in range(1, n + 1):
res += 1/i
return res*n
def coupon_collectors_approx(n):
return n*math.log(n) + 0.5 + n*0.577215665
print(coupon_collectors(100))
# 518.737751763962
print(coupon_collectors_approx(100))
# 518.7385850988092当然，实际上，为了收集所有 100 种优惠券，你所需购买的实际盒子数量会因试验而异，具体取决于每个盒子中获取的特定优惠券。然而，公式 n * H(n) 给了我们一个对平均情况的预期，这可以成为规划和预算的有用工具。
对于较大的 n 值，该公式预测需要打开更多的盒子以收集所有 n 种独特的优惠券。这是因为找到新优惠券的概率随着已收集优惠券数量的增加而下降。调和数 H(n) 随着 n 对数增长，因此预期的盒子数量大致与 n ln n 成正比。这意味着收集大量独特的优惠券可能是一项具有挑战性且耗时的任务，这与我们的直觉相符。
E(T) 关于 n 的线性图 [作者图片]
接下来，我们尝试计算 T 的方差，以便了解收集所需的盒子数量在不同试验中的变化情况。由于所有试验都是独立的（假设每种优惠券在特定盒子中出现的概率相等），随机变量 Tᵢ, Tⱼ; i != j 也是独立的。因此，其和的方差是其方差之和。因此，
由于 Tᵢ 是一个几何随机变量：
因此，
在这里我们使用了欧拉对巴塞尔问题的方法：
例如，假设你想收集所有 100 种独特的优惠券，并且你多次重复这个过程。方差将给你一个估计，说明所需的盒子数量在不同试验中变化的程度。如果方差很小，则可以期待每次试验所需的盒子数量相似。如果方差很大，则所需的盒子数量可能在不同试验中变化很大。
def coupon_var(n):
return n**2 * (math.pi**2)/6
print(coupon_var(100))
# 16449.340668482262方差与 n² 成正比，因此对于较大的 n 值，方差增长的速度远快于所需的期望盒子数量。这意味着随着 n 的增大，收集所有 n 个优惠券所需的盒子数量变得越来越不可预测，估计你需要购买多少盒子会变得越来越困难。
Var(T) 与 n 的线图：E(T) 和 Var(T) 的增长订单比较 [作者图片]
最后，我们尝试计算（或至少界定）需要打开的盒子数量超过（或等于）c 的概率，即 T 取值大于或等于 c 的概率。由于 T 的分布相当复杂，找到这种概率的确切值非常困难。然而，统计学为我们提供了许多有用的不等式，帮助我们界定概率的值。具体来说，我们将使用马尔可夫不等式来上界 T 取值大于或等于 c 的概率。
马尔可夫不等式是概率理论中的一种强大工具，它允许我们对随机变量超出某一值的概率做出一般性陈述。这个不等式以俄罗斯数学家安德烈·马尔可夫的名字命名，他在 19 世纪末首次引入了它。马尔可夫不等式表示，对于任何非负随机变量 X 和任何正数 a，X 大于或等于 a 的概率小于或等于 X 的期望值除以 a。在数学符号中，这可以写作：
直观上，马尔可夫不等式表示，如果我们想知道随机变量取值大于或等于 a 的可能性，我们可以通过将随机变量的期望值除以 a 来界定这个概率。这个界限通常比较松，但在我们对随机变量的分布信息有限的情况下，它可能会很有用。
由于 T 是非负的（盒子数量不能为负），我们可以使用马尔可夫不等式：
上述近似对于当 n 的值非常大时估计概率可能会很有用。例如，假设我们想估计需要打开超过 1000 个盒子才能收集到所有 100 个独特的优惠券的概率。我们可以利用不等式来获得这个概率的上界，如下：
def coupon_collectors_approx(n):
return n*math.log(n) + 0.5 + n*0.577215665
def coupon_prob(n, c):
ev = coupon_collectors_approx(n)
return ev/c
print(coupon_prob(100, 1000))
# 0.5187385850988091因此，如果我们知道 n 和 c 的值，我们可以利用这个界限来估计我们需要打开超过 c 个盒子才能收集到所有 n 个独特的优惠券的概率。
总之，优惠券收集者问题是概率理论中的经典问题，具有广泛的实际应用。这个问题涉及收集一组 N 个独特的优惠券，其中每个优惠券在给定盒子中被找到的概率是相等的。我们讨论了这个问题的各种方面，包括收集所有 n 个独特优惠券所需时间的期望值和方差，以及收集所有 n 个独特优惠券所需的盒子数量超过给定值的概率。
优惠券收集者问题是一个引人入胜的问题，具有许多有趣的特性和应用。它是理解概率和统计的重要工具，其解决方案在许多实际应用中具有广泛的用途，从设计调查和收集数据到分析客户行为和预测市场趋势。通过理解优惠券收集者问题，我们可以获得对复杂系统行为的宝贵洞察，并在各种情境中做出更明智的决策。
感谢阅读！希望你喜欢这篇文章！