Monte Carlo方法的常用方差缩减技术

那么在第二节第二部分中我们介绍了Monte Carlo算法的逻辑和简易实现。正如我们介绍的，这个算法的逼近误差减小速度为。也就是说，要提升N倍的效率，我们需要　N2倍的运算次数。虽然计算机计算的很快，但是这个计算数量增长的速度也未免太快了。

对于大规模计算技术成熟的今天来说，算力是廉价的，但是我们也不可能无限次使用。因此，如果我们拥有一种减小方差的技术，使得同样的计算次数我们能够得到更小的误差，从而提高运算效率，那就会大大优化整个算法的资源消耗，使之更加经济。在本章中，我们会介绍一种适合Monte Carlo方法的方差缩减技术——对偶变量法。

所谓对偶变量法指的是在分布中先生成了一个分位点为q的随机变量查找（1）q−的分位点，作为下一个随机变量的取值。这样的话，只需要生成M　/2个随机数而不是M个，在原理上可以减少一半的随机数运算量。比方说，一个M=10 000的生成随机数任务，使用这种方式，我们就可以减少到只需要生成M=5 000个随机数。

那么在偷了一半的懒以后，我们误差会发生什么样的变化呢？

可见，根据中心极限定律，我们复制了一个对偶变量以后，我们的误差和之前是完全一样的。

原则上来说，这个方法可以减少20％～40％的运行时间和内存消耗。因为生成随机数一般而言在计算机内部是采取Box-Muller算法求解反函数，显然直接使用对偶变量可以跳过这一步直接得到随机变量取值，大大降低了内存消耗和计算量。但是由于在整个随机路径上还有其他的运算，因此我们无法做到减少50％的运算量。经验数据而言，就是刚才所说的，减少20％～40％的运算量。(www.xing528.com)

那么从数学上来说，为什么我们可以只用一半的样本，就能够达到和之前完全一样的精确程度呢？或者说，我用相同的样本数量，可以达到比之前更低的方差，为什么我们的方差被缩减了呢？

我们用正态分布来作为一个例子进行解释，我们把随机变量样本分成了两组，原变量组和对偶变量组，根据概率论基本计算法则，我们有：

由于我们知道　ZZ−和　是完全对称的，自然而然我们可以得到一个负的相关性：

这将会使得以下不等式成立：

上述不等式中，左侧为对偶变量法导致的方差，而右侧为不做对偶变量法导致的方差。这就是对偶变量法会缩减方差的数学理论依据。