几种奖池抽取期望计算
1. 不放回抽取
从一套充分洗匀的扑克中不放回地一直抽，直到抽到两张大小王都抽到，一共抽了多少张的期望值？
先说结论：
一般地，从 $n$ 张牌中不放回地抽取特定 $k$ 张，期望抽取次数是 $Exp = k \cdot (n+1)\ /\ (k+1)$
然后说证明：
首先，在充分洗匀的情况下，从牌堆顶部抽取和从牌堆中间任意位置抽取是等价的，所以可以假设牌堆是从左到右的展开一列，抽取动作等效于从左开始逐张提取卡片，直到所有目标牌都抽取到手里。想像 k 张目标牌已经排成一列，其顺序无关紧要因为最终都会被清空。这 k 张牌相隔包括左右外侧共产生 k+1 个空隙：
然后将 n-k 张非目标牌随机插入这 k+1 个空隙中，每个空隙插入的概率相等，所以期望张数是 $\frac{n-k}{k+1}$。
最后考察清点过程，显然最右侧外侧可以抛弃，所以需要抽取的期望张数是 $n - \frac{n-k}{k+1} = \frac{k \times (n+1)}{k+1}$。得证。
这类抽奖励在各类游戏中都有，其特点是：
- 奖池有限
- 不会抽到重复的奖品
- 通常玩家心仪的是奖池中的几个特定奖品，其它是无关紧要的
有些游戏会添加『升星级』的设置，某个抽卡人物 A 多次抽到后，会升级为 A+，A++ 等。这种情况完全可以视为若干个独立的 A 在奖池中，需要全部抽齐，计算时调整 n 与 k 的值即可。
—— 算下来『全部抽齐』确实是成本很高的目标。
2. 放回抽取
在数量为 n 的奖池中进行抽取，抽取结果是可重复的（抽完放回），抽完所有 n 件奖品的期望抽取次数是多少？
$$Exp= n \cdot (1 + 1/2 + 1/3 + \cdots + 1/n) = n \cdot \sum _{i=1}^n \frac{1}{i} = n \cdot H_n $$
$H_n$ 就是调和级数。
证明，从后往前考察抽取过程：
- 如果当前只剩最后一件奖品没抽到，则从 n 件奖品中抽取特定一件的几率是 1/n，期望抽取次数是 n。
- 如果剩最后两件奖品没抽到，只要从 n 件奖励中抽到这两件的任意一件，就会进入上一条的『只剩一件』状态。抽到这两件奖励之一的几率是 2/n，期望抽取次数是 n/2。
- 每抽到一件新的就会进入下一个状态。而在任意某个状态时，当前对应的期望抽取次数是总数 / 剩余新奖品数。
- 因此，总的期望抽取次数是所有状态的期望抽取次数之和。
调和级数是发散的，可以用 Excel 等工具计算期望值，也可以用近似公式 $H_n \approx \ln n + C + 1/2n$ 算。这里的 $C$ 就是欧拉常数，约为 0.5772156649。
进一步的，如果不需要抽完，而只是抽取其中的特定 k 件奖品，仍可以从最后一件倒数推算，其期望抽取次数是：
$$Exp = \frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{k-1} + \frac{n}{k} = n \cdot H_k$$
3. 放回抽取，不同概率
在各类游戏中，奖励物品往往有不同的『品质』等级，以及不同的出现概率。可以简单理解为
奖池分为 $m$ 个小奖池，每个小奖池进入概率分别为 $p_1, p_2, \cdots, p_m$，奖品数量分别为 $n_1, n_2, \cdots, n_m$。获得整个奖池全部奖励的期望抽取次数 $N$ 是多少？
对于每个小奖池，期望抽取次数是 $n_i \cdot H_{n_i}$，再除以小奖池本身的概率 $p_i$，即得 $N_i=n_i\cdot H_{n_i} \ /\ p_i$。但对于整个奖池，总期望抽取次数 $N$ 不是所有小奖池的次数之和，而是它们之中的最大值。因为当有 $n_i = p_i\cdot N$ 的抽取次数落到 $i$ 号小奖池时，也有对应的 $(1-p_i) N$ 溢出到其它小奖池。最大值保证溢出部分覆盖其它小奖池的期望抽取次数。随意举例如下：
| 品质 | 数量 | 概率 | 期望有效抽取次数 | 对应期望抽取总次数 | 溢出次数 |
|---|---|---|---|---|---|
| 橙色传说 | 10 | 0.01 | $10\cdot H_{10} \approx 29.29$ | $2928.97$ | $10\cdot H_{10} \ /\ 0.01 \cdot 0.99 \approx 2899.68$ |
| 紫色史诗 | 20 | 0.09 | $20\cdot H_{20} \approx 71.95$ | $799.50$ | $20\cdot H_{20} \ /\ 0.09 \cdot 0.91 \approx 727.54$ |
| 蓝色稀有 | 50 | 0.3 | $50\cdot H_{50} \approx 224.96$ | $749.86$ | $50\cdot H_{50} \ /\ 0.3 \cdot 0.7 \approx 524.91 $ |
| 白色普通 | 200 | 0.6 | $200\cdot H_{200} \approx 1175.6$ | $1959.34$ | $200\cdot H_{200} \ /\ 0.6 \cdot 0.4 \approx 783.74$ |
总抽取次数 $N$ 会以 $0.01:0.09:0.3:0.6$ 的比例分配到四种品质中。观察表格，橙色传说所需的抽取次数最多，且溢出部分按比例仍可以覆盖其它所有奖池的有效抽取次数，也就是说抽到 2929 次时，期望可以让全部 10 件橙色传说抽取到手里。此时溢出的 2899 次已经完全覆盖了其它三种品质的有效期望抽取次数。所以 $$Exp = Max\left(n_i \cdot H_{n_i} \ /\ p_i\right)$$
进一步考虑发现，只要每个小奖池的期望有效抽取次数和设定的小奖池进入概率比例不一致，则一定会有一个小奖池的期望抽取次数最大。如果正好一致，也意味着每个都是最大值。这个结论是普适的。
4. 放回抽取，反还比例
在某些游戏中，抽取到重复奖品时，会通过『碎片』等给予一定的返还比例，若干个碎片可以合成需要的道具。先考虑单个奖池的情况：
假设奖池中有 n 件奖品，抽取概率相同。抽到重复奖品时，返还比例是 r(r<1)，那么抽取次数的期望值是多少？
没有傻逼会去合成已经存在的道具，所以返还可以视为抽取了 r 个新道具。同时由于 r <1，重复的价值仍是小于不重复的，因此在确保碎片可以合成奖池所有剩余奖品前，应当不合成任何奖励减少重复，使得整体收益最大化。再次从后往前考察抽取过程：
- 如果只差最后一件奖品没抽到，那么我仍需要从 n 件奖励中抽取，抽到这件奖励的几率是 1/n，期望抽取次数是 n。其中 1 次是有效抽取，n-1 次是重复抽取，返还 r(n-1) 碎片。
- 如果剩最后两件奖品没抽到，只要从 n 件奖励中抽到这两件的任意一件，就会进入『最后一件』状态，抽到这两件奖励的几率是 2/n，期望抽取次数是 n/2。其中 1 次是有效抽取，n/2-1 次是重复抽取，返还 r(n/2-1) 碎片。
- 以此类推，在 n 奖池中抽取到 t 个奖品时，对应的总抽取碎片为：
\begin{align*}
R(t) &= r\cdot(n-1) + r\cdot(\frac{n}{2}-1) + \cdots + r\cdot(\frac{n}{t-1}-1) +r\cdot(\frac{n}{t}-1) \\
&= r \cdot \sum_{i=1}^t \left( \frac{n}{i} - 1 \right) \\
&= r \cdot \left( nH_t - t \right) \\
\end{align*}
在某个节点 $t=k$ 时，获得的碎片就已经足够合成了所有剩余的奖品，即 $R(k) \geq n-k$。因为 $R$ 单调递增，$k$ 必然存在，此时对应的期望抽取次数即是 $n \cdot H_k$。$k$ 的通式求解超出了我的能力，但使用 Excel 或编程求解在有限的 n 范围内仍是方便的。
5. 放回抽取，反还比例，多个奖池
假设还是 $m$ 个分概率的小奖池，但返还的碎片是通用的，那么全部奖品的总抽取次数期望值是多少？
这里需要再添加一个参数，每个奖池的相对价格是不同的，设为 $c_i$。在 r 相同同，高价值奖池重复物品返回的碎片绝对数量更多。需要通过调整各奖池的 $c_i \cdot R(t)$，使各奖池的每抽价值归一化，后续就化为多个小奖池取最大值的已知问题了。即：
- 设总抽取次数为 $N$，则对于每个小奖池会分得 $k_i = N \cdot p_i$ 次。
- 各小奖池 $i$ 各抽取 $k_i$ 次，得到 $t_i$ 个奖品，满足 $n_i \cdot H_{t_i} \leq k_i$，虽然计算期望可以取等号，但调和级数无法依此简化计算。
- 此时产生的碎片为 $r\cdot(k_i-t_i)$ 即 $R(t_i)$，剩余未抽取的奖品数量为 $n_i - t_i$。
- 当总碎片数量大于等于剩余奖品所须数量时，N 得解。整理得到：
\begin{array}{l}
{\left\{
\begin{aligned}
& k_i =N \times p_i, \\
&n_i \cdot H_{t_i} \leq k_i, \\
&\sum_{i=1}^m [R(t_i) \cdot c_i] \geq \sum_{i=1}^m [(n_i-t_i)\cdot c_i] \\
\end{aligned}
\right. } \\
\\
\Rightarrow \large{ N = Max\left( k_i / p_i \right) }
\end{array}
- $c_i$ 为不同奖池间的价值权重，与碎片兑换各级别奖品的相对数量有关，与 $r$ 无关。
- $p_i c_i$ 为定义数据，调和级数只有离散解，每个小奖池计算的全局期望 $N_i$ 仍可能不一致。
6. 概率提升
在某些游戏中，当抽取未能获得奖励时，会提升下一次抽取的概率，直到抽取到奖励后重置概率。则真实概率是多少？
先从一个简单例子入手：
- 事件 A 的发生概率是 1/2，事件 B 发生概率为另 1/2，当 A 未发生时，下一次发生事件 A 的概率提到 100%。那么在多次重复中，A 事件的真实概率是多少？
直觉可能会认为是 75%。但进一步思考发现，事件 B 的下一轮必定跟随事件 A，而事件 A 的下一轮 A 与 B 各有 50% 几率发生。将多轮过程展开后会发现这是 $A:BA=1:1$ 的序列。因此单看事件 A 发生的真实概率为 2/3。
推广到 A 事件 1/3 的情况，可以得到：
| 组合 | 概率 |
|---|---|
| A | $1/3$ |
| BA | $2/3 \times 2/3 = 4/9$ |
| BBA | $2/3 \times 1/3 \times 1 = 2/9$ |
在足够长的序列中，三者以 $A:BA:BBA=\frac{1}{3}:\frac{4}{9}: \frac{2}{9}$ 的比例出现，序列总长度为 $L = \frac{1}{3}\cdot n + \frac{4}{9}\cdot 2n+ \frac{2}{9}\cdot 3n$，其中 A 在每个组合中都出现一次，因此 A 的真实概率是 $\frac{n}{L} = \frac{9}{17}$。
由此观察到一般规律，对于初始概率为 $a$，提升步长为 $p$，达到 100% 时的步数为 $k$，即 $a+kp\geq 1 \Rightarrow k\geq(1-a)/p$ 时，真实概率 $P(A)$ 是以下式子的解：
\begin{align*}
L &= p(A)+2\cdot p(BA)+3\cdot p(BBA)+ \cdots + k \cdot p(\underbrace{BBB \ldots B}_{k-1}A) + (k+1) \cdot p(\underbrace{BBB \ldots B}_{k}A) \\
&= a + 2(1-a)(a+p) + 3(1-a)^2(a+2p) + \cdots + k(1-a)^{k-1}(a+(k-1)p) +(k+1)(1-a)^k\cdot1 \\
&= \sum_{i=1}^k \left[i\cdot(1-a)^{i-1}(a+(i-1)\cdot p) \right] + (k+1)(1-a)^k \cdot 1 \\
P(A) &= k/L
\end{align*}
因为 $k$ 是有限的，所以式子不涉及无穷级数，但是计算仍然不方便，需要借助工具。
在 $a = p = 1/n$ 的特殊情况下，可以进一步简化为：
\begin{align*}
L &= \frac{1}{n} + \frac{n-1}{n}\cdot\frac{2}{n}\cdot2 + \frac{n-1}{n}\cdot\frac{n-2}{n}\cdot\frac{3}{n}\cdot3 + \cdots + \frac{n-1}{n}\cdot\frac{n-2}{n}\cdots\frac{1}{n}\cdot\frac{n}{n}\cdot n \\
& = \sum_{i=1}^n \left[\frac{i^2}{n^i} \cdot \prod_{j=1}^{i-1} (n-j) \right] \\
Q(n) &= 1/L \\
\end{align*}
手动计算几个较小值：
\begin{align*}
Q(2) &= \frac{1}{ \frac{1}{2} + \frac{2^2}{2^2}(2-1) } = \frac{2}{3} \\
Q(3) &= \frac{1}{ \frac{1}{3} + \frac{2^2}{3^2}(3-1) + \frac{3^2}{3^3}(3-1)(3-2) } = \frac{9}{17} \approx 0.5294 \\
Q(4) &= \frac{1}{ \frac{1}{4} + \frac{2^2}{4^2}(4-1) + \frac{3^2}{4^3}(4-1)(4-2) + \frac{4^2}{4^4}(4-1)(4-2)(4-3) } = 32/71\approx 0.4507 \\
Q(5) &= \frac{1}{ \frac{1}{5} + \frac{2^2}{5^2}\cdot4 + \frac{3^2}{5^3}\cdot4\cdot3 + \frac{4^2}{5^4}\cdot4\cdot3\cdot2 + \frac{5^2}{5^5}\cdot4\cdot3\cdot2\cdot1 } = 625/1569\approx 0.3983 \\
Q(6) &= \frac{1}{ \frac{1}{6} + \frac{2^2}{6^2}\cdot5 + \frac{3^2}{6^3}\cdot5\cdot4 + \frac{4^2}{6^4}\cdot5\cdot4\cdot3 + \frac{5^2}{6^5}\cdot5\cdot4\cdot3\cdot2 + \frac{6^2}{6^6}\cdot5\cdot4\cdot3\cdot2\cdot1 } = 324/899 \approx 0.3604 \\
Q(7) &= 117649/355081 \approx 0.3313, \\
Q(8) &= 131072/425331 \approx 0.3082, \\
Q(9) &= 4782969/16541017 \approx 0.2892, \\
Q(10)&= 1562500/5719087 \approx 0.2732,
\end{align*}
来个大的：
\begin{align*}
Q(100)&=\frac{\tiny{10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}}{\tiny{129277986730885202106151856642773382549665465071825090615034369359178917814747670780594211447306244001059786961886915926297133393516168977984471526892507817}} \\
&\approx 0.0819
\end{align*}
再来个图：
-graph.png)
7. 保底
在某些游戏中，抽取到一定次数后，会有保底机制，即抽取次数超过一定值后，会直接给予某个奖励。
如果只是每 n 次固定给予一个奖励，就是简单的在原期望上加 1/n：$Exp_{(e)} = Exp + 1/n$。
但实际上，在引入保底机制的情况下，讨论概率和期望并没有意义，它已经被『规则』所取代了。当游戏运营方明确表示为概率添加规则时，这个抽奖系统本身就变得不可信了。带保底的抽奖系统一定会和你帐号中的某些变量挂钩，你的抽取与获奖可能性就并非是由某个全系统一致的随机发生器决定，而更可能是与你的帐号历史、充值、活跃度等相关。这个系统运行的不再是概率，而是对你容忍底线的反复试探。