“This is the 19th day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

preface

Random numbers are a very useful tool, especially when simulating natural phenomena or uncertain events. For example, in game development, we can use random numbers to simulate the random walk of NPCS, and we can also use random numbers to generate some random data, such as simulating the population distribution of different features in the natural population. Today, we will learn about random numbers.

Random walk

Suppose we now have an infinitely large map, and an NPC character needs to randomly walk around the map. So, we can control this behavior through random numbers. We generate a random number to determine which direction the NPC needs to move west. We generate a random number between -1 and 1 to determine how far the NPC needs to move once in the X and Y directions, respectively.

Using p5.js, we can write the following simple code


function sketch() {
    return {};
}

const p = new P5(sketch, document.body);
let walker: Walker = null;

p.setup = function () {
    p.createCanvas(640.360);
    walker = new Walker(p, 320.180);
};

p.draw = function () {
    p.stroke(0);
    walker.update();
    walker.display();
};

class Walker {
    x: number = 0;
    y: number = 0;

    constructor(private p: p5, x: number, y: number) {
        this.x = x;
        this.y = y;
    }

    display(): void {
        this.p.stroke(0);
        this.p.point(this.x, this.y);
    }

    update(): void {
        const v = Vector.random2D();
        this.x += v.x;
        this.y += v.y; }}Copy the code

The results of the program are as follows:

So that’s a simple example of random numbers. One feature of the random walk example above is that NPCS are equally likely to move in one direction at any given time. For random numbers with equal probability in a certain range, we call them evenly distributed random numbers.

Gaussian distribution

Now we come to the second application scenario. Suppose we need to simulate the population of a certain country, and we use random numbers to generate humans of different heights. Therefore, it is obviously inappropriate for us to use such random numbers with average distribution. According to the survey, people’s heights are not evenly distributed, and most people’s heights are near the average height, and there are always a few people who are very tall and very short. Therefore, the average distribution of random numbers here is not very composite. According to the survey, the distribution of human height basically follows the gaussian distribution model.

For a scenario like this, we now need to simulate the effect of various splashes of paint on the drawing board, most of which should be in the middle. We can use this property of gaussian distribution to simulate.


const points: DrawPoint[] = [];

p.setup = function () {
    p.createCanvas(640.360);
    walker = new Walker(p, 320.180);
};

p.draw = function () {
    p.clear();
    p.stroke(0);
    points.push(new DrawPoint(p));
    points.forEach((p) = > p.display());
};

class DrawPoint {
    x: number;
    y: number;
    color: number[];
    constructor(private p: p5) {
        this.x = p.randomGaussian(0.5.0.2) * 640;
        this.y = p.randomGaussian(0.5.0.2) * 320;
        this.color = [p.random(0.255), p.random(0.255), p.random(0.255)];
    }

    display(): void {
        this.p.fill(this.color);
        this.p.circle(this.x, this.y, 5); }}Copy the code

The result is that most of the dots fall closer to the center of the canvas, with fewer dots falling from the edges.

Custom distribution of random numbers

However, there are many examples that cannot be directly simulated by using uniform distribution and Gaussian distribution. We may need to generate a random number that follows a probability distribution function.

Again, using the example above of paint falling on the canvas, we don’t really want the points to be normally distributed, but let’s say we want the points to be exponentially distributed. The probability density function of the exponential distribution is as follows:

We can observe that the closer we get to zero, the more random we get, which means that our paint should fall closer to the top left corner. So how do we generate random numbers that obey our custom probability density function?

Here is a common method called accept-reject. The core idea of this method is as follows:

  1. Select a random number R1
  2. Pick another random number, R2
  3. If R2 is less thanpdf(R1), R1 is the random number we need
  4. If not, start from scratch

The algorithm is described as follows:

function montecarlo(pdf: (x: number) = >number) :number {
    while (true) {
        const a = Math.random();
        const b = Math.random() * 5;
        if (b < pdf(a)) {
            returna; }}}Copy the code

The PDF here refers to the probability density Function, according to which we can get random numbers that obey any probability density distribution function. Then we can also easily make our pigment spots obey the exponential distribution, the result is as follows:

Note:

In particular, do you have any questions about why b = math.random () * 5 has a 5? This 5 represents the maximum of the probability density function. And we can use the following pictures to illustrate why we need to multiply by its maximum here.

If we do not multiply by the maximum of the PDF function, the random number distribution we generate using the algorithm is as follows:

As we can see, since the maximum values we generate are 0~1, some of the values generated by the PDF function are obviously greater than 1, so some of the values greater than 1 cannot be represented. At this point, we need to manually adjust this parameter. At this point, we make b = math.random () * 2

In this way, we get points that are really gaussian. Therefore, the shortcoming of this algorithm is that different maximum values need to be set for different probability density functions.

conclusion

Today we looked at some applications of random numbers, and we can do some amazing things with random numbers. However, js comes with random numbers that are evenly distributed. However, for some scenarios, evenly distributed random numbers are not applicable. So we learned about the Gaussian distribution, which is a random distribution function. The random function with gaussian distribution can help us solve part of the scene, but its flexibility is not too high. What we want more is to get a random number that obeys any probability density function. Finally, we use the accept-reject method to help us achieve this feature.

Well, that’s pretty much it for today. Don’t forget to give the author a thumbs up if you found this article useful