Crack the red envelope algorithm! Why do others always have the best luck?

Audit expert: Zheng Yuanpan

Professor of Zhengzhou University of Light Industry

Every Chinese New Year, there is a wave of red envelopes coming. Do you feel a little excited when you think about it?

However, for the same red envelope, why do others always have the "best luck" while you can only get 10 cents or 50 cents...

Is it really fair to grab red envelopes through mobile phones?

What happens on your phone the moment you open the red envelope?

What unknown scientific principles are hidden behind grabbing red envelopes?

Source: Tuchong Creative

In fact, the algorithm behind grabbing red envelopes is rigorous and complex. It must ensure fairness, be interesting, and take into account various unexpected situations in reality.

Whether it is WeChat or other payment platforms, the red envelope algorithm is a trade secret and we have no way of knowing the principle behind it.

Although it is confidential, it can't escape some basic algorithms. The actual red envelope distribution algorithm is also continuously improved on some basic and simple algorithms.

Now let me take you through several possible algorithms for implementing the red envelope function~

The red envelopes that depend on your hand speed

When this question is first asked, some people may think: Since the total amount and number of people in the red envelopes are set in advance, can't I just randomly allocate a certain amount to each person when he clicks "open the red envelope"?

The only thing to note is that this amount cannot be greater than the total amount, nor less than a penny, until all the money is robbed.

This seemingly simple and perfect red envelope distribution method actually hides a huge bug - the first person to open the red envelope, the greater the amount he or she may receive. Why is this so?

Although the amount is randomly allocated to each person when grabbing the red envelope, which seems fair, there will always be a "first come, first served" principle.

Let's assume there is a 100 yuan red envelope. The first person can randomly get a certain amount between 0.01 yuan and 100 yuan. If we calculate all the possible amounts that the first person draws and take the average, then he can get 50 yuan on average.

This 50 yuan has a vivid name in mathematics, called mathematical expectation. Since it is an "expectation", there will always be times when it fails, and there are also unexpected surprises. Therefore, the amount drawn by the first person may be less than 50 yuan, or it may be more than 50 yuan.

Assuming the first person gets 23 yuan, there will only be 77 yuan left in the red envelope. Even if the second person is lucky, he can only get a value very close to 77 yuan (if there are others who want to grab the red envelope later). This is less than the maximum amount of money the first person can get (very close to 100 yuan).

If we use the "mathematical expectation" method mentioned above to calculate, the second person can only get 38.5 yuan on average, which is obviously unfair.

As the red envelope grabbing game progresses, the later people grab the red envelopes, the less total amount left in the red envelopes, and the smaller the possible profit on average. The red envelope grabbing game that should have been "full of surprises" and "exciting and thrilling" eventually turned into a "hand speed competition" and "network speed competition."

However, there is room for improvement in this method, which is to allocate the amounts in advance and randomly shuffle the order before the first person opens the red envelope.

This is equivalent to the person who sends the red envelope successfully paying, and the mobile phone automatically generates a specified number of simulated people, and lets them grab the money in the red envelope in turn according to this random allocation method. According to what was said before, the simulated people who grab the red envelope first will get more money on average than the simulated people who grab the red envelope later.

At this time, we randomly shuffle the order of these "simulated people". When the real person clicks on the red envelope, these "simulated people" will hand over the money they have grabbed to the real person who is operating the mobile phone in the shuffled order. In this way, by pre-allocating and shuffling the order, we have successfully solved the problem of the amount of money being grabbed getting smaller and smaller.

“Rain and dew are shared equally” red envelope

In order to improve the fairness of grabbing red envelopes, some people have proposed another red envelope algorithm called the "double mean method".

Don't be scared by this high-end name, the principle of this method is very simple, that is, to forcibly reduce the maximum amount that each person can draw. Even if you are the first person to open the red envelope, you are not allowed to arbitrarily draw an amount between 0.01 and 100 yuan.

Source: Tuchong Creative

So, how do we determine the maximum amount each person can draw?

