Research on WeChat Red Packet Algorithm

Background: Before the New Year relatives were grabbing red envelopes, they all wanted to grab the first one, saying that the sooner the grabbing, the bigger the grabbing.In fact, this must be incorrect. WeChat should have generated all the red envelopes when you sent the red envelopes. So you said that no matter how many people grab them, it should be the same as WeChat. Unless WeChat did some processing, for example, the earlier you grab the red envelopes, the more likely you are to have the best hand. When you return to work after the end of the year, you suddenly think about the strategy of WeChat red envelopes generation.

20 yuan 10 red envelopes, 2 yuan per person.Because in theory the amount of red envelope should be about 2 yuan, and the more probable the smaller the probability, it feels like a normal distribution function, so it feels that the WeChat red envelope belongs to truncated normal distribution.The best hand is about 2-3 times.
Like this (the one you find online):

All red packages are generated when the sender sends the red packages. A red pack is just a red pack that is generated. Clicking on a red pack sent by someone else only counts if there is a red pack at the moment you click. If there is no red pack, you can only check details. So the split word that appears when you open it is equivalent to a token, you can use this token to get the red pack.Of course, this token may have been used up when you received the red envelope, so you'll also go back to details and tell you how much money you received.

The amount randomly allocated from the red envelope pool each time should be the mean of the total number remaining at that time. For example, the first person should be based on a normal distribution of 2. If he draws 4 yuan, then the random second red envelope is naturally based on a normal distribution of 16/9. Then, push back and draw the last one without drawing, and divide the rest directly.And because red envelopes are at least 0.01, every time you draw a prize, you have to leave enough money to distribute the remaining red envelopes. You can judge them at random every time.And I made a quota multiplier, because the random numbers are likely to be below the mean, and multiple accumulations are likely to cause the last red envelope to be too large, so I made adjustments that need to be re-drawn when the last red envelope is larger than a certain multiple.In addition, in such a lottery, the average value of the first person should be the largest, so I have distorted the order of the resulting red packets at the end.

Randomly generated red envelope code, made some simple encapsulation.
If Y~N(a, b^2) (b>0), X=(Y-a)/b~(0,1)

package com.galaxy.fym.algorithm.maxsublist;

import java.math.BigDecimal;
import java.util.*;

/**
 * Created by fengyiming on 2017/2/17.
 *
 * @author fengyiming
 *         Random red envelopes: the amount is too distributed
 *
 *         If the non-standard normal distribution X~N (mu, _^2), then a one-time function (X-mu)/_of X must obey the standard normal distribution N(0,1).
 *         For example, a quantity X is a non-standard normal distribution with an expectation of 10 and a variance of 5^2 (that is, X~N(10,5^2)); then for the linear function Y=(X-10)/5 of X, Y is Y~N(0,1) which obeys the standard normal distribution.
 */
public class RedPacket {

    private static Random random = new Random();

    private static BigDecimal MIN_VALUE = new BigDecimal("0.01");

    private static boolean isMin = false;

    /**
     * Generate Red Packet
     *
     * @param amountValue Total red envelope amount
     * @param sizeValue   Red Pack Size
     * @param maxMutValue Remaining Red Packet Limited Multiple
     * @param sigmaValue  Standard deviation multiple
     * @return
     */
    public static List<BigDecimal> getAllHotPacket(double amountValue, double sizeValue, double maxMutValue, double sigmaValue) {
        //Total red envelope amount
        BigDecimal amount = new BigDecimal(String.valueOf(amountValue));
        BigDecimal restAmount = amount;
        BigDecimal size = new BigDecimal(String.valueOf(sizeValue));
        BigDecimal mu = restAmount.divide(size, 2, BigDecimal.ROUND_HALF_DOWN);
        BigDecimal avg = new BigDecimal(mu.toString());
        BigDecimal MAX_MUT = new BigDecimal(String.valueOf(maxMutValue));
        double sigma = sigmaValue <= 0 ? 1 : sigmaValue;
        List<BigDecimal> hotPacketPool;
        do {
            hotPacketPool = new ArrayList<BigDecimal>(size.intValue());
            int hotPacketSize = size.intValue() - 1;
            //size-1 red envelope before random outgoing, the last red envelope takes the remaining value, and the last red envelope cannot be too large, has a limit multiple of the mean
            for (int i = 0; i < hotPacketSize; i++) {
                BigDecimal randomBigDecimal = getRandomHotPacketAmount(mu.doubleValue(), sigma, restAmount, size.intValue()-1);
                restAmount = restAmount.subtract(randomBigDecimal);
                //System.out.println("Remaining red envelope amount:" + restAmount);
                size = size.subtract(BigDecimal.ONE);
                mu = restAmount.divide(size, 2, BigDecimal.ROUND_HALF_DOWN);
                hotPacketPool.add(randomBigDecimal);
            }
            hotPacketPool.add(restAmount);
        } while (restAmount.compareTo(avg.multiply(MAX_MUT)) > 0);
        //Disrupt the red packet order because the earlier the red packet is, the higher the mean value is
        //Traverse the list in reverse order, and then swap numbers at the current position by randomly passing an int number smaller than the current position
        Collections.shuffle(hotPacketPool);
        return hotPacketPool;
    }

