思路

「随机」可以通过随机取值实现,而「公平」说白了就是让每个人取值的期望相同。为了实现期望相同,我们可以有不同的思路去解。

以下给出几种解法与示例代码(Python3),预备代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np

class RedEnvelope(object):
    def __init__(self, money, size):
        self.remain_money = money
        self.remain_size = size

def round_money(money):
    return np.round(money * 100) / 100

def get_random_money(red_envelope):
    raise NotImplementedError

def test(money=100, size=10, num_tests=10000):
    rets = [[] for _ in range(size)]
    for _ in range(num_tests):
        red_envelope = RedEnvelope(money, size)
        for i in range(size):
            rets[i].append(get_random_money(red_envelope))

    print(f'num,    mean,    std')
    for i in range(size):
        print(f'{i:3d}, {np.mean(rets[i]):7.4f}, {np.std(rets[i]):6.4f}')

解法一:保证每次抽取公平(期望为均值)

(据 陈鹏 提供的 Java 代码修改,据说是真实的微信的算法)

为了保证每一次抽红包的「公平」,那么我们只需要保证每次抽红包的时候,拿到的钱的期望是剩余价值除以人数得到的均值。这样一来每次抽的时候,所有人的期望都是一样的,也就保证了每一次抽红包都是公平的。但是这样有个问题,后取的人由于受到先取的人抽到的红包数额的影响(前面的人抽到的红包太小或太大),方差会更大,换句话说,就是「先取的人风险小,后取的人风险大」。

代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def get_random_money(red_envelope):
    red = red_envelope

    if red.remain_size == 1:
        red.remain_size -= 1
        return round_money(red.remain_money)

    # Range
    min_ = 0.01
    max_ = red.remain_money / red.remain_size * 2;

    # Random
    money = max_ * np.random.rand()
    if money < min_:
        money = min_
    money = round_money(money);

    # Return
    red.remain_size -= 1;
    red.remain_money -= money;
    return money

测试结果:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
num,    mean,    std
  0,  9.9400, 5.8220
  1, 10.0404, 5.7862
  2,  9.9271, 5.8735
  3, 10.0769, 5.8989
  4, 10.0780, 6.0159
  5, 10.0661, 6.2623
  6, 10.0106, 6.4298
  7,  9.9954, 6.8259
  8,  9.9581, 7.6108
  9,  9.9072, 7.6397

实验结果也验证了,越后抽的人抽到的方差越大,风险越大,抽到超低红包或者最佳手气的可能性也最大。

解法二:保证同一分布取值(机会均等)

我们要保证每个人的期望相同,也可以说成是机会均等。那么如果我们在一个均匀分布(例如 $U(0, 1)$)中取值若干次,然后按照数值的比例去切割红包,不就可以实现「机会均等」了吗。

示例代码如下(因为需要预先生成所有红包数额,所以没用上面的 test 代码):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def split_random_money_ratio(money, size):
    ratio = [np.random.rand() for _ in range(size)]
    ratio /= np.sum(ratio)
    ret = [round_money(money * r) for r in ratio]
    ret[-1] = round_money(money - np.sum(ret[:-1]))
    return ret

def test(money=100, size=10, num_tests=10000):
    rets = [split_random_money_ratio(money, size) for _ in range(num_tests)]

    print(f'num,     mean,      std')
    for i in range(size):
        print(f'{i:3d}, {np.mean(rets[i]):8.4f}, {np.std(rets[i]):8.4f}')

测试结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
num,     mean,      std
  0,  10.0000,   4.4034
  1,  10.0000,   4.6846
  2,  10.0000,   3.5690
  3,  10.0000,   4.4951
  4,  10.0000,   3.9861
  5,  10.0000,   4.7215
  6,  10.0000,   6.0410
  7,  10.0000,   4.6096
  8,  10.0000,   2.6252
  9,  10.0000,   6.1895

我们可以看到均值是稳定的,但是方差的差别没有什么明显的规律,应该是比上面的解法更加公平。

参考