蒙特卡罗方法和随机数

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是20世纪40年代中期随着科学技术的发展和电子计算机的发明而提出的一类重要的数值计算方法。

它是指使用随机数（更常见的是伪随机数）来解决计算问题的一类方法，与之对应的是确定性算法。蒙特卡罗方法在金融工程、宏观经济学、计算物理学等领域都有广泛应用。

蒙特卡罗方法最典型的应用之一就是求圆周率 π。

如图，在坐标系中有一个以 (0,0) 为圆心、半径为 1 的圆，再画一个边长为 2 的正方形，使圆内切于正方形。

在第一象限中，正方形的面积为：

1 × 1 = 1

而四分之一圆的面积为：

π × 1 × 1 ÷ 4 = π / 4

根据统计学原理，如果从 (0,0) 到 (1,1) 的区域中随机取 N 个点，那么最终落在圆内的点数与随机点总数的比例应该接近它们的面积比例，也就是 π / 4。

随机点越多，计算结果通常就越接近 π。

因此，求 π 的程序可以如下：

#!/usr/bin/env python

import random
import math

def getpi(count):
    i = 0
    k = 0.0

    while i < count:
        x = random.random()
        y = random.random()

        if math.sqrt(x*x + y*y) < 1:
            k += 1

        i += 1

    return k / (count * 0.25)

利用上面的函数，以不同的采样点数量计算圆周率，分别得到以下结果：

可以看到，随着采样点数量增加，计算结果总体上越来越接近实际值。这也体现了蒙特卡罗方法的基本特点：通过大量随机采样，用统计结果逼近实际结果。

第二个例子是求抛物线的面积。

要求函数 y=x²、x 轴和 x=1 所围成的面积。

传统的方法是利用微积分：

也可以利用蒙特卡罗方法进行计算。

在 0 ≤ x ≤ 1、0 ≤ y ≤ 1 的正方形区域内随机生成大量点，如果随机点满足：

y < x²

那么这个点就位于曲线 y=x² 的下方。

#!/usr/bin/env python

import random

def getarea(count):
    i = 0
    k = 0.0

    while i < count:
        x = random.random()
        y = random.random()

        if y < x*x:
            k += 1

        i += 1

    return k / count

不同的采样数量最终得到如下结果：

理论上的结果为：

1 / 3 ≈ 0.333333333

可以看到，随着采样数量增加，结果也逐渐接近理论值。

随机数

上面两个例子中，蒙特卡罗方法的关键就是生成大量随机数，并对随机结果进行统计。

因此，随机数的质量就非常重要。对于需要进行统计模拟的随机数来说，一个重要特点就是分布应该尽可能符合预期。

这里用下面的程序生成大量随机点，并观察其分布：

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import matplotlib.pyplot as plt
import random

def showpic(count):
    i = 0

    while i < count:
        x = random.random()
        y = random.random()

        plt.scatter(x, y, s=5, alpha=0.6)

        i += 1

    plt.show()

得到随机点分布图：

可以看到，随机点整体上呈现比较均匀的分布。

我们知道，随机数可以大致分为真随机数和伪随机数。

真随机数通常利用现实世界中难以预测的物理事件产生，例如某些硬件噪声、采样时间等。伪随机数则由确定性的算法生成，只要初始状态相同，就可以生成相同的序列。

Linux 中的 /dev/random 和 /dev/urandom 都可以提供随机数据，它们主要利用系统收集的熵来提供随机性，但在行为和使用场景上有所区别。

在实际应用中，如果对安全性要求较高，例如密码、密钥等场景，需要使用适合密码学用途的安全随机数；如果主要用于模拟、计算等场景，通常使用普通的伪随机数生成器即可。

对于一个用于统计模拟的伪随机数算法来说，通常希望它具有较好的统计特性，例如：

1. 随机序列的分布具有较好的均匀性；
2. 不同样本之间具有较低的相关性；
3. 长序列中不应该出现明显的周期性和异常模式；
4. 在实际应用允许的范围内，尽量避免从输出序列轻易预测出内部状态。

目前常见的伪随机数算法包括线性同余法、移位寄存器以及梅森旋转算法等。

从蒙特卡罗方法可以看到，随机数并不是简单地产生一些“看起来随机”的数字。随机数的统计特性会直接影响最终的计算结果，而蒙特卡罗方法本质上也是利用大量随机样本去逼近一个确定的结果。

参考资料

1. 蒙特卡洛方法
2. 蒙特卡罗方法入门
3. 如何评价一个伪随机数生成算法的优劣
4. Pseudo-Random vs. True Random
5. Random number generation
6. 伪随机性