    /**
     * Calculate the size of random red envelopes based on the mean and standard deviation of the remaining red envelopes
     *
     * @param mu
     * @param sigma
     * @param rest The rest of the money
     * @param restSize How much red envelopes are left
     * @return
     */
    private static BigDecimal getRandomHotPacketAmount(double mu, double sigma, BigDecimal rest, int restSize) {
        if(isMin){
            return MIN_VALUE;
        }
        BigDecimal radomNo;
        //Minimum remaining money
        BigDecimal minRest = MIN_VALUE.multiply(new BigDecimal(restSize));
        //Random red envelopes must also meet the minimum remaining red envelopes of 0.01
        do {
            radomNo = getRandom(mu, mu * sigma);
        }
        while (rest.subtract(radomNo).subtract(minRest).compareTo(BigDecimal.ZERO) < 0);
        if(rest.subtract(radomNo).subtract(minRest).compareTo(BigDecimal.ZERO) == 0){
            isMin = true;
        }
        BigDecimal randomBigDecimal = radomNo;
        //Take 2 decimal places for the red envelope amount
        randomBigDecimal = randomBigDecimal.setScale(2, BigDecimal.ROUND_HALF_DOWN);
        //Judgement amount cannot be less than 0.01 yuan
        randomBigDecimal = randomBigDecimal.compareTo(MIN_VALUE) > 0 ? randomBigDecimal : MIN_VALUE;
        return randomBigDecimal;
    }

    /**
     * double value producing normal distribution of mu sigma
     *
     * @param mu
     * @param sigma
     * @return
     */
    private static BigDecimal getRandom(double mu, double sigma) {
        double randomValue = random.nextGaussian() * sigma + mu;
        BigDecimal value = new BigDecimal(String.valueOf(randomValue)).abs();
        return value;
    }

    public static void main(String[] args) {
        BigDecimal all = BigDecimal.ZERO;
        List<BigDecimal> allHotPacket = getAllHotPacket(10d, 10d, 3d, 1d);
        int size = allHotPacket.size();
        BigDecimal max = BigDecimal.ZERO;
        int maxIndex = 0;
        for (int i = 0; i < size; i++) {
            BigDecimal amout = allHotPacket.get(i);
            System.out.println("No." + (i + 1) + "Random red packet amount size:" + amout);
            if (amout.compareTo(max) > 0) {
                max = amout;
                maxIndex = i + 1;
            }
            all = all.add(amout);
        }
        System.out.println("All red envelope amounts are red envelopes:" + all);
        System.out.println("The best hand is:" + maxIndex + "Red envelopes in amount:" + max);
    }

}
First random red packet amount size: 0.15
 Second random red packet amount size: 1.48
 3rd Random Red Packet Amount Size: 0.02
 4th Random Red Pack Amount Size: 2.21
 5th Random Red Pack Amount Size: 1.14
 All red envelopes amount is red envelope: 5.00
 Best luck: 4th Red envelope, amount: 2.21

First random red packet amount size: 0.13
 Second random red packet amount size: 0.65
 3rd Random Red Packet Amount Size: 2.30
 4th Random Red Pack Amount Size: 0.95
 Random red packet size 5: 0.97
 All red envelopes amount is red envelope: 5.00
 Best luck: 3rd red envelope, amount: 2.30

