微信红包的随机分割算法

作者: , 共 2380 字

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

1. 微信红包的数学描述

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

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

$$ \left\{ x_1, x_2, \cdots, x_K \ \Big| \ x_i \in [1, L], \ \sum_{i=1}^K x_i = N \right\} \label{setx} $$

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})与下面集合:

$$ \left\{ y_1, y_2, \cdots, y_{K-1} \ \Big| \ 0 < y_1 < y_2 < \cdots < y_{K-1} < T \right\} \label{sety} $$

有一一映射关系:

$$ (x_1, x_2, \cdots, x_K) \leftrightarrow (x_1, x_1 + x_2, x_1 + x_2 + x_3, \cdots, x_1 + x_2 + \cdots, x_{K-1}) $$

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

3. 有上限时的处理方法

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

3.1. 重复取样法

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

为降低需要取样的次数,当上限太低(\(L\leq 2N/K\))时,可以对问题做一个转换:

$$ \begin{array}{rcl} x_i & \rightarrow & L + 1 - x_i \\ (N, K, L) & \rightarrow & (K * (L + 1) - N, K, L) \end{array} $$
# 该函数返回一个样本结果,以及生成该样本的重复采样次数。
# 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.

类似文章:
用手机上的微信读书快半年了。App 上显示的累计读书时间为 308 个小时。我越来越喜欢这个产品,给大家推荐推荐。
这是一个老问题,最近有老同学问起,就在这里提一下吧。
今天刚看了《疯狂的外星人》。电影片头说原著是《乡村教师》。但整个电影,除了出现外星人之外,和《乡村教师》一点关系都没有。