蒙特卡洛方法探索

需积分: 9 162 浏览量更新于2024-07-31 收藏 2.28MB PDF 举报

"Explorations in Monte Carlo Methods" 是一本由Ronald W. Shonkwiler和Franklin Mendivil合著的书籍，两位作者都在Monte Carlo算法领域有深厚的造诣。这本书是Undergraduate Texts in Mathematics系列的一部分，由Springer出版社出版。蒙特卡洛方法（Monte Carlo Methods）是一种基于随机抽样或统计试验的计算技术，广泛应用于各种科学和工程问题，特别是在解决高维度复杂问题时展现出其独特优势。这本书旨在向本科生和研究生介绍这一强大的计算工具。书中可能涵盖了以下几个核心知识点： 1. **基本概念**：介绍Monte Carlo方法的基本原理，包括随机变量、概率分布和统计抽样的概念，以及如何利用随机性来解决问题。 2. **应用领域**：阐述Monte Carlo方法在物理、工程、经济学、金融学、计算机图形学、统计物理、量子力学等多个领域的应用实例。 3. **算法设计**：详细讲解如何设计和实现Monte Carlo算法，包括随机数生成、模拟方法如 Importance Sampling 和 Markov Chain Monte Carlo (MCMC)。 4. **收敛性与误差分析**：讨论Monte Carlo方法的收敛速度和误差估计，以及如何通过增加样本数量来提高结果的精度。 5. **案例研究**：通过具体的问题，如计算圆周率、期权定价、求解偏微分方程等，深入浅出地展示Monte Carlo方法的实际应用。 6. **高级主题**：可能涉及更复杂的Monte Carlo技术，如Metropolis-Hastings算法、Gibbs采样、模拟退火等，以及在复杂系统模拟中的应用。 7. **编程实践**：鼓励读者通过编程实践来加深理解，可能会提供Python、Matlab或其他编程语言的代码示例。 8. **数学工具**：书中可能涵盖了一些必要的数学背景知识，如概率论、统计推断和随机过程，以帮助读者更好地理解和应用Monte Carlo方法。 9. **学术资源**：书后的参考文献和在线资源链接，为读者提供了进一步研究和学习的路径。这本教材不仅适合数学、计算机科学和工程专业的学生，也对任何需要处理复杂计算问题的科研工作者具有很高的参考价值。通过深入学习，读者将能够掌握如何利用Monte Carlo方法解决实际问题，并具备独立设计和评估Monte Carlo模拟的能力。

4 1 Introduction to Monte Carlo Methods

realized that the computer was exactly the tool needed for these simu-

lations, thereby saving we eks of manual labor. Of course, there was still

the problem of generating the required random numbers. In fact, von

Neumann proposed solving this problem in an insightful way, by the

use of the digital computer itself, and created the ﬁrst pseudorandom

number generator, the “middle-square” generator.

Follo wing this lead, w e will perform Buﬀon’s needle experiment by

computer simulation. A convenien t choice for the parameters is d =2

and L = 1. The program generates two random numbers, one to play

the role of X,0≤ X<d/2, and the other of Θ,0≤ Θ<π/2. Next we

calculate whether X ≤

sin Θ and record a hit if so. Repeating this n

times, π is estimated as n/H

.Fornow,taken =10,000.

Keep in mind that the purpose of this exercise is to get started

in Monte Carlo methods and not to determine π, a value w e already

know. In fact, we need the value of π to generate the random values of Θ

needed in our Buﬀon needle simulation. For a Monte Carlo simulation

that estimates π ab initio, see Section 1.4.

Here is the program written in Matlab. We rely on Matlab for the

random numb er generation and the comparison. Matlab can also graph

the results in the form of a histogram. Histogramming is one of our main

analytical tools and we will discuss it shortly.

Matlab

> throws = 10000; % percent makes the rest of the line a comment

> x=rand(1,throws); % a vector of 10000 pseudorandom numbers in the range [0,1)

> theta=rand(1,throws); % semicolon supresses printing

> theta=0.5*pi*theta; % theta now 10000 random numbers between 0 and π/2

> hits= x<=0.5*sin(theta); % hits is a vector of 0’s where false and 1’s where true

> sum(hits) % no semicolon prints the number of hits out of the 10000 thro ws

> piEst=throws/sum(hits)

1.1.2 Histogramming Simulation Results

In running our Buﬀon needle simulation we obtain a single number,

an estimate for π. Is it too high, too low, close to the correct value,

ho w close? We don’t know (continuing our assumption that π is not

known in advance). But there is a way to answer these questions; it is

by running multiple exp eriments and histogramming the results.

A histogram is a special kind of bar chart for depicting a series of

values, v

, v

, ..., v

, numbering, say, n in total. A convenient sub-

division of the x-axis is created containing the values, for example by

means of the points x

, x

, ..., x

. They establish intervals, or bins,

