开卡包的期望
问题描述
目前有N个卡包，K种卡牌，每次开卡包等概率的开出K种卡牌中任意一张
求N个卡包能够开出的卡牌种类期望数
开出所有种类的卡包期望数
问题1
设随机变量 X 表示 N 包卡包开出的卡牌种类数，每张卡牌未被开出的概率为 ( 1 − 1 k ) N \left(1 - \frac{1}{k}\right)^N (1−k1)N 。
根据期望线性性质， X 的期望为：
E ( X ) = k ⋅ [ 1 − ( 1 − 1 k ) N ] E(X) = k \cdot \left[1 - \left(1 - \frac{1}{k}\right)^N\right] E(X)=k⋅[1−(1−k1)N]
- 对每张卡牌定义指示变量 X i X_i Xi（开出第 i 张牌时 X i = 1 X_i = 1 Xi=1 ，否则为 0 ）。
- 单张卡牌未被开出的概率为 ( 1 − 1 k ) N ，故 E ( X i ) = 1 − ( 1 − 1 k ) N \left(1 - \frac{1}{k}\right)^N ，故 E(X_i) = 1 - \left(1 - \frac{1}{k}\right)^N (1−k1)N，故E(Xi)=1−(1−k1)N 。
- 总期望 E ( X ) = K ∗ ( 1 − ( 1 − 1 k ) N ) E(X) =K*(1 - \left(1 - \frac{1}{k}\right)^N) E(X)=K∗(1−(1−k1)N)
问题2
设 X 为收集所有 k 种卡牌所需的开包次数。将 X 分解为 k 个阶段的随机变量之和：
X = X 1 + X 2 + ⋯ + X k X = X_1 + X_2 + \cdots + X_k X=X1+X2+⋯+Xk
其中 X i X_i Xi表示从已收集 i-1 种卡牌到收集第 i 种卡牌所需的开包次数。
第 1 阶段（ X 1 ）：初始时未收集任何卡牌，每次开包必获得新卡牌，因此 X 1 = 1 第 1 阶段（ X_1 ）：初始时未收集任何卡牌，每次开包必获得新卡牌，因此 X_1 = 1 第1阶段（X1）：初始时未收集任何卡牌，每次开包必获得新卡牌，因此X1=1 。
第 i 阶段（ X i , i ≥ 2 ）：已收集 i − 1 种卡牌，剩余 k − ( i − 1 ) = k − i + 1 种新卡牌。此时每次开包获得新卡牌的概率为 p i = k − i + 1 k ，因此 X i 服从参数为 p i 的几何分布。几何分布的期望为 1 p i ，即： E [ X i ] = k k − i + 1 . 第 i 阶段（ X_i, i \geq 2 ）：已收集 i-1 种卡牌，剩余 k - (i-1) = k - i + 1 种新卡牌。此时每次开包获得新卡牌的概率为 p_i = \frac{k - i + 1}{k} ，因此 X_i 服从参数为 p_i 的几何分布。几何分布的期望为 \frac{1}{p_i} ，即： \mathbb{E}[X_i] = \frac{k}{k - i + 1}. 第i阶段（Xi,i≥2）：已收集i−1种卡牌，剩余k−(i−1)=k−i+1种新卡牌。此时每次开包获得新卡牌的概率为pi=kk−i+1，因此Xi服从参数为pi的几何分布。几何分布的期望为pi1，即：E[Xi]=k−i+1k.
根据期望的线性性质，总期望为各阶段期望之和：
E [ X ] = E [ X 1 ] + E [ X 2 ] + ⋯ + E [ X k ] . \mathbb{E}[X] = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \cdots + \mathbb{E}[X_k]. E[X]=E[X1]+E[X2]+⋯+E[Xk].
代入各阶段期望：
E [ X ] = 1 + k k − 1 + k k − 2 + ⋯ + k 1 = k ( 1 1 + 1 2 + ⋯ + 1 k ) . \mathbb{E}[X] = 1 + \frac{k}{k-1} + \frac{k}{k-2} + \cdots + \frac{k}{1} = k \left( \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{k} \right). E[X]=1+k−1k+k−2k+⋯+1k=k(11+21+⋯+k1).
这里用到了调和数 H k = 1 + 1 2 + ⋯ + 1 k H_k = 1 + \frac{1}{2} + \cdots + \frac{1}{k} Hk=1+21+⋯+k1，因此最终期望为：
E [ X ] = k ⋅ H k . \mathbb{E}[X] = k \cdot H_k. E[X]=k⋅Hk.
结论：
无论卡包种类数 n 是多少（只要每种卡包开出每张卡牌的概率均为 1/k ），收集所有 k 种卡牌的期望开包次数为：
k ( 1 + 1 2 + 1 3 + ⋯ + 1 k ) \boxed{k \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k} \right)} k(1+21+31+⋯+k1)
或用调和数表示为：
k ⋅ H k \boxed{k \cdot H_k} k⋅Hk