“This is the 13th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

preface

This is a transcript of my previous blog post on CSDN. The original link is: Monte Carlo algorithm learning notes

Introduction:

Monte Carlo algorithm is a class of random algorithms, using random samples to estimate the true value. In this video we are going to use a couple of examples to illustrate the Monte Carlo algorithm.

By uniform sampling
$\pi$

Let’s say we don’t know
$\pi$Value. Now let’s estimate
$\pi$Value, assuming we have a random number generator, can we use it to estimate
$\pi$Value? Next, we use the Monte Carlo method to estimate
$\pi$Value.

Suppose we have two random number generators, both of which can generate random numbers from -1 to +1 evenly. We take one of the generated numbers as x and the other as Y. So you’re generating one point in the plane coordinate system at a time. All the points are going to be in the blue square, and since x and y are uniformly distributed, all the points in the blue square have the same probability density. The square contains a green circle of radius 1 centered at the origin.

Random points can fall inside or outside the circle. So we can think about, what is the probability that a point falls inside a circle? Obviously, the probability should be the area of the circle divided by the area of the square. That is, P = PI / 4 P = PI / 4 P = PI / 4.

Suppose we sample uniformly n points from the square region, then the expected number of points that fall into the circle is PnPnPn. Of course, this is a mathematical expectation, not a certainty.

Another problem is how to determine whether a point is inside or outside the circle given a point. Well, it’s pretty easy to figure that out, just using the equation of the circle. That is, we only need to determine whether the point is satisfied

Can.

Suppose we uniformly sample n groups of points, and m of them fall inside the circle. If n is very large, then we can approximate it

So I’m going to apply the transformation, and I’m going to put n in the denominator. We can get:

The law of large numbers guarantees that Monte Carlo is correct, and as the number of samples n approaches infinity, 4m/n approaches
$\pi$. In fact, the probability inequality can be used to calculate the upper bound between the true value and the estimated error. The Bernstein inequality proves that the upper bound of the estimation error is inversely proportional to
$\sqrt{n}$. This means that the larger the sample size, the more accurate the Monte Carlo approximation. However, the convergence rate is not fast. The accuracy can only be improved by 100 times if the sample size is more than 10,000 times.

So we have that
$\pi$Formula, we can program calculation, pseudo-code as shown in the figure below:

Buffon needle experiment

Buffon’s pin drop experiment was also used to calculate PI \ PI π, and the advantage is that it can be done by humans without the need for a computer. The contents of Buffon’s needle-throwing experiment are as follows: Take a piece of paper, draw a number of equally-spaced parallel lines, throw a random needle, and count how many needles intersect the parallel lines. From this quantity, we can calculate PI \ PI π.

Its calculation formula is as follows:The proof is omitted.

Estimate the shaded area

As shown in the figure below, we need to calculate the shaded area.As shown in the figure, the shaded points must satisfy two conditions:

1. It has to be inside the circle
2. It has to be outside the sector

So it satisfies the following equation:We randomly sample points in the square area. We do n experiments, and m of them fall in shadow. Then the area of the shaded part can be estimated as:Its pseudocode is as follows:

Approximate integration

Approximate integration is one of the most important applications of Monte Carlo, widely used.

Definite integral of a function of one variable

Let’s first look at a simple problem, using monte Carlo method to find the definite integral of a function of one variable. The independent variable x of a function of one variable is a scalar. The specific calculation method is as follows:

1. Uniformly sampling n points x1 from the interval [a, b]… ,xn
2. Take the average of these n points times the length of the interval b minus a, and call that Qn
3. The definite integral I of the function over the interval is approximately Qn

Similarly, the law of large numbers guarantees monte Carlo correctness. As the number of samples n approaches infinity, Qn approaches I.

Definite integral of a function of several variables

When the independent variable x is a set of variables, it is the definite integral of a function of several variables. The calculation process is as follows:

1. First, x1,… xnx_1,\cdots, X_nx1,… xn are obtained by random and uniform sampling from the integral space ω \Omega ω.
2. Calculate the volume V=∫ ω dxV=\int_{\Omega}dxV=∫ ω dx
3. Calculate Qn = V 1 n ⋅ ∑ I = 1 nf (xi) Q_n = V \ cdot \ frac {1} {n} \ sum_ {I = 1} ^ nf (x_i) Qn = V ⋅ n1 ∑ I = 1 nf (xi)
4. The definite integral I of the function over the interval is approximately Qn

Note that this definite integral may also be difficult to compute in the second step, but we also want to keep the shape of Omega \Omega as simple as possible.

Let’s take an example.We can also estimate the area of a circle by calculating definite integrals
$\pi$. But also in the
$\Omega$Uniformly sampled to obtain a series of points, and then calculated
$\Omega$In the area. The final calculation
$Q_n$As an estimate of the final definite integral. This is the same way we started with probability
$\pi$It’s worth it.

Monte Carlo method is used to approximate the expectation

We define X as a d-dimensional random variable, and p(X) as its probability density function. Let f(x) represent any d dimensional function of several variables. So, we can get that the expectation of f(X) is the definite integral of f(X) times p(X) over the entire D-dimensional space:It’s not easy to directly evaluate this definite integral, especially if x is a higher-dimensional vector. In general, you can use the Monte Carlo approximation to find the expectation. Specifically, there are three steps:

1. The first is random sampling, not uniform sampling but sampling according to the probability density function p(x)
2. And then you take the sample and you plug it into the function f and you compute f of xi, f of x_i, f of xi, and you average the n values, and you call that Qn
3. Finally, Qn is returned as an estimate of the sample’s expectation.

reference

1. Monte Carlo Monte Carlo www.youtube.com/watch?v=XRG…