1.1 How Can Random Numbers Solve Problems? 5

), [x

), ...,[x

K−1

). A count is made of how many of the

values lie in each bin and a b ar of that height is depicted standing on

that bin. Technically this is called a frequency histogram. Dividing the

frequencies by n, the total numb er of values, calculates the relative fre-

quencies. Making the heights equal to these values generates a density

histogram. A densit y histogram is an approximation to the probabilistic

distribution of the process the values represent. We take up the idea of

probability distribution in the next section.

Let us modify our Buﬀon needle program to produce a histogram.

For technical reasons, this time we make an estimate of 1/π.Therea-

son has to do with the fact that we want the random variable to be

in the numerator rather than the denominator. Therefore we estimate

1/π =0.318309 ... using 100 trials of the basic experiment. But in ad-

dition, consider an experiment consisting of these basic experiments,

let’s call it the “super experiment.” We perform 2000 such super ex-

perimen ts and histogram these data. Altogether we will be performing

two hundred thousand simulated needle tosses. The resulting histogram

can be used to provide probabilistic accuracy statements about the es-

timated value of π.

Figure 1.3 shows the resulting histogram produced by the Matlab

program below. We see that it has the bell shape of a normal distribu-

tion, a topic we take up in Section 2.6. The average of the 2000 super

experiments is an approximation of the mean of the distribution and

is likewise an approximation of 1/π. For the run shown in Figure 1.3

the average is ¯p =0.3180.

The width of a normal distribution is determined by a parame-

ter called the standard deviation. The standard deviation for the run

shown is s =0.0467. A property of the normal distribution is that the

probability that a sample drawn from it falls between two standard

deviations on either side of the mean is 0.954. Hence a single sample

usually lies between 0.3180−2·0.0467 and 0.3180+2·0.0467. For the av-

erage of 2000 samples, the interval shrinks to 2·0.0467/

√

2000 = 0.0021

on either side of the mean. Finally, since an interval centered on the

true mean will contain a sample mean if and only if the same interval

cen tered on the sample mean contains the true mean, we can say

probabilit y that (0.3180 − 0.0021 < 1/π < 0.3180 + 0.0021) = 0.954.

In other words, only about 5% of the time will this experiment pro duce

an interval of width 0.0042 = 2 · 0.0021 that fails to contain 1/π.

For π itself, just reciprocate the inequalities,

8 1 Introduction to Monte Carlo Methods

In the upper left and right of Figure 1.4 are plotted the histograms

of 1,000 simulated rolls of a “red” and a “green” die. One sees that the

outcomes are about evenly distributed among the numbers 1 through

6. The histogram of their sum is plotted in the lower left. As one can

see, even for 1,00 trials, the results can be far from the expected prob-

abilities. The histogram for 10,000 trials is plotted in the lower right.

These are much closer to the expected results.

Sometimes the outcomes of an experiment do not fall on nice integer

values; for example, consider measuring the circumference of hen’s eggs

pro duced by the chickens on a farm. In such a case, we must artiﬁcially

create a subdivision of the range of possible outcomes, the bins. Now for

each instance of the experiment we must determine into whic h bin the

outcome falls and add 1 to the frequency count for that bin. Looking

back on the dice-rolling experiment, w e see that we did exactly the same

thing, only the bins were naturally arranged by the discrete nature of

the outcomes.

After conducting a large number of trials and recording the bin

frequencies, we depict the results as before by plotting bars lying over

each bin of height equal to its frequency. This time the width of the

bar will be that of the bin. To obtain a density histogram, the total

area under the bars must sum to 1. Therefore the frequencies must be

scaled, each multiplied by a constant c, to satisfy the equation



i=1

(∆

x),

where K is the total number of bins, f

is the frequency count of the

ith bin, and ∆

x is the ith bin width. Solving for c, the frequencies

must be scaled by

c =



(∆

1.1.3 Sample Paths

Another method of portraying the results of a run of an experiment

is to plot its sample path. Suppose the outcome on the ith trial of the

experiment is R

. The sample path is a plot of the pairs (i, R

)for

i =1, 2,...,n,wheren is the number of trials.

To illustrate, consider a gambling experiment in which a gam bler

makes $1 bets against the house. Suppose the winning chances are

剩余248页未读，继续阅读

Bridgezhou

粉丝: 0
资源: 1

蒙特卡洛方法探索

Explorations in Monte Carlo Methods-蒙特卡罗基础

Introduction to Computing Explorations in Language Logic and Machines

Explorations in Quantum Computing

Explorations in Harmonic Analysis

space in language and cognition: explorations in cognitive diversity

贤者代数图论的探索Explorations in Algebraic Graph Theory with Sage

计算入门-语言，逻辑和机器探索Introduction to Computing - Explorations in Language, Logic, and Machines

Explorations of plant cell cultures in experimental teaching of biotechnology (2014年)

Programming Language Explorations

chipwhisperer-explorations

最新资源