Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

preface

Hello! Friend!!!

Thank you very much for reading haihong’s article, if there are any mistakes in the article, please point out ~

Self-introduction ଘ(੭, ᵕ)੭

Nickname: Haihong

Tag: programmer monkey | C++ contestant | student

Introduction: because of C language to get acquainted with programming, then transferred to the computer major, had the honor to get some national awards, provincial awards… Has been confirmed. Currently learning C++/Linux/Python

Learning experience: solid foundation + more notes + more code + more thinking + learn English well!

Little White stage of learning Python

The article is only used as my own study notes for the establishment of knowledge system and review

The problem is not to learn one more question to understand one more question

Know what is, know why!

1. Monte Carlo algorithm

What is the Monte Carlo algorithm?

Monte Carlo method (Monte Carlo Method), also known as statistical simulation method, is in the mid-1940s due to the development of science and technology and the invention of electronic computer, and was put forward a kind of probability statistics theory as the guidance of a very important numerical calculation method. A method of using random numbers (or, more commonly, pseudo-random numbers) to solve many computational problems.

Origin:

The Monte Carlo method was developed in the 1940s by S.M., a member of the Manhattan Project, which developed the atomic bomb in the United States during World War II. First proposed by Ulam and J. von Neumann. Mathematician Von Neumann gave the method a mysterious name after Monte Carlo of Monaco, the world’s most famous casino. The monte Carlo method is generally recognized as the origin of the French mathematician Buffon in 1777 proposed to use the needle experiment method to find PI.

Basic idea:

When the problem to be solved is the probability of the occurrence of a certain random event, or the expected value of a random variable, the probability of the occurrence of the event is estimated by the frequency of the occurrence of the event through some “experimental” method, or some digital features of the random variable are obtained and taken as the solution of the problem.

Working steps:

Construct or describe probabilistic processes
Implement sampling from known probability distributions
Set up various estimators

Sample 1

Title: Classical Monte Carlo method for finding PI

Basic idea: generate enough random number points in the area of the graph, and then calculate the ratio of the number of points falling in the circle to the total number multiplied by 4, which is PI.

The Demo code(When the number of simulations is 10000)

import math
import random
m = 10000
n = 0
for i in range(m):
	# x and y are random numbers between 0 and 1
    x = random.random()
    y = random.random()
    # If the point (x,y) belongs to the 1/4 circle in the figure, the valid number +1
    if math.sqrt(x**2 + y**2) < 1:
        n += 1
# to calculate PI
pi = 4 * n / m
print("pi = {}".format(pi))

# PI = 3.1508 (random results may not be identical)
Copy the code

Demo code (with 1,000,000 simulations)

import math
import random
m = 1000000
n = 0
for i in range(m):
    x = random.random()
    y = random.random()
    if math.sqrt(x**2 + y**2) < 1:
        n += 1
pi = 4 * n / m
print("pi = {}".format(pi))

# pi = 3.141416
Copy the code

The sample 2

Compute the definite integral of y=x2y =x ^2y=x2 over the interval [0,1] using python

The Demo code

import math
import random
m = 1000000
n = 0
for i in range(m):
    x = random.random()
    y = random.random()
    if y >= x**2:
        n += 1
r = n / m
print("r = {}".format(r))

# r = 0.666817
Copy the code

Variant: Compute the integral

Title source: blog.csdn.net/FightingBob…

Theoretical answer: π8ln2\frac{\ PI}{8}ln28πln2

First draw the function image:

import numpy as np
import matplotlib.pylab as plt
x = np.linspace(0.1,num=50)
y = np.log(1 + x) / (1 + x**2)
plt.plot(x,y,The '-')
Copy the code

The function image is as follows:

Calculation of integral

import numpy as np
import random
m = 100000
n = 0
for i in range(m):
    x = random.random()
    y = random.random()
    if np.log(1 + x) / (1 + x**2) > y:
        n += 1
ans = n / m
ans

# 0.27293
PI /8*log(2) = 0.2721983
Copy the code

Sample 3

There is now a project with three WBS elements: design, build, and test. It is assumed that the probability distribution of the estimated duration of the three WBS elements is a standard normal distribution, and the logical relationship between the three elements is from completion to start, so the duration of the whole project is the sum of the duration of the three WBS elements.First, draw the probability density functions of these three elements

It can be seen from the table that the minimum time is 8 days and the maximum time is 34 days, so we set the time range to 7-35 days

import numpy as np
import matplotlib.pyplot as plt
import math
 
 
def normal_distribution(x, mean, sigma) :
    return np.exp(-1*((x-mean)**2)/(2*(sigma**2)))/(math.sqrt(2*np.pi) * sigma)
 
 
mean1, sigma1 = 14.2
x1 = np.linspace(7.35,num=100)
 
mean2, sigma2 = 23.3
x2 = np.linspace(7.35, num=100)
 
mean3, sigma3 =22.4
x3 = np.linspace(7.35, num=100)
 
y1 = normal_distribution(x1, mean1, sigma1)
y2 = normal_distribution(x2, mean2, sigma2)
y3 = normal_distribution(x3, mean3, sigma3)
 
plt.plot(x1, y1, 'r', label='m=14,sig=2')
plt.plot(x2, y2, 'g', label='m=23,sig=3')
plt.plot(x3, y3, 'b', label='m=22,sig=4')
plt.legend()
plt.grid()
plt.show()
Copy the code

The image is as follows:The Demo code

import numpy as np
import matplotlib.pylab  as plt
import random
import math