Assume that the total amount of the red envelope is 100 yuan, and 20 people are trying to grab it. If it is distributed equally, each person can get 5 yuan. Multiply this number by 2 and you will get the maximum amount that the first person is allowed to draw, which is 10 yuan. This is also the origin of the name "double average".

With this method, the first person can only randomly draw a certain amount between 0.01 and 10 yuan, and the mathematical expectation of the amount he draws is 5 yuan on average. Assuming that he is unlucky and draws 4 yuan, then when it is the second person's turn to open the red envelope, there will be 96 yuan left.

Similarly, we assume that 96 yuan is divided equally among 19 people, with each person getting about 5.5 yuan on average. Multiplying this number by 2 is the maximum amount the second person can get, 10.10 yuan. He can only randomly draw a certain amount between 0.01 yuan and 10.10 yuan. The average amount of all the amounts he can draw is about 5.05 yuan.

If the second person is extremely lucky and wins 6 yuan, then the third person may get between 0.01 and 10 yuan, with a mathematical expectation of 5 yuan.

By analogy, we found that no matter you are the first person to open a red envelope or the 19th person to open it, the maximum amount you can get is almost the same, and on average you may get about the same amount of money, which greatly improves the fairness of grabbing red envelopes.

So is this red envelope algorithm the best?

You know, this kind of "equal distribution" red envelope has a strong sense of fairness, but it also sacrifices many surprises.

Once we know the amount of the red envelopes and the number of people who receive them, we can roughly estimate our earnings. Even if we are the "lucky one" today, the money we can get will not exceed the pre-calculated upper limit.

So, how can we make the process of grabbing red envelopes fair and exciting? Take a look at the following methods~

The inspiration of "Rope Cutting"

We have just played a lot of "games" with numbers. Now let's put aside the numbers and look at life.

In addition to representing 100 yuan, 100 can also have many meanings, such as 100 meters of rope.

So, we might as well use a 100-meter rope to represent 100 yuan. If there are 20 people grabbing the red envelope, we randomly cut 19 cuts on the rope to divide it into 20 parts of completely random lengths. Each person then randomly takes one part. The longer the rope, the more money it represents.

What would happen if the above situations were applied to the rope cutting problem?

The first method of randomly distributing the amount of money is like taking a pair of scissors and randomly cutting 19 times from left to right, and each cut is directly given to one person.

The improved random distribution method is to put the last 20 pieces of rope into a black box and shake them evenly, and let the recipient draw from the box like drawing lots.

The "double mean method" is still to cut the rope from left to right and distribute it to everyone while cutting. However, the maximum length of each cut is strictly limited.

After this analogy, have you thought of any new distribution methods?

What would happen if we broke the rule of "cutting from left to right" and instead randomly cut 19 pieces of rope on the 100-meter rope, and then distributed the 20 pieces of rope to each person in turn?

Source: Author's own

Since the order of left and right is not affected, the length of each rope is not limited, which retains the surprise of grabbing the red envelope. In addition, since the 19 knives need to be randomly cut before distribution, the order of opening the red envelope will not affect the amount, ensuring fairness, which can be said to be the best of both worlds.

Do you think this analogical way of thinking is interesting? It not only allows us to understand the principle of grabbing red envelopes from a different perspective, but also provides a new idea for the discovery of new methods.

In fact, the actual operating principle of WeChat red envelopes is much more complicated than the several methods we introduced. It involves some details that are easy to overlook but have a great impact on the results.

For example, the minimum amount of RMB is 0.01 yuan. How can we ensure that the amount of the randomly generated red envelope is not less than 0.01 yuan? Will the first few people with "extreme luck" take away most of the amount in the red envelope, so that the people behind cannot even get an average of 0.01 yuan?

There are actually many details like this, and the WeChat red envelope allocation algorithm we are using now is not necessarily the most perfect. With the update of the version and the upgrade of the algorithm, the logic of the red envelope allocation algorithm is also being improved little by little.

Source: Digital Beijing Science Center