微信红包算法的分析

最近在研究 Random Art，一种基于用户输入的随机生成艺术，对随机数这块比较感兴趣，同时微信的红包分发也是一种基于随机的思想，所以对其有了一定的研究。

1. 引子

最早的时候是看了这个问题
微信红包的随机算法是怎样实现的？
我对这方面的算法很感兴趣，正巧最近研究的方向有点偏随机数这块，所以也自己实现了一下微信的红包分发算法。

2. 算法

从上文题目中可以了解到，微信并不是一开始就预分配所有的红包金额，而是在拆时进行计算的。这样做的好处是效率高，实时性。
红包具体是怎么计算的呢？
引用别人的回答

答：随机，额度在 0.01 和(剩余平均值 2)之间。
例如：发 100 块钱，总共 10 个红包，那么平均值是 10 块钱一个，那么发出来的红包的额度在 0.01 元～20 元之间波动。
当前面 3 个红包总共被领了 40 块钱时，剩下 60 块钱，总共 7 个红包，那么这 7 个红包的额度在：0.01～（60/72）=17.14 之间。
注意：这里的算法是每被抢一个后，剩下的会再次执行上面的这样的算法（Tim 老师也觉得上述算法太复杂，不知基于什么样的考虑）。
这样算下去，会超过最开始的全部金额，因此到了最后面如果不够这么算，那么会采取如下算法：保证剩余用户能拿到最低 1 分钱即可。
如果前面的人手气不好，那么后面的余额越多，红包额度也就越多，因此实际概率一样的。

那基于这个思想，可以写出一个红包分配算法：

/**
 * 并不完美的红包算法
 */
public static double rand(double money, int people, List<Double> l) {
    if (people == 1) {
        double red = Math.round(money * 100) / 100.0;
        l.add(red);
        return 0;
    }
    Random random = new Random();
    double min = 0.01;
    double max = money / people * 2.0;
    double red = random.nextDouble() * max;
    red = red <= min ? min : red;
    red = Math.floor(red * 100) / 100.0;
    l.add(red);
    double remain = Math.round((money - red) * 100) / 100.0;
    return remain;
}

算法整体思路很简单，就在在最后一个人的时候要注意，此时不进行随机数计算，而是直接将剩余金额作为红包。

3. 第一次分析

采用上述算法，可以对用户的抢红包行为做分析。
这里的模仿行为是：
30 元的红包，10 人抢。操作 100 次。
可以得出如下结果【横轴表示第?个位置，纵轴表示红包金额】

从图中可以很轻易的看出来，越后抢的人，风险越大，同时收益也越大，有较大几率获得“手气最佳”。【方差大】
那红包面值的分布性如何呢？
【横轴表示第?个位置，纵轴表示重复 100 次，第?个位置上收益的平均值。】

可以看出，都是比较接近平均值(3 元)的。
那重复 1000 次呢？

更接近了。

可以看出，这个算法可以让大家抢到红包面额在概率上是大致均等的。

4. 不足之处

接着往下翻那个知乎问题，发现有一位同学提出了这个问题：

他接下来放了好几张他试验的截图。我这里取了一张，如果有兴趣，可以去知乎的问题里查看更多图片。

而此时，我哥在和我的在讨论中，也告诉我，确实存在某个规律，可能让最后一个抢的人占有某些微小的优势，比如，多 0.01 的之类。
例如发 6 个，总额 0.09 的包，最后一个抢的有极大概率是 0.03。

然而我之前的代码却没办法体现出这一点。
比如 10 人拆 0.11 元的包，我的结果是：

可见以上代码还存在不足之处。
于是我就有一个猜测。

微信可能不是对全金额进行随机的，可能在派发红包之前，已经对金额做了处理，比如，事先减去(红包个数*0.01)，之后在每个红包的随机值基础上加 0.01，以此来保证每个红包最小值都是 0.01。

这个猜测或许可以解开那位知友和我哥这边的疑惑。

5. 完善算法

在原先的基础上对代码进行简单的修正。

public static double rand(double money, int people, List<Double> l) {
    if (people == 1) {
        double red = Math.round(money * 100) / 100.0;
        l.add(red+0.01);
        return 0;
    }
    Random random = new Random();
    double min = 0;
    double max = money / people * 2.0;
    double red = random.nextDouble() * max;
    red = red <= min ? min : red;
    red = Math.floor(red * 100) / 100.0;
    l.add(red+0.01);
    double remain = Math.round((money - red) * 100) / 100.0;
    return remain;
}

这个算法，在第一次调用时传入 money 的值是总金额减去红包数*0.01，大概像这样
_money = _money - people * 0.01;

6. 第二次分析

1. 验证上次的不足之处

1. 10 人抢 0.11 元的包

2. 2 人抢 0.03 元的包

3. 6 人抢 0.09 的包

2. 修改后的代码会不会对已知结论造成影响

30 元的红包，10 人抢。操作 100 次
【横轴表示第?个位置，纵轴表示红包金额】

【横轴表示第?个位置，纵轴表示重复 100 次，第?个位置上收益的平均值。】

可见，结论基本上没有改变。

7. 结论

先抢后抢，金额期望都是相同的
微信的红包算法很可能是预先分配给每人 0.01 的“底额”
后抢者风险高，收益大

当我喜滋滋的将我的结论分享给我的同学时，发生了以下对话。

我："以后收到小包也别灰心啊，期望都是一样的。有个大佬发 10 块的红包给 10 个人，发了 1000 次，那最终这 10 个人能得到的钱都是和 1000 持平，不会差太多。"
同学：“问题是，大佬往往只发一次。”

不知道该哭好还是该笑好

8. 补充

上几张今天测试的图，补充一下之前的观点，发 n 个红包，总金额是(n+1)*0.01，最后一个领的一定是手气最佳。

大家也可以试试。
以上，大概可以证明，微信红包是在分配前先给每个人 0.01 的最低金额的！

微信红包算法的分析