While others are grabbing red envelopes, programmers are studying red envelope algorithms

The popularity of WeChat red envelopes during the Year of the Goat is self-evident. Advertisers invested 500 million yuan in cash red envelopes and cooperated exclusively with CCTV's Spring Festival Gala in the Year of the Goat, which played a huge role in promoting the event. This was like a shot of a tonic pill, which brought great attention and traffic to WeChat in a short period of time. On New Year's Eve, the total number of red envelopes sent by WeChat users reached 1.01 billion times, the number of shake interactions reached 11 billion times, and the peak number of red envelopes sent was 810 million times per minute.

Putting aside the market value of WeChat red envelopes, the algorithm of the red envelopes themselves has also sparked heated discussions. Since the official has not given a clear statement, there are many different opinions. The editor will also bring you several analyses below.

First, let’s look at the data analysis emperor

Most people make their own guesses, which is the only option when you don't know the internal randomization algorithm, but most people don't give their own survey results. Here is a sample of 100 survey data and make your own guesses.

1. The amount of money in the wallet satisfies the truncated normal random number distribution. Roughly speaking, take a random number from the truncated normal distribution, divide its sum by the total value, get the correction factor, and then multiply all the random numbers by the correction factor to get the red envelope value.

This distribution means: there are more red envelopes below the average, but not far from the average; there are fewer red envelopes above the average, but there are more red envelopes far larger than the average.

Figure 1. Wallet value and its frequency distribution histogram and normal fitting

But looking at the distribution histogram does not indicate that it conforms to the normal distribution, but considering the simplicity of the program and the rationality of the random numbers, this is the most reasonable guess.

The later the wallet is, the higher the value is.

Figure 2. Curve of relationship between wallet sequence number and its value

From the linear fitting red line in Figure 2, we can see that the overall trend of wallet value is slowly increasing, and its range of change is roughly a "channel" drawn by the upper and lower boundaries of the green dotted line. (The curve can be enclosed in such a conventional "channel", which also reflects the rationality of Rule 1 from the side, indicating that it is not a uniformly distributed random number)

This pattern can also be seen from another graph of averages.

Figure 3. The curve of the average value changing with the number of sequences

In the sample, a wallet with a value of 1,000 is divided into 100 parts, with an average of 10. However, in Figure 3, we can see that before the last wallet, the average was always lower than 10, which means that the value of the wallet at the beginning was low, and it was always pulled up by the value of the later wallets, which were more valuable.

3. Of course, the average graph can also reveal another rule, that is, the person with the highest number of draws tends to be lucky and draw more. Because the person with the highest number of draws takes whatever is left in the wallet, and the average of all the previous draws is less than 10, so at least the person with the highest number of draws will be higher than the average. In this sample, wallet No. 98 draws 35, while the wallet with the highest number of draws draws 46.

In summary, based on the sample guess:

1. Most of the time the amount of money you draw is the same as others, but once it’s more, it can easily be a lot more.

2. The closer you pull out of the wallet at the back, the easier it is to get more money.

3. ***It is often easy for a person to have good luck.

Comment: This is obviously very practical and there is a difference. Every time I grab it, it’s only a few cents no matter when.

The second student wrote a simple python code

It has been observed that the red envelope distribution meets the following points:

1. No one will be left without money

2. Will not be distributed in advance

3. Money fluctuates widely

When the red envelopes were first created, the distribution plan was set. When grabbing the red envelopes, they just pop up one by one.

So the python code is as follows:

 def weixin_divide_hongbao(money, n):
 divide_table = [random.randint( 1 , 10000 ) for x in xrange( 0 , n)]
 sum_ = sum(divide_table)
 return [x*money/sum_ for x in divide_table]

However, there are two small problems with the above algorithm:

1. Floating point precision problem

2. Boundary value processing

The third student wrote a Java version based on the Python version circulated on the Internet

 int j = 1 ;
 while (j< 1000 )
 {
 int number = 10 ;
 float total = 100 ;
 float money;
 double min = 0.01 ;
 double max;
 int i = 1 ; 
 
 List math = new ArrayList();
 while (i<number)
 { 
 
 max = total- min*(number- i);
 int k = ( int )((number-i)/ 2 );
 if (number -i <= 2 )
 {k = number -i;}
 max = max/k;
 money=( int )(min* 100 +Math.random()*(max* 100 -min* 100 + 1 ));
 money=( float )money/ 100 ;
 total=total-money;
 math.add(money);
 System.out.println( "the" +i+ "person gets" +money+ "the rest" +total);
 i++;
 if (i==number)
 {
 math.add(total);
 System.out.println( "the" +i+ "person gets" +total+ "0 left" );
 }
 } 
 
 System.out.println( "The number of red envelopes distributed in this round" +(math.indexOf(Collections.max(math))+ 1 )+ "Personal luck***" );
 j++;
 }

