彩票收集问题

彩票收集问题的一个描述是，有n种彩票，每次随机抽取其中一种彩票一张，则要收集每种彩票各一张所需要抽取的次数的期望是多少。

求解方法

对于每种彩票的抽取概率均相等的情况，则抽取到第一种彩票的概率为1，期望次数为1。之后抽取到第二种彩票的概率为从n种彩票中抽取n-1种彩票的概率，即 $(n ? 1) / n$ ，期望次数为 $n / (n ? 1)$ ，以此类推，第三种彩票的概率为 $(n ? 2) / n$ ，期望次数 $n / (n ? 2)$ 。
故总次数的期望为
$1+n/(n-1)+n/(n-2)+...+n = n(1/n+1/(n-1)+1/(n-2)+...+1) = n H_n$
其中 $H_n$ 表示调和级数的第n个部分和。

彩票收集问题的扩展

本文主要讨论彩票收集问题的几种扩展问题的求解算法。

每种彩票的抽取概率不再相等，而是分别为 $p_1,p_2,...,p_n]$ 。
要求收集每种彩票各c张时的抽取次数的期望。
要求收集每种彩票的张数分别为 $c_1,c_2,...,c_n]$ 。
第1种情况与第2种情况相结合。
最复杂的情况：第1种情况与第3种情况相结合。

1. 抽取概率各不相等

当每次抽取彩票时，不再以等概率抽取每种彩票，而是以给定概率 $p_1,p_2,...,p_n](p_1+p_2+...+p_n=1)$ 抽取彩票时，原解法不再有效，因为此时抽取每种彩票的概率不再相同，需要分情况进行讨论。

按集齐每种彩票至少各一张时，每种彩票第一次抽到的顺序分情况讨论：
以n=4为例：
假设顺序[1234]代表112234,1213214,…等情况，即第一个抽到彩票1，第二个是彩票2，第三个彩票3，最后一个是一张彩票4
顺序[1234]出现的概率为 $P([1234])=p_1*p_2/(1-p_1)*p_3/(1-p_1-p_2)$
此时的期望次数为 $E([1234])=1+1/(1-p_1)+1/(1-p_1-p_2)+1/(1-p_1-p_2-p_3)$
以此类推
总期望为所有顺序出现的概率*期望次数后求和
$E = P ([1234]) ? E ([1234]) + P ([1243]) ? E ([1243]) + . . . . . + P ([4321]) ? E ([4321])$
这里需要枚举4种彩票的全排列，即枚举每一种抽取顺序。
对于概率和小于1的情况（即在一次抽取种有可能抽不到彩票），只需要将每个概率除以概率之和后进行计算，然后将最后的期望除以概率之和即可得到真实的期望。
以下是一个python的求解算法代码示例，p为给定的抽取概率：

import itertools
import numpy as np
p = np.array([0.1, 0.08, 0.12, 0.15])
n = len(p)
s = sum(p)
p /= s
e = 0
for i in itertools.permutations(np.arange(n)): #全排列
    pi = ei = pt = 1
    for k in range(n-1):
        pk = p[i[k]]
        pi *= pk/pt
        pt -= pk
        ei += 1/pt
    e += pi * ei
e/s