2

微信红包的随机分割算法

 3 years ago
source link: https://zhiqiang.org/cs/random-split-algorithm.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

1. 微信红包的数学描述

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

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

{x1,x2,⋯,xK ∣∣ xi∈[1,L], K∑i=1xi=N}(1)(1){x1,x2,⋯,xK|xi∈[1,L],∑i=1Kxi=N}

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

对于没有上限，亦即L=∞L=∞时，线段切割法是一个很简单的算法。假设长度为NN的线段，在上面随机选取K−1K−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=∞L=∞时，原解空间(11)与下面集合：

{y1,y2,⋯,yK−1 ∣∣ 0<y1<y2<⋯<yK−1<T}(2)(2){y1,y2,⋯,yK−1|0<y1<y2<⋯<yK−1<T}

有一一映射关系：

(x1,x2,⋯,xK)↔(x1,x1+x2,x1+x2+x3,⋯,x1+x2+⋯,xK−1)(3)(3)(x1,x2,⋯,xK)↔(x1,x1+x2,x1+x2+x3,⋯,x1+x2+⋯,xK−1)

这样在解空间(11)里随机取数，就变成了在解空间(22)里随机取数。显然后者就是线段切割法。

3. 有上限时的处理方法

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

3.1. 重复取样法

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

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

xi→L+1−xi(N,K,L)→(K∗(L+1)−N,K,L)(4)(4)xi→L+1−xi(N,K,L)→(K∗(L+1)−N,K,L)
# 该函数返回一个样本结果，以及生成该样本的重复采样次数。
# 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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK