万能的考拉
今天你考拉没?

科普 | 微信红包的随机算法是怎样实现的?

在你绝不错过几百亿的同时,有没有考虑这样一个问题:为啥小明可以随机到88元,而我却只有0.8元呢?为啥“手气最佳”的人总不是我!为什么!为!什!么!所以主页君为你们专门留意了这个问题,并把这份细心又复杂的答案耐心传送给大家。有心的朋友可以继续探讨此问题,能够抛砖引玉,那是最好不过了。

著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。
作者:张景舒
链接:https://www.zhihu.com/question/22625187/answer/85431684
来源:知乎

今年过年我花了120元做了一组实验(其中60元由老婆的红包赞助,特此鸣谢 ^-^ ),获取了两个样本。两个样本的大小均为60人。

经过对样本的分析,我的结论是:获取的钱数有可能符合截尾正态分布;但我的两个样本结果显示,后抽取的人未必获得更多的钱。

很有可能腾讯在一个钱包上传时就已经用算法将红包分成了给定份数,接下来抽取人去抽取钱包的时候只是按照时间顺序把给定份数的钱包给抽取人罢了。

补充一点:假设陈鹏先生的算法是正确的(亦即此算法确实是微信红包的算法),那么先抽取者与后抽取者获得红包大小的期望值是相同的,但是标准差不同。根据个人的风险偏好的结构(risk preference structure)不同,风险回避(risk-averse)的抽取者应该尽量先抽,而风险偏爱(risk-seeking)的抽取者应该尽量后抽。 【陈鹏先生的算法是否可信以及整体到底符合何种分布都有待于更多的样本进行检验。目前我没有找到反例】

以下为验证部分。

首先,我来讨论一下为什么要采用截尾正态分布。首先介绍一种更加直接的方法(我有一些朋友也这样猜测):如果我有50元,要发给25人。那么我用连续均匀分布随机产生24个位于0到50之间的数字。这24个数字将整个0-50的区间划分为25份,分别分给这25个人。但事实并不是这样的。学过序列统计的人应该知道,由于这24个点是连续均匀分布产生的,因此他们的序列统计量也是连续均匀分布产生的,因此他们之间的间隔的分布是指数分布的。具体证明从略,可参照John Rice 2007。

若是没有序列统计的背景,我们也可以跑一个模拟。我有60元钱,按照上述数据产生机理随机分成60份(因此人均1元左右),然后如是操作10000次,对数据采取聚集后的归一化处理。由于中心极限定理(Central Limit Theorem),该分布反应整体分布(Population Distribution)。画出柱形图如下:
可见是符合指数分布的。

这种产生机理不好的地方在于:大多数人得到的钱非常少,而极少数人得到的钱却非常多,因此可能有一个公平性的问题,而这可能会对抽取人的积极性产生影响。截尾正态分布能够更好地避免这样的问题,因为更多人的红包大小会聚集在平均值附近,而且由于尾部更快的衰减,因此获得特别大的红包的概率也会相应减小,有助于增加公平性与参与的积极性。这一点佐证了土豆的观点,尽管具体截尾的方位可能需要获取更多的数据才有可能有一个准确的预测。

以下是我的两个样本的柱形图:


大家可以比照我的柱形图与上面指数分布柱形图。注意到:
1.更多的人获得的红包在均值附近;
2.获取大于2.5元的红包的概率几乎为零(事实上,第一个钱包的最高值是2.06,第二个钱包的最高值是2.10。然而假设是指数分布的(或者说均匀连续分布的数据产生机理),那么在每个60元红包中都会有一定量的抽取者抽到大于3甚至大于4元的红包–这点我通过模拟也确认了。

我进一步对正态假设做了检验,如下为样本1,样本2的分位数图(Q-Q Plot)
如果完全符合正态分布,那么所有点应该都大致在对角线附近。事实并非完全如此。可见两个样本在一定程度符合正态分布假设,但在两头有一定的异常值。

原因有二,一者样本偏小,大数定理不能完全进来,容易有异常值。二者样本是截尾正态分布,所以图和完全正态分布可能有出入。

接下去我讨论一下获取钱包大小和抢钱包先后的关系。我的结论是,红包大小和抢红包先后没有统计意义上的关联。

如下是我的两个样本的红包大小数量,我把他们按照时间顺序进行了排序,因此越靠右的人代表越后抢红包的人。

如图可见,其实先抢钱包还是后抢钱包对钱包大小的影响未必有很大的影响。

事实上,我的两个样本中,抢到的钱数甚至是随着时间推移逐渐减少的,尽管减少的量非常非常小。因此楼上土豆举的例子中向上走的趋势可能是样本特性,不具有普适性。当然了,我也只有两个样本,更进一步的结论或许有待于更多人搜集并贡献钱包的数据。

事实上,如果我们整合第一个结论,腾讯这样的设计是逻辑自洽的。在第一个结论中,我们谈到了截尾分布相比指数分布的优越性在于其公平性。因此,腾讯选择用截尾分布表明了其对公平性的重视。那么,试想这样一个特意选取产生方式更加复杂的截尾分布增加公平性的企业,为什么要让后抢红包的人获得更大的红包呢?这似乎看起来有些自相矛盾。

综上所述,我的两个主要结论如下:

1)红包大小服从截尾正态分布,其好处是减少抽取红包大小分布的方差。
让更多的人抽取的红包在均值附近,同时仍给一小部分人抽取大红包的机会,总体来说增加了红包抽取人的积极性和游戏的公平性;

2)抽取红包大小与抽取红包先后无相关性。
一种可能的红包产生机制是:当发红包者<准备红包>的时候,程序自动依照截尾分布产生了相应大小,相应个数的红包,然后随机发给抽取红包的人。同样,这样的一个随机过程有助于增加游戏的公平性,也减少了红包抽取人投机操作(亦即譬如故意等钱包半空的时候再抽取)的动机。我在知乎上看到一位朋友谈到她的腾讯工作的朋友确认了红包产生是在<准备红包>时就完成了的,因此也在一定程度上增强了我的这种推测的可信度。

我看到知友陈鹏先生贴上了微信的算法。我用陈先生的算法研究了一下抢红包的人抢到红包大小和抢红包先后的关系,想与大家分享一下研究结果。

陈鹏先生的代码大致意思是这样的:假设有100元钱,分给十个人。那么第一个人获得红包大小怎么计算呢?100/10 = 10元。这是期望值。从0.01到20的区间中(其中20=10乘以2)随机抽取一个数,就是第一个人获得红包的大小。假设第一个人获得了15元,那么剩下的85元平均分给9个人,这九个人平均获得红包大小为9.4元,那么第二个人的红包大小均匀分布于0.01元到18.88元的区间中,依次类推。算法保证最后一个人至少抽到0.01元。

不难看出,每个人获得的红包大小的期望值仍然是10元。但是分布就不同了,因为之前抽取的人结果的好坏会影响到后抽取的人的结果。假设陈鹏先生贴的算法是可靠的,亦即微信确实用这样的算法来分配红包,我简单模拟了一下第一个抽取的人,第五个抽取的人,以及最后一个抽取的人(第十人)的红包大小的分布如下:
如图显见,对于第一个抽取红包的人,抽取红包大小服从均匀分布,但越到后面的抽取者抽取红包大小的分布就越不均匀。越到后面的抽取者越有可能抽到小的红包,但也有可能抽到一个数值相当大的红包。理论上讲,加入前九个人运气都很差并都只抽到0.01,最后一个人抽取红包的数额可能接近100。当然,均匀分布下这类情况出现的可能性几乎为零,经过我反复验证,100,000次中都不会出现一次。我同时附上抽取红包的期望值大小以及标准差大小的表格。
简单地说,结论就是:假设陈鹏先生贴的算法是可靠的,那么风险规避(risk-averse)的红包抽取人应该尽量抢先抽取,而风险偏爱(risk-seeking)的红包抽取人应该尽量后抽取(而且越往后似乎标准差增速也越大),因为后抽者取有可能抽到先抽取者不可能抽到的大红包,尽管抽到小红包的概率也会相应增大。Most of the things of this world are about trade-off, and there is just no such thing as a free lunch.

最后附上我发的两个红包所获取的原始数据,这样有兴趣的研究猿可以在我的基础上做进一步调查与研究。祝大家猴年吉祥,万事胜意!

结论

反正小编是看不懂上面写的。。。。。。

低调的发布一个二维码 … …

qrcode_for_gh_ec00dbc1dfca_344

news_副本

 

未经允许不得转载:万能的考拉 » 科普 | 微信红包的随机算法是怎样实现的?

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

今日考拉 万能的考拉

联系我们商业合作