First random red packet amount size: 4.74
 Second random red packet amount size: 0.88
 3rd Random Red Packet Amount Size: 1.07
 4th Random Red Packet Amount Size: 0.20
 Random red packet size 5: 0.43
 6th Random Red Packet Amount Size: 0.41
 7th Random Red Packet Amount Size: 0.22
 8th Random Red Packet Amount Size: 0.20
 9th Random Red Pack Amount Size: 0.65
 10th Random Red Pack Amount Size: 1.20
 All red envelopes amount is red envelope: 10.00
 Best luck: 1st red envelope, amount: 4.74

First random red packet amount size: 0.63
 Second random red packet amount size: 0.33
 3rd Random Red Packet Amount Size: 1.35
 4th Random Red Pack Amount Size: 1.00
 5th Random Red Pack Amount Size: 0.70
 6th Random Red Pack Amount Size: 3.19
 7th Random Red Packet Amount Size: 0.19
 8th Random Red Packet Amount Size: 1.50
 9th Random Red Pack Amount Size: 0.18
 10th Random Red Pack Amount Size: 0.93
 All red envelopes amount is red envelope: 10.00
 Best luck: 6th red envelope, amount: 3.19

First random red packet amount size: 1.05
 Second random red packet amount size: 0.68
 3rd Random Red Packet Amount Size: 0.19
 4th Random Red Packet Amount Size: 1.64
 Random red packet size 5: 1.64
 6th Random Red Packet Amount Size: 0.86
 7th Random Red Packet Amount Size: 0.81
 8th Random Red Packet Amount Size: 1.06
 9th Random Red Pack Amount Size: 0.98
 10th Random Red Pack Amount Size: 1.09
 All red envelopes amount is red envelope: 10.00
 Best luck: 4th Red envelope, amount: 1.64

Testing whether random numbers conform to normal distribution

package com.galaxy.fym.algorithm.maxsublist;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * Created by fengyiming on 2017/2/19.
 * Algorithms for Verifying Normal Distribution
 */
public class Test2 {

    private static Random random = new Random();

    private final static double[] sigmas = {1d, 2d, 3d};

    private final static double DOUBLE_1 = 1d;

    private final static double DOUBLE_0 = 0d;

    public static void main(String[] args) {
        int size = 10000000;
        double mu = 2d;
        double sigmaValue = 1d;
        //Switching Standard Deviation
        double sigma = mu * sigmaValue;
        Map<Double, Double> map = installMap();
        for (int i = 0; i < size; i++) {
            double radomNo = getRandom(mu, sigma);
            if (radomNo > mu - sigma && radomNo <= mu + sigma) {
                map.put(sigmas[0], map.get(sigmas[0]) + DOUBLE_1);
            }
            if (radomNo > mu - 2 * sigma && radomNo <= mu + 2 * sigma) {
                map.put(sigmas[1], map.get(sigmas[1]) + DOUBLE_1);
            }
            if (radomNo > mu - 3 * sigma && radomNo <= mu + 3 * sigma) {
                map.put(sigmas[2], map.get(sigmas[2]) + DOUBLE_1);
            }
        }
        double mu1 = map.get(sigmas[0]);
        double mu2 = map.get(sigmas[1]);
        double mu3 = map.get(sigmas[2]);
        System.out.println("The probability that a random number will appear within one label difference is:" + mu1 / size);
        System.out.println("The probability that a random number will appear within two label differences is:" + mu2 / size);
        System.out.println("The probability that a random number will appear within three label differences is:" + mu3 / size);

    }

    private static double getRandom(double mu, double sigma) {
        return random.nextGaussian() * sigma + mu;
    }

    private static Map<Double, Double> installMap() {
        Map<Double, Double> map = new HashMap();
        map.put(sigmas[0], DOUBLE_0);
        map.put(sigmas[1], DOUBLE_0);
        map.put(sigmas[2], DOUBLE_0);
        return map;
    }
}

Of course, WeChat red envelope is certainly not that simple, and may not be based on normal distribution, so in order to increase its playability, there should be a lot of processing. For example, when the mean value of red envelope is high, there will always be some people who will score several points. This estimate should be handled.

Keywords: Java REST less

Added by Roble on Thu, 21 May 2020 06:48:23 +0300