【Puzzle】收集优惠券

摘要: 《概率50题》收集优惠券

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

---

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

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

---

问题描述

Collecting Coupons

Coupons in cereal boxes are numbered 1 to 5
All 5 coupons must be collected to receive a prize
With one coupon per box, how many coupons on average are required to make a complete set?

每个盒子中有一张优惠券，优惠券共有 5 种，编号为1到5。必须收集所有5张优惠券才能获得奖品。

问: 收集到一套完整的优惠券平均需要打开多少盒子？

思路参考

单独考虑每个优惠券。

记 T1 为一个随机变量，表示拿到第一个没见过的编号所需的盒子个数。P(T1 = 1) = 1，E(T1) = 1

记 T2 为一个随机变量，表示从拿到第一个没见过的编号到拿到第二个没见过的编号所需的额外的盒子个数。根据全期望公式

$$\begin{align} E(T_{2}) &= \sum\limits_{X}E_{X}(E_{T_{2}|X}(T_{2}|X)) \\ &= \sum\limits_{x}P(X = x)E_{T_{2}|X=x}(T_{2}|X=x) \\ \end{align}$$

这里的 X 是新开的盒子的数字是否是见过的那 1 个。共有两种情况

• 是前面见过的那1个，概率 1/5，此时额外的盒子数的期望是 1 + E(T2)
• 不是前面见过的那2个，概率 4/5，此时额外的盒子数就是 1

$$E(T_{2}) = \frac{4}{5} + \frac{1}{5}(1 + E(T_{2})) \\ E(T_{2}) = \frac{5}{4}$$

记 T3 为一个随机变量，表示从拿到第二个没见过的编号到拿到第三个没见过的编号所需的额外的盒子个数。根据全期望公式

$$\begin{align} E(T_{3}) &= \sum\limits_{X}E_{X}(E_{T_{3}|X}(T_{3}|X)) \\ &= \sum\limits_{x}P(X = x)E_{T_{3}|X=x}(T_{3}|X=x) \\ \end{align}$$

这里的 X 是新开的盒子的数字是否是见过的那 2 个。共有两种情况

• 是前面见过的那2个，概率 2/5，此时额外的盒子数的期望是 1 + E(T3)
• 不是前面见过的那2个，概率 3/5，此时额外的盒子数就是 1

$$E(T_{3}) = \frac{3}{5} + \frac{2}{5}(1 + E(T_{3})) \\ E(T_{3}) = \frac{5}{3}$$

记 T4 为一个随机变量，表示从拿到第3个没见过的编号到拿到第4个没见过的编号所需的额外的盒子个数。根据全期望公式

$$\begin{align} E(T_{4}) &= \sum\limits_{X}E_{X}(E_{T_{4}|X}(T_{4}|X)) \\ &= \sum\limits_{x}P(X = x)E_{T_{4}|X=x}(T_{4}|X=x) \\ \end{align}$$

这里的 X 是新开的盒子的数字是否是见过的那 3 个。共有两种情况

• 是前面见过的那3个，概率 3/5，此时额外的盒子数的期望是 1 + E(T4)
• 不是前面见过的那3个，概率 2/5，此时额外的盒子数就是 1

$$E(T_{4}) = \frac{2}{5} + \frac{3}{5}(1 + E(T_{4})) \\ E(T_{4}) = \frac{5}{2}$$

记 T5 为一个随机变量，表示从拿到第4个没见过的编号到拿到第5个没见过的编号所需的额外的盒子个数。根据全期望公式

$$\begin{align} E(T_{5}) &= \sum\limits_{X}E_{X}(E_{T_{5}|X}(T_{5}|X)) \\ &= \sum\limits_{x}P(X = x)E_{T_{5}|X=x}(T_{5}|X=x)) \\ \end{align}$$

这里的 X 是新开的盒子的数字是否是见过的那 4 个。共有两种情况

• 是前面见过的那4个，概率 4/5，此时额外的盒子数的期望是 1 + E(T5)
• 不是前面见过的那4个，概率 1/5，此时额外的盒子数就是 1

$$E(T_{5}) = \frac{1}{5} + \frac{4}{5}(1 + E(T_{5})) \\ E(T_{5}) = 5$$

收集到一套完整的优惠券需要打开的盒子个数的期望为 E1 + E2 + E3 + E4 + E5 = 137/12 = 11.416667

蒙特卡洛模拟

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

def run():
    setting = set()
    n = 0
    while True:
        n += 1
        x = np.random.randint(1, 6)
        if x in setting:
            continue
        setting.add(x)
        if len(setting) == 5:
            break
    return n

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

T = int(1e7)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("{:.6f} coupons on average are required".format(t))

11.415423 coupons on average are required
11.417857 coupons on average are required
11.415529 coupons on average are required
11.417148 coupons on average are required
11.416793 coupons on average are required
11.413937 coupons on average are required
11.416149 coupons on average are required
11.416380 coupons on average are required

---