微信红包的随机分割算法

春节到了，又是了抢红包的时节。不过我对于这背后的数学和算法更感兴趣。

1、微信红包的数学描述

如果以分为单位，微信红包算法可以简单转为一个数学概率取样问题：需要将指定的总和$N$，随机地分为$K$个正整数，且每个数不超过指定值$L$。

也就是，我们需要在下面集合中均匀取样：

2、没有上限时的线段切割法

对于没有上限，亦即$L = \infty$时，线段切割法是一个很简单的算法。假设长度为$N$的线段，在上面随机选取$K-1$个点，这些点将线段分割成的段便是我们所需要的。

一个简单的Python实现如下：

def random_split(N, K):
    if K == 1:  return [N]

    import random
    points = random.sample(list(range(1, N)), K - 1)
    points.sort()

    splits = [points[0]]
    for idx in range(K - 2):
        splits.append(points[idx + 1] - points[idx])
    splits.append(total - points[-1])

    return splits

这个算法的准确性在于，当$L=\infty$时，原解空间(\ref{setx})与下面集合：

有一一映射关系：

这样在解空间(\ref{setx})里随机取数，就变成了在解空间(\ref{sety})里随机取数。显然后者就是线段切割法。

3、有上限时的处理方法

目前没想到什么好方法，查询文件未果。

3.1、重复取样法

一个很直接的方法是，先用没有上限的方法取样，然后抛弃突破上限的样本。这可以确保数学上的随机性。

为降低需要取样的次数，当上限太低（$L\leq 2N/K$）时，可以对问题做一个转换：

# 该函数返回一个样本结果，以及生成该样本的重复采样次数。
# N: 红包总额；K：红包个数；L：上限。
def random_split_with_limit(N, K, L):
    if K * (L + 1) < 2 * N:
        N = K * (L + 1) - N
        splits, times = random_split_with_limit(K * (L + 1) - N, K, L)
        return [L + 1 - x for x in splits], times

    times = 0
    while True:
        times += 1
        splits = random_split(N, K)
        if max(splits) <= L:
            return splits, times

这个方法的问题在于，随着红包的增加，需要重复取样的次数会指数级别的增加。比如 10 个红包大约 10 次取样就能生成一个有效样本，但 20 个红包需要 200 到 300 次，而 30 个红包需要 5000 次左右！

4、真实的微信红包算法

根据网上流传的一份微信红包的架构设计简介，微信用的算法是所谓的二倍平均余额法：

分配：红包里的金额怎么算？为什么出现各个红包金额相差很大？

答：随机，额度在 0.01 和(剩余平均值*2)之间。

例如：发 100 块钱，总共 10 个红包，那么平均值是 10 块钱一个，那么发出来的红包的额度在 0.01 元～20 元之间波动。

当前面 3 个红包总共被领了 40 块钱时，剩下 60 块钱，总共 7 个红包，那么这 7 个红包的额度在： 0.01～（ 60/7*2 ）=17.14 之间。

注意：这里的算法是每被抢一个后，剩下的会再次执行上面的这样的算法。

这种方法可以确保所有人的期望值都相当，但并没有保证解空间里的均匀性。最直观的，第一个人的红包额不会超过平均数的两倍。

在微信群抢红包先后顺序决定手气吗？里，作者还用数学证明了，在上述的算法下，后抢的人方差更大。作者用计算机模拟了千万级别的红包数量，得到下面的抢红包策略：

风险偏好：如果你想要稳稳当当地抢，就先抢；如果你喜欢抢到超级大红包，就后抢。

「手气最佳发红包」游戏：发的红包数少（ 6 个以下）就后抢，红包多（ 6 到 15 个）就中间抢，很多（ 15 个以上）就先抢！

Q. E. D.