最近做了一个集卡的活动，基本就是支付宝五福卡的翻版，只是在计算期望的时候，发现不好算，问了一下AI，说这个是”集邮问题“。

什么是集邮问题

每次随机获得一张邮票，可能重复；目标是收集齐全部 8 种邮票，研究平均需要抽多少次，以及抽若干次后集齐的概率。

如何计算

如果概率一样，有现成的公式可以计算。

def coupon_collector_math(n):
    # 利用公式直接计算期望，O(n)
    harmonic_sum = sum(1/i for i in range(1, n + 1))
    return n * harmonic_sum

如果概率不一样，就需要用动态规划去计算。

def expected_draws(probabilities: list[float]) -> float:
    """
    计算集齐所有邮票需要的期望抽取次数。

    probabilities:
        每一种邮票被抽中的概率，所有概率之和必须为 1。
        例如 [0.25, 0.20, ..., 0.04]
    """
    n = len(probabilities)
    full_state = (1 << n) - 1

    if abs(sum(probabilities) - 1.0) > 1e-9:
        raise ValueError("所有邮票概率之和必须等于 1")

    if any(p <= 0 for p in probabilities):
        raise ValueError("每种邮票的概率都必须大于 0，否则永远无法集齐")

    @lru_cache(maxsize=None)
    def dp(state: int) -> float:
        if state == full_state:
            return 0.0

        duplicate_probability = 0.0
        new_stamp_cost = 0.0

        for i, probability in enumerate(probabilities):
            if state & (1 << i):
                # 已经拥有这张邮票，抽中后状态不变
                duplicate_probability += probability
            else:
                # 抽中新邮票，进入下一个状态
                next_state = state | (1 << i)
                new_stamp_cost += probability * dp(next_state)

        # E = 1 + 重复概率 * E + 新状态的期望
        # 移项后：
        # E = (1 + 新状态的期望) / (1 - 重复概率)
        return (1.0 + new_stamp_cost) / (1.0 - duplicate_probability)

    return dp(0)

测试结果

如果是8张邮票，概率一样，都是0.125，则期望是 21.74 次。

probabilities = [
    0.125,
    0.125,
    0.125,
    0.125,
    0.125,
    0.125,
    0.125,
    0.125
]

如果概率不一样，像下面这种，则期望是 1302.51 次。

期望并不等于一定

期望只是说拉平下来，需要多少次能够集齐。但如果你是非酋，那可能需要很多次。

如果是8张邮票，概率一样，则如下。