Monte Carlo method(Monte Carlo methods, MMC) is the general name of a group of numerical methods based on obtaining a large number of realizations of a stochastic (random) process, which is formed in such a way that its probabilistic characteristics coincide with similar values ​​of the problem being solved. Used to solve problems in various fields of physics, chemistry, mathematics, economics, optimization, control theory, etc.

Story

Buffon's algorithm for determining Pi

Random variables have been used to solve various applied problems for quite a long time. An example is the method for determining the number Pi, which was proposed by Buffon back in 1777. The essence of the method was to throw a needle length L onto a plane drawn by parallel lines located at a distance r from each other (see Fig. 1).

Picture 1. Buffon's method

Probability (as can be seen from the further context, we are not talking about probability, but about the mathematical expectation of the number of intersections in one experiment; this becomes a probability only if r>L) that the segment intersects the line is related to the number Pi:

, Where

A- the distance from the beginning of the needle to the nearest straight line;

θ is the angle of the needle relative to straight lines.

It’s easy to take this integral: (provided that r>L), therefore, by counting the proportion of segments intersecting lines, we can approximately determine this number. As the number of attempts increases, the accuracy of the result obtained will increase.

In 1864, Captain Fox, while recovering from an injury, in order to somehow occupy himself, carried out an experiment on throwing a needle. The results are presented in the following table:

	Number of throws	Number of intersections	Needle length	Distance between lines	Rotation	Pi value
First try					absent
Second try					present
Third try					present

Comments:

Plane rotation was used (and, as the results show, successfully) in order to reduce the systematic error.

In the third attempt, the length of the needle was greater than the distance between the lines, which made it possible, without increasing the number of throws, to effectively increase the number of events and improve accuracy.

Relationship between stochastic processes and differential equations

The creation of the mathematical apparatus of stochastic methods began at the end of the 19th century. In 1899, Lord Rayleigh showed that a one-dimensional random walk on an infinite lattice could give an approximate solution to a parabolic differential equation. Andrei Kolmogorov in 1931 gave a big impetus to the development of stochastic approaches to solving various mathematical problems, since he was able to prove that Markov chains are related to certain integro-differential equations. In 1933, Ivan Petrovsky showed that the random walk forming a Markov chain is asymptotically related to the solution of an elliptic partial differential equation. After these discoveries, it became clear that stochastic processes can be described by differential equations and, accordingly, studied using well-developed mathematical methods for solving these equations at that time.

Birth of the Monte Carlo method at Los Alamos

First, Enrico Fermi in the 1930s in Italy, and then John von Neumann Stanislaw Ulam in the 1940s in Los Alamos, suggested that it was possible to use the connection between stochastic processes and differential equations “in the opposite direction.” They proposed using a stochastic approach to approximate multidimensional integrals in the transport equations that arose in connection with the problem of neutron motion in a visotropic medium.

The idea was developed by Ulam, who, ironically, like Fox, was struggling with forced idleness while convalescing from illness, and while playing solitaire, wondered what the likelihood was that the solitaire game would “work out.” He came up with the idea that instead of using the usual considerations of combinatorics for such problems, he could simply perform the “experiment” a large number of times and, thus, counting the number of successful outcomes, estimate their probability. He also proposed using computers for Monte Carlo calculations.

The advent of the first electronic computers, which could generate pseudorandom numbers at high speed, dramatically expanded the range of problems for which the stochastic approach turned out to be more effective than other mathematical methods. After this, a big breakthrough occurred and the Monte Carlo method was used in many problems, but its use was not always justified due to the large number of calculations required to obtain an answer with a given accuracy.

The year of birth of the Monte Carlo method is considered to be 1949, when the article by Metropolis and Ulam “The Monte Carlo Method” was published. The name of the method comes from the name of the city in the Principality of Monaco, widely known for its numerous casinos, since roulette is one of the most widely known random number generators. Stanislaw Ulam writes in his autobiography, Adventures of a Mathematician, that the name was suggested by Nicholas Metropolis in honor of his uncle, who was a gambler.

This post will help you get out of a rather sticky situation. Let's say you are locked in a room, you have a skein of thread and a needle, and you are persistently asked to calculate the approximate value of a number Pi, using only these objects, well, anything can happen, you know. So, today, while listening to a course on matan at the University of Pennsylvania, I suddenly learned how to do this. What I couldn’t even imagine was that the number Pi is hiding here too. It turned out that the roots of this question go back to the 18th century, when Georges-Louis Leclerc de Buffon set himself the following task: “suppose the floor is made of wooden strips of two colors, they alternate; What is the probability that a thrown needle will fall in such a way that it will intersect the line where the two strips join?” A simulation of this process and the answer to the question can be found under the cut.

Simulation

In order not to spoil the intrigue, let's start with an experiment. So, we have many needles of length L and a skein of green thread. Let us apply a certain number of parallel segments of equal length to the surface at a distance L from each other.

Let's throw 100 needles onto this field.

Perhaps not enough. Let's add another 900 and mark those needles that cross the threads in red.