The algorithm proposed by the fourth student seems very scientific.

He believes:

1. Everyone should be able to receive red envelopes;

2. The sum of the red envelope amounts received by each person = the total amount;

3. The amount of red envelopes received by each person varies, but it can’t be too different, otherwise it will be boring;

4. The algorithm must be simple, otherwise it will not live up to Tencent’s reputation;

Before formal coding, build a progressive model to analyze the rules

Set the total amount to 10 yuan, and N people will randomly receive it:

N=1

Then the red envelope amount = X yuan;

N=2

To ensure that the second red envelope can be sent out normally, the first red envelope amount = a random number between 0.01 and 9.99

The second red packet = 10-the amount of the first red packet;

N=3

Red Packet 1 = a random number between 0.01 and 0.98

Red envelope 2 = a random number between 0.01 and (10-red envelope 1-0.01)

Red envelope 3 = 10 - red envelope 1 - red envelope 2

…

 header("Content-Type: text/html; charset = utf -8"); // Output is not garbled, you know
 $ total = 10 ; //Total amount of red envelope
 $ num = 8 ; // Divide into 8 red envelopes, support 8 people to receive randomly
 $ min = 0.01 ; // Each person can receive at least 0.01 yuan 
 
 for ($ i = 1 ;$i < $num;$i++)
 {
 $ safe_total =$total-($num-$i)*$min; //Random safety upper limit
    $ money = mt_rand ($min*100,$safe_total*100)/100;
 $ total =$total-$money;
 echo 'The '.$i.'th red packet: '.$money.' yuan, balance: '.$total.' yuan < br /> ';
 }
 echo 'The '.$num.'th red packet: '.$total.' yuan, balance: 0 yuan';

When I input it, I see that the fluctuations are too big and the data is too boring!

The first red packet: 7.48 yuan, the balance: 2.52 yuan

The second red packet: 1.9 yuan, balance: 0.62 yuan

The third red packet: 0.49 yuan, balance: 0.13 yuan

The 4th red packet: 0.04 yuan, balance: 0.09 yuan

The fifth red packet: 0.03 yuan, balance: 0.06 yuan

The 6th red packet: 0.03 yuan, balance: 0.03 yuan

The 7th red packet: 0.01 yuan, balance: 0.02 yuan

The 8th red packet: 0.02 yuan, balance: 0 yuan

Improve it by using the average value as a random safety upper limit to control the volatility

 header( "Content-Type: text/html; charset=utf-8" ); // Output is not garbled, you know  
 $total= 10 ; //Total amount of red envelope  
 $num= 8 ; // Divide into 8 red packets, support 8 people to receive randomly  
 $min= 0.01 ; //Everyone can receive at least 0.01 yuan   
 
 for ($i= 1 ;$i<$num;$i++)
 {
 $safe_total=($total-($num-$i)*$min)/($num-$i); //Random safety upper limit  
    $money=mt_rand($min* 100 ,$safe_total* 100 )/ 100 ;
 $total=$total-$money;
 echo 'The ' .$i. 'th red packet: ' .$money. ' yuan, balance: ' .$total. ' yuan <br/>' ;
 }
 echo 'The ' .$num. ' red packet: ' .$total. ' yuan, balance: 0 yuan' ;

The output result is shown in the figure below.

The first red packet: 0.06 yuan, the balance: 9.94 yuan

The second red packet: 1.55 yuan, balance: 8.39 yuan

The third red packet: 0.25 yuan, balance: 8.14 yuan

The 4th red packet: 0.98 yuan, balance: 7.16 yuan

The fifth red packet: 1.88 yuan, balance: 5.28 yuan

The 6th red packet: 1.92 yuan, balance: 3.36 yuan

The 7th red packet: 2.98 yuan, balance: 0.38 yuan

The 8th red packet: 0.38 yuan, balance: 0 yuan

summary:

The editor thinks that this can be completely understood as a murder caused by a red envelope. The editor has only listed a few. Some engineering students directly threw out mathematical models, discrete functions, etc., but no matter whether the algorithm is simple or complex, it is enough to have fun.