m = 10000
a = 0
b = 0
y1 = np.random.normal(loc=14,scale=2,size=m)
y2 = np.random.normal(loc=23,scale=3,size=m)
y3 = np.random.normal(loc=22,scale=4,size=m)
y =y1 + y2 + y3
a,b = np.mean(y),np.var(y)
a,b

# (59.08396232409535, 29.120136564111085)
The theoretical mean is 59 = 14 + 23 + 22 and the variance is 29 = 2*2 + 3*3 + 4*4
Copy the code

2, the three door problem

Three problems

The Monty Hall Probelm problem, also known as the Monty Hall Probelm problem, comes from Let’s Make a Deal. Contestants are shown three closed doors, one of which has a car behind it. The door with the car behind it wins the car. The other two doors each hide a goat. When the contestants chose a door but did not open it, the host opened one of the two remaining doors, revealing one of the goats. The host then asked the contestants if they wanted another door, which was still closed. The question is: Would switching to a different door increase the contestant’s chances of winning the car? If, strictly speaking, the presenter knows that sheep are behind the door he opens, the answer is yes. If you don’t change the door, you have a 1/3 chance of winning the car, if you change the door, you have a 2/3 chance of winning the car.

Application of monte Carlo’s idea

Monte Carlo application focuses on the use of random numbers to simulate the problem of winning rate similar to gambling problem, and through multiple simulations to get the simulation value of the value to be calculated. In the three-door problem, 0, 1 and 2 points are used to represent the number of the three doors, an integer is randomly generated between [0,2] to represent the number of the door where the prize is located, and an integer is randomly generated between [0,2] again to represent the number of the door chosen by the contestant. Use the variable change to represent changing doors (true) and not changing doors (false) in the game.

Monte Carlo processThe Demo code

import math
def play(change) :
    prize = random.randint(0.2)
    guess = random.randint(0.2)
    if guess == prize:
        if change:
            return False
        else:
            return True
    else:
        if change:
            return True
        else:
            return False
def winRate(change, N) :
    win = 0
    for i in range(N):
        if(play(change)):
            win += 1
    print("The winning percentage is {}".format(win / N))
N = 1000000
print("Probability of winning every door change:")
winRate(True,N) 
print("Probability of winning by not changing the door every time:")
winRate(False,N)

# Theory change door 2/3 do not change door 1/3
# Probability of winning every door change:
The winning rate is 0.665769
# Probability of winning without changing the door every time:
# The winning rate is 0.33292
Copy the code

The results

3. M*M bean problem

M*M bean Bayesian statistical problem

M&M’s are candy chocolate beans that come in various colors. Mars, the company that makes M&Ms, changes the mix from time to time. In 1995, they introduced blue M&Ms. In a normal bag of M&M’s, the colors were 30% brown, 20% yellow, 20% red, 10% green, 10% orange, and 10% tan. This later became: 24% blue, 20% green, 16% orange, 14% yellow, 13% red, and 13% brown. Suppose a friend of mine has two bags of M&M’s. He tells me that one bag is from 1994 and one bag is from 1996. But he didn’t tell me exactly what year the bag was from. He gave me an M&M from each bag. One is yellow and the other is green. So what’s the probability that the yellow beans came from a 1994 bag?

The Demo code

import time
import random
for i in range(10) :print(time.strftime("%Y-%m-%d %X",time.localtime()))
    dou = {1994: {'brown':30.'yellow':20.'red':20.'green':10.'orange':10.'the browns':30},
           1996: {'blue':24.'green':20.'orange':16.'yellow':14.'red':13.'brown':13}}
    num = 10000
    list_1994 = ['brown'] *30*num+['yellow'] *20*num+['red'] *20*num+['green'] *10*num+['orange'] *10*num+['the browns'] *10*num
    list_1996 = ['blue'] *24*num+['green'] *20*num+['orange'] *16*num+['yellow'] *14*num+['red'] *13*num+['brown'] *13*num
    random.shuffle(list_1994)
    random.shuffle(list_1996)
    count_all = 0
    count_key = 0
    for key in range(100 * num):
        if list_1994[key] == 'yellow' and list_1996[key] == 'green':
            count_all += 1
            count_key += 1
        if list_1994[key] == 'green' and list_1996[key] == 'yellow':
            count_all += 1
    print(count_key / count_all,20/27)
    print(time.strftime("%Y-%m-%d %X",time.localtime()))
    
    #...
    # 0.7407064573459715 0.7407407407407407
    # 20/27 is the theoretical answer
Copy the code

The results

conclusion

Source of learning: STATION B and its classroom PPT, the code is reproduced

The essay is just a study note, recording a process from 0 to 1

Hope to help you, if there is a mistake welcome small partners to correct ~

I am haihong ଘ(੭, ᵕ)੭

If you think it’s ok, please give it a thumbs up

Thanks for your support ❤️

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Python Mathematical Modeling series 6: Monte Carlo algorithms

preface

1. Monte Carlo algorithm

Sample 1

The sample 2

Sample 3

2, the three door problem

3. M*M bean problem

conclusion

Python Mathematical Modeling series 6: Monte Carlo algorithms

preface

1. Monte Carlo algorithm

Sample 1

The sample 2

Sample 3

2, the three door problem

3. M*M bean problem

conclusion

Related Posts

Data structures and algorithms – Recursive processing of the eight Queens problem

@enableAutoConfiguration Processing logic

Java concurrency based in August (a) | more challenges