微信红包的随机分割算法

作者:

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

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.

类似文章:
编程 » C++, 算法
一个短小、高效的 C++函数,用来判断指定日期是星期几:
2007 年,我们 讨论过一个算法问题 , perfect shuffle ,据称是个微软面试题:
注: 这个问题来自 China Theory Week 2008 的 Open Problems Session。
最大回撤是一个重要的风险指标。对于对冲基金和数量化策略交易,这个指标比波动率还重要。
Google 新推出了 图片搜索 ,可直接上传图片(或者用图片链接)搜索网络上的相似图片, 例子 。估计还没多少人意识到,这玩意儿是人肉搜索的大杀器,以后大家还是少上传私人照片到公开网络。
这是一个老问题,最近有老同学问起,就在这里提一下吧。
今天刚看了《疯狂的外星人》。电影片头说原著是《乡村教师》。但整个电影,除了出现外星人之外,和《乡村教师》一点关系都没有。