Suppose we threw not all the needles at once, but one at a time, and at each step we recorded the ratio of the number of needles that landed on the threads to the total number of thrown needles, thereby obtaining a greater and greater approximation of the probability that the needle, falling, will cross the thread .

If you throw 10,000 needles, the picture will be more accurate.

Now let’s do the following transformation: divide two by each number in the resulting series.

For 10,000 needles it is already more accurate.

If we find the average of the last five thousand terms of the series we get 3.141685 , while pi is equal to 3.141593 .

In general, it is no longer a secret to anyone that the last series converges to the number Pi. But how could this happen? I learned about this when I was 28 years old from the above course. Let's dive into the matan.

Theory

We will consider the needle and the line closest to it to the right. Let us denote the distance from the left end of the needle h, angle of deviation from the line - a.

Obviously, the length of the opposite leg from the angle A will be equal to the sine of the angle multiplied by the length of the hypotenuse. Then we can state that if h less than or equal to the leg opposite the angle A, then the needle crosses the thread. Let's draw a graph:

If we count for every needle thrown h And a and mark these points on the previous graph, the picture will be as follows:

Thus, the probability that the needle will cross the thread will be equal to the ratio of the area of ​​the figure under the graph to the area of ​​the rectangle, that is Pi, multiplied by the length of the needle.

From here we get the desired approximation of the number Pi, as the experience in the first part showed.

The plane is lined with parallel lines. The distance between any two adjacent straight lines is equal to 1. A needle of a fixed length falls onto a plane l (l ≤ 1).

Find the probability with which the needle intersects at least one of the lines (that is, it has common points with at least one of the lines).
We assume that the needle has no thickness (it is just a segment) and that it falls and lies flat on the plane, and does not stick into it.

Hint 1

What is meant by the probability of an event?

1. First, let's agree on what we mean by event. Let us conduct a series of identical experiments - tests, in each of which the same initial conditions are used and the result of the next test does not depend in any way on the results of the previous ones. Textbook examples: tossing a “perfect” coin, throwing a “perfect” dice. Or, as in our problem, throwing a needle onto a lined plane.

Each test has different elementary outcomes. For example, rolling a number from 1 to 6 in the dice example. Event some subset of the set of elementary outcomes is called. For example, “roll 2”. Or “rolling an odd number” (that is, rolling a 1, 3, or 5). You can consider more complex tests, such as tossing five coins. Here the elementary outcomes will be: “five heads fell”, “four heads and one tail fell”, and so on. As an event, we can consider, for example, the following: “at least three heads fell.”

In our problem, a test is one throwing of a needle, and the event we need is the intersection of at least one line.

2. Under probability of an event you can understand the ratio of the number of outcomes favorable for this event to the number of all possible outcomes (hence it turns out that probability is always a number from 0 to 1). For example, the probability of the event “rolling an odd number” when throwing one die is 1/2, because exactly half of all possible outcomes match. The probability of the event “at least three heads” when throwing 5 coins is also 1/2.

This definition of probability works well when the set of possible outcomes is finite. But in our problem there are infinitely many outcomes - the positions of the fallen needle. And there are also infinitely many suitable outcomes. How to be? Let’s adjust our “definition” a little: probability of an event- this is the share that favorable outcomes “occupy” in the set of all outcomes. With this “definition” it is already possible to calculate the probability required in the problem.

To be honest, everything said above is a “hands-on” explanation and cannot be considered with all mathematical rigor. But for our purposes this approach is quite sufficient.

3. Just one more example for clarity. Let's consider a square and connect the midpoints of two adjacent sides with a segment, thus cutting off a corner. After this, we will randomly poke the needle into the square. With what probability are we going to get inside the corner? Here, the outcome of each test is where the end of the needle lands, that is, one point inside the square. It is clear that there are infinitely many outcomes and that there are also infinitely many outcomes suitable for our event - getting into the corner. Therefore, it is already pointless to talk about the number of outcomes to calculate the probability. But the fraction can be calculated - it is simply the ratio of the areas of the corner and the square. It is equal to 1/8. Note that the boundaries of the figures have zero area, so you don’t have to think about them. In particular, the needle will hit the segment that cut off the corner with probability 0.

Hint 2

The last example from the first hint may give a hint of a possible way to solve the problem. It is necessary to enter parameters that would determine the position of the needle and allow us to describe all cases when it crosses the lines. Two parameters are quite enough here. After this, we need to understand what values ​​these parameters can take and what values ​​describe our event. If you choose the parameters well, then these conditions will be quite simple and you can even “depict” them: take a coordinate plane whose axes correspond to the parameters, and draw a region whose points satisfy the obtained conditions. After this, all that remains is to calculate the area of ​​the entire region and the area of ​​that part of it that corresponds to the intersection of the needle and the lines. And then find the ratio of these areas.

Solution

