How to Get the Top K of WeChat Red Envelopes

0x00 Preface

The story goes like this: I’m about to return to the institute. There are three dormitory options: Suzhou Street, Youth Apartment, and Ke Yi Zhao. Among them, Ke Yi Zhao is likely the worst. Suzhou Street has the best living conditions, but it’s a 6-person room with a long commute time, making Youth Apartment seem quite OK.

Since the quotas for Youth Apartment and Suzhou Street are limited, they are often allocated via a lottery. The most traditional lottery method is grabbing red envelopes. The strategy adopted by my lab is ‘winner takes all,’ meaning those who get the Top K of WeChat red envelopes get the better accommodation.

0x01 Analysis

Bi Dao analyzed WeChat red envelope grabbing back in 2020 BV1z7411e7qB¹, concluding that everyone’s expected value is the same, but the later you grab, the more likely you are to get a ‘big red envelope,’ and the variance increases.

This leads to the probability of becoming the ‘Luckiest King’:

Under this condition, we hope not necessarily to be the Luckiest King, but to be in the Top K, so this can be considered an incremental work based on Bi Dao’s research.

0x02 Simulation

From Bi Dao’s video, we can see that WeChat red envelope amounts are distributed in [0.01, 2 * average of remaining amount]. Therefore, I used ChatGPT to write a simulation program, fixed some bugs myself, and here we only calculate for up to 20 people and the Top 10, simulating 100,000 times.

However, there are some pitfalls to note: first, the amount grabbed must be rounded to two decimal places; second, if it’s the last person, they must grab the exact remaining amount.

The code is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

import random
import matplotlib.pyplot as plt

# 模拟参数
num_trials = 100000


def simulate_red_envelope(num_users):
    total_amount = 100.0
    red_envelope = [0.0] * num_users

    for i in range(num_users):
        remaining_envelope = num_users - i
        remaining_amount = total_amount - sum(red_envelope)
        avg_amount = remaining_amount / remaining_envelope
        max_amount = min(avg_amount * 2, remaining_amount)
        amount = (
            random.uniform(0.01, max_amount)
            if remaining_envelope > 1
            else remaining_amount
        )
        amount = round(amount * 100) / 100.0
        red_envelope[i] = amount

    return red_envelope


def calculate_topk_probability(num_users, num_trials):
    probabilities = []
    for k in range(1, min(num_users, 10)):
        results = [0] * num_users
        for _ in range(num_trials):
            red_envelope = simulate_red_envelope(num_users)
            sorted_envelope = sorted(
                range(num_users), key=lambda x: red_envelope[x], reverse=True
            )
            topk = sorted_envelope[:k]
            # 统计获得 topk 的概率
            for i in range(k):
                results[topk[i]] += 1

        probabilities.append([result / num_trials for result in results])

    return probabilities


def plot_probability(probabilities):
    num_users = len(probabilities[0]) if len(probabilities) > 0 else 0
    k_values = list(range(1, min(num_users, 10)))

    # 绘制 k 个子图
    plt.figure(figsize=(4 * len(k_values) + 4, 4))

    for i, k in enumerate(k_values):
        ax = plt.subplot(1, len(k_values), i + 1)

        ax.plot(range(1, num_users + 1), probabilities[i], label="Probability")
        print(probabilities[i], k)

        ax.set_xlabel("Rank")
        ax.set_xlim(1, num_users)
        # 只显示整数坐标
        ax.set_xticks(range(1, num_users + 1))
        ax.set_ylabel("Probability")
        ax.set_ylim(0, 1)

        # Title
        ax.set_title("Probability of Top {} Amounts".format(k))

    # plt.xlabel("Rank")
    # plt.xlim(1, num_users)
    # # 只显示整数坐标
    # plt.xticks(range(1, num_users + 1))
    # plt.ylabel("Probability")
    # plt.ylim(0, 1)

    # plt.title("Probability of Top K Amounts")
    # plt.legend()

    plt.savefig("red_envelope_probability_N{}_K{}.png".format(num_users, k))


for N in range(2, 21):
    # 模拟抢红包并计算概率
    probabilities = calculate_topk_probability(num_users=N, num_trials=num_trials)

    # 绘制概率图表
    plot_probability(probabilities)

0x03 Results & Conclusions

The results obtained are quite extensive; I will only display a few characteristic ones ($N = 2,3,4,5,10,20$).

First, Top 1 is essentially the Luckiest King, used to compare with Bi Dao’s results to verify the correctness of my findings.

1. Regarding the Luckiest King, just as Bi Dao concluded, the more people there are, the higher the probability that the last two people will become the Luckiest King.

2. Regarding Top K, as K increases, this curve gradually changes from a concave curve to a convex curve, until finally becoming a monotonically decreasing curve. This is what is meant by ‘variance increases.’ As K increases, the probability of the last person getting a lower amount increases, thus the probability of entering the Top K decreases. At the same time, the probability of entering the Top K also increases in mean value as K grows, after all, the probability of 10 people getting Top 10 is always 1.

In other words, within a certain range, it is better to grab later to get the Top K, but when K exceeds a certain value, it is better to grab earlier.

So, where does this threshold lie? Let’s explore this question next.

There are actually some small tricks here. First, the person who grabs last is very special because their amount is not obtained through sampling. When calculating the turning point, if we consider making the entire sequence monotonically decreasing, the sequence becomes extremely unstable, even lacking clear patterns (non-increasing), requiring more theoretical calculation to support this conclusion. It is also heavily influenced by sampling errors, as the probability difference between the last two is not significant. Limited by my knowledge of probability theory, I leave this difficult problem for the reader to ponder. However, if we do not consider the last person and only consider the decreasing sequence of the preceding ones, then this threshold becomes increasing as N increases.

The plot of N regarding the threshold k is shown below:

A conjectured conclusion is that this threshold k satisfies the following formula:

$$ k = \left \lfloor \frac{N-1}{4} \right \rfloor $$

As for why it is 4, it should be related to the distribution of WeChat red envelope amounts, but I lack theoretical analysis here.

0x04 Limitations

This is actually a setting of opposition among everyone. During the red envelope grabbing process, there is no information sharing, but in a real environment, you can ask classmates who have already grabbed to get the current number of people and the remaining amount. Under such conditions, the decision-making becomes more complex. For example, what should the decision be if previous people grabbed small red envelopes? What should the decision be if someone grabbed a very large red envelope? This problem remains to be explored and is left for the reader to think about.

There are still many points that have not been thoroughly studied, and limited by my probability knowledge, it is difficult to provide more probabilistic theoretical calculations. If readers are interested, welcome to discuss and exchange ideas in the comments section.