动机
模拟把难以直接完成的计算,转成计算机可以重复进行的实验。复杂区域的积分也许难以解析求值,但抽取一点并计算函数值却可能很容易。计算机没有消除不确定性,而是把问题转成可以用概率分析误差的计算。要让大量输出有意义,必须先指定估计的对象,以及把输出与目标连接起来的假设。
三种误差需要分开。数学模型可能简化了研究对象;数值模拟器可能再以离散化近似该模型;最后,有限次 Monte Carlo 平均会在模拟器输出的期望附近波动。增加重复次数主要处理第三种误差,不能自动消除模型误差或离散偏差。即使平均值看来十分稳定,也可能稳定地估计了错的目标。
以单位区间上的积分为例,均匀取一点并计算函数,可把面积写成期望。不同机器可以各自完成多次重复,并用上一单元的摘要公式合并结果。然而,摘要的算术正确只是论证的一部分;各次重复还必须具有分析中指定的联合分布。若所有工作节点意外采用同一条随机序列,并行处理可能根本没有增加独立信息。
定义
设 在 上均匀分布。对可积函数 ,目标积分可写成 。
定义 2.1.1
(重复与普通 Monte Carlo 估计量)
设 是一次完整模拟重复的输出,且期望 存在。由 的独立同分布副本 组成普通 Monte Carlo 估计量:
定义 2.1.2
(无偏与均方误差)
若 ,称 的估计量 无偏。其均方误差是 。
有有限二阶矩时,均方误差等于方差加偏差的平方。无偏并不保证某一次结果接近真值;波动很小也不能排除相对于真正研究目标的系统偏移。
定义 2.1.3
(标准误及其估计)
若 的方差是有限的 , 的标准差称为标准误。当 时,用样本方差 估计它:
单次输出的标准差描述模拟结果的变动,标准误则描述其平均值的变动。除以 必须由独立性或其他适当理论支持,不能只因输出文件有 行便套用。
概念视角几何
样本方差是投影的长度平方
把输出写成 中的向量 ,其中 。残差 组成 ,而 是到与 垂直的超平面的正交投影。因此 。当 时,它的期望是 :分母数的正是拟合均值之后剩下的维数。
定义 2.1.4
(置信程序与覆盖率)
置信程序是由数据产生随机区间的规则。其覆盖率是在假设成立时重复应用该规则、区间包含目标的概率。
覆盖率不是单靠频率派论证就能事后赋予固定参数的概率。我们先推导有限样本界,再区分它与正态近似。
定义 2.1.5
(可重现性)
若指定的计算输入及运行选择足以让计算重做并得到相同结果,称模拟可重现。
种子只是其中一项;还可能需要生成器算法、函数库版本、随机流分配、模型参数、样本数及归约次序。确定性的伪随机序列并不真的是无限个独立随机变量。概率分析是良好模拟程序的数学模型,实际使用仍要检查生成器及抽样实现是否合适。
定理 / 命题
定理 2.1.6
(独立重复的均值与方差)
设 独立同分布,均值为 、有限方差为 ,且 预先固定。则
若 ,样本方差满足 。
命题 2.1.7
(有限样本的误差保证)
在相同假设下,任意 都有
若已知确定的有效界 ,且 ,选取 ,可保证误差小于 的概率至少为 。此界可能保守;把随机样本方差直接代替 ,不会自动保留这项保证。
证明思路
证明
(展开中心化总和及样本方差恒等式)
期望的线性性给出无偏,这一步不需要独立。计算方差时,把每项减去均值,再展开总和的平方。独立性令不同项的交叉期望为零,剩下 个 ,除以 后得到 。估计量无偏,所以均方误差等于它的方差。
样本方差则用恒等式:
右方两项的期望分别是 与 ,故相减后除以 即得结论。这也解释为何样本方差的分母与观测记录的描述性方差不同。
证明透视
独立性在哪里用到,在哪里不用
的无偏性只用到线性性,所以重复之间无论怎样相依都仍成立。独立性只在一处用到:展开 的平方后有 个交叉项 ,要靠不相关才全部为零。样本方差这一步再次用到这个方差公式,即 。恒等式本身是确定性的代数,因此分母 恰好来自从 中减去一个 。
概率界只需要刚证明的方差公式。
证明
(对平方误差应用 Markov 不等式)
再对非负变量 使用 Markov 不等式。其期望是 ,而误差至少为 的事件,迫使平方误差至少为 。这就是此处的 Chebyshev 界。样本数公式只是移项;若方差为正,任何有限样本数都不能使这个界变为零。若要求确定性的零误差,需要另一种论证。
独立同分布且有正的有限方差时,中心极限定理还说明标准化平均渐近服从标准正态。它支持以约 个估计标准误形成名义 区间,但这是渐近近似,并非上述有限样本界的直接结论。高度偏斜、罕见事件及小样本都可能令近似很差。
例题详解
例题 2.1.8
(平方积分与预算规划)
令 。积分得到 、,故 。 时,标准误为 。由于它按 缩小,要减半就需四倍独立重复。
若要求绝对误差小于 、失败概率不超过 ,有限样本界要求 ,故 次足够。这里用的是教学例子已知的真实方差。实际问题中,先导实验可协助规划,但先导样本方差本身不是确定上界。若只知道 ,可用有效界 ,得到较保守的 次预算。
例题 2.1.9
(罕见事件与看似完美的输出)
令 是概率 的事件指示变量。方差为 。取 ,比例的标准误为 。Chebyshev 界说绝对误差至少 的概率不超过 。若正态近似合适,名义区间半宽约为 ;两者属不同类型的结论。
改成 ,一万次独立试验完全没有事件的概率是 ,约 。这时观测样本方差是零,但不能报告零不确定性;实验没有证明事件不可能发生。抽样预算必须足以分辨目标的尺度,尤其在要求相对精度时。
例题 2.1.10
(对偶配对与公平的成本比较)
每次抽一个 ,改用 。由于 与 都均匀分布,均值仍是 。化简得 ,对其平方积分后减去 ,得到方差 。
同样有 次函数求值预算时,普通方法平均 个独立输出,方差为 。对偶方法平均 个独立配对输出,方差为 ,小八倍。每对内部刻意相依,不同对之间则必须独立。比较时要计函数求值数,不能只计平均的项数;若配对有额外开销,实际时间效率还需另行测量。
对偶法并非必然改善。若 ,便有 ,每对只是重复同一数值。在固定求值预算下,相对于独立抽样浪费了一次求值。改善与否取决于所选函数能否产生有利的负协方差。
常见错误
反例模式
长输出文件不等于大独立样本
错误说法是:平均 个输出,方差总会除以 。抽一次有正的有限方差的 ,然后令所有 。每项边际分布都正确,但平均仍是 ,任何 的方差都一样。一般平均的方差还包含交叉协方差。修正说法必须加入独立性,或另有明确控制相依性的分析。各节点重用完全相同的随机流,就可能在程序中造成此问题。
常见错误
(把固定种子或相邻种子当作独立性的证明)
固定种子只能证明可重做,不能证明无偏、独立或准确。并行计算应使用有记录的子随机流分配方案,或生成器支持的独立随机流功能。选取相邻整数种子本身不是随机流相互独立的证明。每个节点负责哪些重复索引也应有记录,并确保重试不会多接纳结果,或选择性丢弃难以完成的输出。
常见错误
(区间看来够好便停止)
当估计区间“已经够窄”就停止,也改变了程序。固定 的定理不能自动用于依数据决定的停止时间。此处应预先决定预算,或改用本身具有效保证的序贯方法。先导实验也要清楚标示,说明它怎样影响最终估计量的设计。
总结
Monte Carlo 的准确度取决于完整重复的分布及各重复之间的关系。无偏性、方差与可重现性回答不同问题。有限方差给出平方根样本数的误差尺度及保守有限样本界。方差缩减应按相同计算预算比较;模型误差与离散误差则要另外分析。
练习
练习 2.1.11
(设 。求期望及方差;取 ,用 Chebyshev 不等式估计样本平均偏离目标至少 的概率上界。)
基础
解答 · 答案
由 、,得期望 、方差 。样本平均的方差为 ,故概率不超过 。这是上界,不是等式,也不是正态近似的概率。
练习 2.1.12
( 次独立重复的标准误是 。输出分布不变时,要降到 需要多少次?指出这种缩放不能处理什么。)
基础
解答 · 答案
目标标准误是原来的四分之一,按 规律需要十六倍次数,即 。这不能修正模型误差、离散偏差、实现中引入的相依性,也不能忽略输出方差改变的情况。
练习 2.1.13
(对 构造对偶配对输出,求其方差并与两次独立求值比较。为什么此例不能建立对所有被积函数都成立的规则?)
核心
解答 · 答案
配对平均恒等于 ,方差为零。两次独立均匀求值的平均方差则是 。精确抵消利用了函数的线性以及两个自变量之和固定。对称函数如 的两个输出相同,不会有这种抵消。
练习 2.1.14
(四个节点各自重用相同的 个独立数学输出,归约器平均全部 个记录。用单次方差 表示估计量方差,并指出有助于发现问题的重现记录。)
核心
解答 · 答案
每个不同输出出现四次,记录平均等于最初 个输出的平均,方差为 ,而非 。应记录每个节点的生成器算法、种子或随机流标识、重复索引范围、样本数及分配规则。重复的随机流与索引范围能暴露问题;仅改动最终归约树不能修复相依性。