Let us agree that the straight lines from the condition go horizontally. So we threw the needle onto the plane. How to describe its location so that it is convenient to take into account the intersection with straight lines? Let us note a peculiar symmetry: it is not so important to us which stripe (or which, if there are two) stripes between the straight lines the needle will fall on - the stripes are all the same. It is also clear that horizontal shifts also have no effect. But what is really important is how “far” the needle lies from the straight lines and at what angle it is inclined to them. Therefore, as parameters from the second hint, you can take the angle of inclination α of the needle to the straight lines and the distance d from the middle of the needle to nearest straight (Fig. 1). Thus, we use another “symmetry” that arose in the problem.

What values ​​can these parameters take? The radian measure of angle α varies from 0 to π, and d takes values ​​from 0 (if the middle of the needle is on a straight line) to 1/2 (the middle of the needle cannot be further from a straight line). On the plane with coordinates (α, d) these restrictions define a rectangle (Fig. 2).

From Figure 3 it is clear under what conditions on α and d the needle intersects at least one straight line: the projection of half the needle in the direction perpendicular to the straight lines must be greater d. That is, the inequality must be satisfied.

So we have a description of all cases when the needle intersects at least one line (there will be an intersection with two lines only if the equalities α = π/2 and d= 1/2, which can give just one point in our rectangle - an infinite set of all possible values ​​of a pair of parameters). It remains to calculate the area under the sinusoid graph and divide it by the area of ​​the entire rectangle, which is equal to π/2 (Fig. 4).

As is known, the area under the graph of a function is equal to a certain integral of this function over the required interval: .

As a result, we find that the desired probability is equal to .

Afterword

It is believed that this problem was first posed and studied quite thoroughly by the 18th century French scientist Count de Buffon - a rather extraordinary person with a very wide range of interests, who did a lot of useful things in various fields of knowledge. Therefore, it is often called the Buffon's needle problem. Apparently, this was the first problem on the so-called geometric probability. As we have seen, the essence of this approach is to represent the set of elementary outcomes of some test in the form of a geometric figure and reduce the question of finding the probability of a particular event to calculating the ratio of the areas of suitable figures. In this way, you can solve several more fairly well-known problems - perhaps you will get acquainted with some of them later here on “Elements”. Therefore, we will present just one more simple task as an exercise:

With what probability is a round coin of diameter d, thrown onto a checkered plane (divided into unit squares), not covering any of the grid lines, that is, ending up entirely inside one of the squares?

Note that when solving Buffon's problem, one can reason a little differently. The course of such a decision is described in detail (though in English).

Now a little about the meaning of the answer we received. At l = 1 the answer is approximately 0.6366197... What exactly does this number represent? As usual, in probability theory this should be understood as follows. Let's say we did a very long series of tests. Let's say we had the patience to throw a needle a million times in each test and remember how many times it crossed straight lines on a plane. And we also conducted a million such tests. It turns out that in most of them (most likely, the overwhelming number) the number of intersections is close to 636,619. And the more such tests we conduct, the closer the proportion of successful outcomes (when the needle crossed the line) will be to. And in fact, of course, it doesn’t matter at all how you divide the tests into series - only the total number is important. In reality, there is not enough patience to conduct such a long series of tests. But you can write a program (or use existing ones like this one) that would perform routine operations and give only the number of intersections for a large number of throws.

What was said in the previous paragraph gives an unusual approach to the important problem of accurately calculating the number π = 3.1415926... Let us recall that this number is defined as the ratio of the length of a circle to its diameter (for all circles this ratio is the same). The number π is one of the main constants in mathematics and physics. This can be partly explained by the fact that circles and ellipses appear in mathematics and physics in a variety of problems and models - from purely geometric to practical ones such as calculations of the orbits of planets and satellites. Therefore, it is important to be able to accurately calculate the value of the number π. It is known that this number is irrational, that is, it cannot be represented as a rational fraction (the ratio of two integers), but there are fractions close to it with small denominators. Archimedes also knew that the fraction 22/7 = 3,(142,857) approximates π to within thousandths. Around the 5th century AD. e. the approximation 355/113 = 3.14159292... was already known - the error is less than one millionth.

What does Buffon's needle have to do with it? As we already understand, in a long series of tests, the proportion of intersections from the total number of needle throws will be approximately equal to 2/π. Therefore, we can empirically find this fraction and calculate an approximate value. The more throws, the more accurate the fraction will be, and therefore the value of π. In the 19th century there were heroes who were ready to spend several evenings on such an activity. They got different values ​​around 3.14. You can read more on this page on the English Wikipedia.

Now, of course, no one is throwing a needle, and the number π has already been calculated well beyond 10 trillion digits. It's funny that such precision is not nearly necessary for practical calculations - it is estimated that it is enough to know π to about the 40th decimal place to accurately calculate the volume of the visible Universe to within one atom. So calculating π with such accuracy is rather a race for records and a competition between supercomputers.

Exact calculations are based on different formulas. Basically, sequences converging to π and summation of series are used; many algorithms can be found on Wikipedia. Here we present only a wonderful formula

which allows you to calculate any digit of π without calculating the remaining digits.