抽奖游戏中额外权重的优势
某公司年会举办抽奖活动，共有 \(n\) 名员工参加，共有 \(m\) 件奖品。员工当中，有 \(k\) 人获得了额外的中奖权重：
- 抽奖前，拥有额外中奖权重的员工，会将自己的一个“分身”加入抽奖参与名单内。
- 对每件奖品抽奖时，抽奖程序从未中奖的参与名单中均匀随机选取一位，选取到自身或自身的“分身”均算作同一员工中奖。如果拥有额外的中奖权重的员工中奖，那么参与名单中会同时移除其本身和其“分身”。
求拥有额外的中奖权重的员工的中奖概率。
精确解
为简便叙述，我们称“拥有额外的中奖权重的员工”为 VIP 员工。
考虑动态规划，状态为三元组 \((n, m, k)\)：设当未中奖员工数为 \(n\)，剩余奖品数为 \(m\)，未中奖的 VIP 员工数为 \(k\) 时，某 VIP 员工此时的中奖概率为 \(p_{n, m, k}\)。根据接下来的单次抽奖，所有可能的转移方式如下：
- 接下来的奖品，抽到了该 VIP 员工，概率为 \(\frac{2}{n+k}\)
- 接下来的奖品，抽到了其他 VIP 员工，概率为 \(\frac{2k-2}{n+k}\)，状态转移到 \((n-1, m-1, k-1)\)
- 接下来的奖品，抽到了普通员工，概率为 \(\frac{n-k}{n+k}\)，状态转移到 \((n-1, m-1, k)\)
故状态转移方程为
\[ p_{n,m,k} = \frac{2}{n+k} + \frac{2k-2}{n+k} p_{n-1, m-1, k-1} + \frac{n-k}{n+k} p_{n-1, m-1, k} \]
边界条件为
\[ p_{n, 0, k} = p_{n, m, 0} = 0, \\ p_{n, m, n} = \frac{m}{n}. \]
实际计算时，观察到状态转移方程中 \(n\) 与 \(m\) 的差值始终恒定，因此可以减少一个复杂度维度，时间复杂度为 \(O(mk)\)。
近似解
这里使用一个近似。我们允许 VIP 员工在抽奖时，其自身或自身的“分身”同时中奖，但我们同时认为该中奖概率可忽略不计。这在 \(m \ll n\) 且 \(k \ll n\) 时是合理的近似。
普通员工的中奖概率为
\[ p_0 = \frac{\binom{n+k-1}{m-1}}{\binom{n+k}{m}} = \frac{m}{n+k}. \]
对 VIP 员工，其中奖概率为
\[ \begin{aligned} p_1 = 1 - \frac{\binom{n+k-2}{m}}{\binom{n+k}{m}} &= 1 - \frac{(n + k - m)(n + k - m - 1)}{(n + k)(n + k - 1)} \\ & \approx 1 - \frac{(n+k-m)^2}{(n+k)^2} \\ &= \frac{m}{n+k} \left(2 - \frac{m}{n+k} \right). \end{aligned} \]
可见，拥有额外的中奖权重，近似相当于为普通中奖概率乘上系数 \(2 - \frac{m}{n+k}\)。可以证明，当 \(\frac{m}{n+k} = 1/2\) 时，该中奖概率与普通中奖概率的差值最大，为 $ p_1 - p_0 = $。
对于一组数据 \(n=100, m = 30, k = 10\)，有 \(p_0 \approx 0.27, p_1 \approx 0.47\)，提升幅度不小。
补充
若这 \(k\) 人 VIP 能够获得两个“分身”，则可以用同样方法近似得到
\[ p_2 = \left (\frac{m}{n+2k} \right)^3 - 3 \left (\frac{m}{n+2k} \right)^2 + 3 \left (\frac{m}{n+2k} \right) \]
此时 VIP 具有更大优势。当 \(n=100, m = 30, k = 1\) 时，\(p_2 \approx 0.65\)。