微信红包算法的分析

微信红包算法的分析

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

1. 引子

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

2. 算法

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

答:随机,额度在 0.01 和 ( 剩余平均值2) 之间。
例如:发 100 块钱,总共 10 个红包,那么平均值是 10 块钱一个,那么发出来的红包的额度在 0.01 元~20 元之间波动。
当前面 3 个红包总共被领了 40 块钱时,剩下 60 块钱,总共 7 个红包,那么这 7 个红包的额度在:0.01~(60/7
2)=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 次。
可以得出如下结果【横轴表示第? 个位置,纵轴表示红包金额】
result1
从图中可以很轻易的看出来,越后抢的人,风险越大,同时收益也越大,有较大几率获得“手气最佳”。【方差大】
那红包面值的分布性如何呢?
【横轴表示第? 个位置,纵轴表示重复 100 次,第? 个位置上收益的平均值。】
result2
可以看出,都是比较接近平均值 (3 元) 的。
那重复 1000 次呢?
result3
更接近了。

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

4. 不足之处

接着往下翻那个知乎问题,发现有一位同学提出了这个问题:
q1
他接下来放了好几张他试验的截图。我这里取了一张,如果有兴趣,可以去知乎的问题里查看更多图片。
q2

而此时,我哥在和我的在讨论中,也告诉我,确实存在某个规律,可能让最后一个抢的人占有某些微小的优势,比如,多 0.01 的之类。
例如发 6 个,总额 0.09 的包,最后一个抢的有极大概率是 0.03。
q3
然而我之前的代码却没办法体现出这一点。
比如 10 人拆 0.11 元的包,我的结果是:
result4
可见以上代码还存在不足之处。
于是我就有一个猜测。

微信可能不是对全金额进行随机的,可能在派发红包之前,已经对金额做了处理,比如,事先减去 (红包个数 *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 元的包

result5

2. 2 人抢 0.03 元的包

result7

3. 6 人抢 0.09 的包

result6

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

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

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

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

7. 结论

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

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

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

不知道该哭好还是该笑好

8. 补充

上几张今天测试的图,补充一下之前的观点,发 n 个红包,总金额是 (n+1)*0.01,最后一个领的一定是手气最佳。
add1
add2
大家也可以试试。
以上,大概可以证明,微信红包是在分配前先给每个人 0.01 的最低金额的!