动机
一个数值积分或期望可能难以精确计算,但容易产生单个随机样本。Monte Carlo 估计用模拟值的平均数代替期望。这个平均数本身是随机的:再次运行相同算法,通常会得到不同结果。因此分析应说明估计的目标是什么,以及指定大小的误差有多大概率发生。
几种保证需要区分。无偏性讨论假想的重复运行中估计量的均值;大数定律讨论样本量增长时的极限;有限样本界控制指定样本量下的误差概率。在任意抽样条件下,它们不能自动相互推出。特别地,平均带来的方差下降取决于模拟结果的依赖结构,而不只是程序输出了多少个数值。
从均匀随机数构造目标分布
估计量需要来自所选分布的样本,单有期望的公式还不够。一个基本构造从 上理想的均匀随机变量 出发。设 为累积分布函数:它不递减、右连续,在负无穷与正无穷处的极限分别为零和一。对 定义其广义逆
这个集合非空且有下界,所以 有限。在该集合中选取递减趋于下确界的点列,由右连续性得 。于是对每个实数 ,
正向由 的单调性得出;反向则因为此时 属于定义下确界的集合。因此
所以 服从目标分布,即使 有跳跃或平坦区间也成立。证明不要求密度或严格递增。若把同一个确定性函数 分别作用于独立的均匀变量 ,所得变量仍然独立同分布;这就连接到下文的独立样本公式。
例题 9.1.1
(指数分布与离散分布的抽样)
当 时,指数分布在 有 ,在 有 。解方程 得 。例如 给出 。
另一个离散变量取值 ,概率分别为 ,累积概率为 。当 返回 ,当 返回 ,当 返回 。各区间的长度恰是所需概率。阶梯函数没有普通的一一反函数;广义逆使这个构造仍然有效。
证明使用理想连续均匀变量和精确运算。计算机提供的是有限集合上的伪随机值,并非真正独立的连续变量;端点约定也很重要。指数公式中 会要求计算 ,而有限网格不能精确表示无界尾部。固定伪随机种子可以重现一次运行,但本身不能证明独立性或给出 Monte Carlo 误差界。应查阅实际生成器的取值范围,并判断它是否适合计算。
快速检查
(目标变量以概率 取 、以概率 取 。给出由均匀变量 得到它的变换,并求目标变量的期望。)
把 的区间与累积概率对照。
解答 · 答案
当 返回 ,否则返回 。期望为 。这是理想构造的分布结论,并非对单次有限网格实现的保证。
快速检查
(若指数分布的速率为 ,变换 在 处返回什么?)
取 代入 。
解答 · 答案
,这正是该分布的中位数。
定义
定义 9.1.2
(Monte Carlo 估计量与方差)
令 为独立同分布实随机变量,具有有限均值 。对整数 ,Monte Carlo 估计量为
若 ,记 。由独立性,
最后一个量是均方根误差,并非单次运行的确定性误差界。两两协方差为零也足以得到这里的方差公式,但下文强大数定律和 Hoeffding 界的证明使用独立性。
概率密度 下的期望就是积分:若 ,可独立抽取 并取 。在随机游走计算中,一个 也可以是整条模拟路径的函数;此时上式要求的是不同路径之间独立,而不是同一路径中相邻位置独立。
定义 9.1.3
(依概率收敛与几乎必然收敛)
如果对每个 都有 ,称 依概率收敛到 。如果使 成立的结果集合具有概率一,称其几乎必然收敛。几乎必然收敛是在一次结果上讨论整条无穷序列,并不表示每个有限样本估计都落在指定容差内。
大数定律与误差界
定理 9.1.4
(有限方差的大数定律)
若 独立同分布,均值为 且方差 有限,则 既依概率成立,也几乎必然成立。对每个 ,Chebyshev 不等式给出有限样本界
对独立同分布变量,更一般的强大数定律在一阶绝对矩有限但方差无穷时也成立;下面的证明使用更严格的有限方差条件。
定理 9.1.5
(有界独立输出的 Hoeffding 界)
假设 独立,几乎必然都落在同一区间 中,其中 ,且均值均为 ;在这一均值条件下不需要同分布。那么对每个 ,
特别地,对 ,只要 ,上界便至多为 。
样本量公式给出充分保证,并非精确失败概率。Chebyshev 使用方差界,Hoeffding 使用已知的几乎必然取值范围。一次运行中观察到的范围较小,本身不能证明输出分布受到该范围限制。
收敛与集中结论为何成立
证明
(均值、方差与弱大数定律)
期望的线性性给出无偏性。由独立性,求和方差中的所有非对角协方差为零,所以 。估计量无偏,因此这个方差也等于均方误差。对 应用 Markov 不等式得到 Chebyshev 界;固定 时右边趋于零,证明依概率收敛。
这里使用的是真实方差。如果 未知,以随机样本方差代替需要另外的统计论证;所写的界不会自动变成置信保证。
证明
(有限方差下的几乎必然收敛证明)
令 、。 相互独立、均值为零、方差为 。先证明最大值不等式
对每个 ,令 为首次满足 的下标是 的事件。 互不相交,并由 确定。由独立性及零均值,交叉项在期望中为零,而不是逐点为零:。剩余增量平方非负。因此
对 求和,并利用 ,得到最大值不等式。
对整数 ,取 、。存在某个 使 的概率至多为 ,这些上界对 可求和。由第一 Borel–Cantelli 引理,几乎必然只有有限多个事件发生。因此充分大时,对每个 均有 。对 将这些概率一的事件取交集,得到 几乎必然成立。
证明透视
为何要对整块下标而非单个下标作估计
有限方差通过 进入证明,这是唯一度量波动大小的地方。独立性只用了一次: 只依赖 ,而 只依赖其后各项,所以两者乘积的期望可以分解,均值为零的增量使它消失。
不显而易见的一步是选择估计什么。对每个单独下标用 Chebyshev 只得 ,而调和级数发散,Borel–Cantelli 引理便无从使用。最大值不等式只付出一个因子 ,就同时控制所有 ;再把下标分成 的块,界 便成为等比数列。块内 ,故 推出 ,代价只是一个因子二。
论证分两阶段收尾:Borel–Cantelli 引理把可求和的失败概率序列转化为单一结果上“最终不再失败”,再对 取可数交集,就去掉了对容忍度的依赖。若没有独立性,交叉项未必消失;本页稍后完全相依的例子中,平均值永不稳定。
证明
(有界输出为何给出指数尾界)
先用一个有界变量估计:若 几乎必然成立,则对任意实数 ,
为说明这一点,令 。有界性保证可以在期望号下求导。对分布进行指数倾斜后,其支撑仍在 ;对对数求导可知 是倾斜后分布的方差。支撑于 的变量方差至多为 :将其到自身均值的平方距离与到区间中点的平方距离比较即可。由于 ,而中心化给出 ,将二阶导数界积分两次,得到 。
对于上尾,由 Markov 不等式和独立性,对 有
取 得到 。对 重复论证,并对两个尾事件使用并集界,便得系数二。独立性用于将和的指数矩分解为各项乘积。
证明透视
指数矩使独立性变成乘积
真正的想法是对 而不是对和本身使用 Markov 不等式,这样独立性就把矩分解成 个单变量因子的乘积。有界性只通过单变量估计 进入,独立性只用在分解这一步。参数 之后可以自由选取:指数 在 时最小,得到 。因子二来自两个尾部的联合界。没有独立性,乘积这一步就不成立,下面完全相依的例子就是这样。
重要性抽样
定义 9.1.6
(改变抽样密度)
设 是相对于同一个参考测度 的概率密度,记 ,“几乎处处”也相对于 。设 是实值可测函数且 。假设在 的集合上, 几乎处处成立。独立抽取 ,定义
在 的 零测集上可任意定义比值。支撑条件保证
如果另外有 ,则其方差为
上面的支撑条件针对这一个被积函数。若希望用同一提议分布处理 下任意被积函数,则应要求 在 上几乎处处成立。若提议分布遗漏 有非零贡献的区域,给所观察样本乘权重也无法恢复遗漏部分。即使支撑足够,过小的 仍可能导致巨大权重和无穷方差。
衡量方差能降到多小,有一个有用的理论基准。令 ,假设 。对任意满足支撑条件且权重二阶矩有限的提议密度 ,Cauchy–Schwarz 不等式给出
因为 。取 可达到等号;它是密度,并具有此被积函数所需的支撑。权重方差可达到的最小值是 。若 在 下几乎处处非负,,最优权重恒为 ;变号的被积函数则不一定能达到零方差。这是理论基准:精确使用 需要其归一化常数 ,而它可能未知。
例如,令 为 上的均匀密度,。此时 、、。权重在左半为 、右半为 ;在提议分布下两半概率均为 。其方差为 ,小于均匀抽样的 ,但并非零。
概念视角分析
把权重的方差看作卡方距离
取 ,则 ,。若在 的地方 ,则 。这是 相对于 的卡方散度:它当且仅当 几乎处处成立时为零,当且仅当 发散时为无穷大。在下面方差无穷的例子中,。
例题
例题 9.1.7
(估计圆盘面积)
独立地从 均匀抽取 ,令 。正方形面积为四,圆盘面积为 ,所以 。估计量是落入圆盘的比例乘四。这里 ,且
若要求绝对误差 、失败概率至多 ,Hoeffding 给出充分条件
所以 足够。这是独立均匀抽样条件下的事前保证,不是此程序返回某个具体小数的实际概率。
例题 9.1.8
(方差为零的重要性提议分布)
估计 时,取目标密度 、提议密度 ,。虽然单点 ,支撑条件仍几乎处处成立。对提议分布的一个样本,
因此任何正样本量的估计都恰为 ,方差为零。相比之下,均匀抽样时 的方差为 。这是一个理想的教学例子,不是一般性的现成方法:将与未知非负被积函数成比例的密度归一化,可能需要先知道正要估计的积分。
例题 9.1.9
(支撑正确但方差无穷)
现在以同样的 、 估计 。对 ,权重为 。其期望为一,但
因此估计量仍然无偏,但每个有限 的方差均无穷:权重非负,所以 。有限方差 Chebyshev 公式和有界输出 Hoeffding 公式都不适用。一般的一阶绝对矩强大数定律仍可能给出几乎必然收敛,但这一事实不提供有限方差误差证书。
反例模式
许多相依输出可能只有一份信息
令 为公平 Bernoulli 随机变量,并对所有 设 。每个 的均值为 、方差为 ,但输出完全相依。无论 多大,平均值始终为 ,其方差保持 ,也不依概率收敛到 。若把这 个值误当成独立变量,就会错误地预测方差为 。
常见错误
常见错误
(把无偏性当成单次估计可靠)
无偏估计在某一次运行中可能离目标很远,甚至可能有无穷方差。有限样本保证需要足够强的尾部控制假设,并须给出容差及失败概率。几乎必然收敛是渐近结论,不是某个有限 的误差证书。
常见错误
(忽略提议密度为零的位置)
如果 的集合上 有非零贡献,估计器永远不会从那里取样。例如估计 时取 ,但取 ,则每个被抽到的点都有 ,期望输出为 而非一。问题是缺失支撑,而不是大样本波动。
总结
方差有限时,独立模拟的平均值无偏且方差为 。Chebyshev、Hoeffding 和强大数定律在不同条件下给出不同类型的结论。重要性抽样改变观测分布;使用基于方差的保证前,必须检查支撑以及权重的二阶矩是否有限。
练习
练习 9.1.10
(独立输出的均值为 、方差为 。当 时,求平均值的方差和均方根误差,并给出误差至少为 的 Chebyshev 上界。)
基础
解答(3)
- 1
平均值的方差
- 2
均方根误差
依据: 估计量无偏,所以其均方误差就是方差。
- 3
应用 Chebyshev 不等式
这只是上界,不是所有具有所述均值和方差的分布的精确概率。
练习 9.1.11
(对 中的独立输出,求一个整数 ,使 时 Hoeffding 双侧界至多为 。)
基础
解答(3)
- 1
写出条件
依据: 这里 。
- 2
解出
- 3
向上取整
足够。
练习 9.1.12
(取 、,,估计 。求重要性权重、其均值和方差。)
核心
解答(3)
- 1
计算权重
关键一步
对 ,几乎必然有
- 2
计算均值
- 3
计算二阶矩与方差
若独立抽取 个提议样本,其平均值方差为 。
练习 9.1.13
(对所有 令 ,其中 为公平 Bernoulli 随机变量。计算 ,并解释为什么不能使用独立样本的 Hoeffding 界。)
核心
解答(3)
- 1
确定平均值
每个 都等于 ,所以对每个 都有 。
- 2
计算概率
由于 ,恒有 ,所以所求概率对每个 都是 。
- 3
找出不成立的假设
输出完全相依,这个分解不成立。界 在 较大时小于 ,与精确值 矛盾。
依据: Hoeffding 的证明把和的指数矩分解为各样本的乘积。