当前课程知识点:概率论与数理统计 > 第十二周 大数定律和中心极限定理 > 蒙特卡洛(Monte Carlo)算法 > 12.3 蒙特卡洛(Monte Carlo)算法
蒙特卡洛方法是计算机出现之后
利用概率模型近似计算的方法
例如右图中单位圆的面积是pi
在-1到1和-1到1围成的正方形区域内
均匀地撒点
落在单位圆内的点标为红色
落在圆外的点标为蓝色
如果共抛了n个点
其中落在单位圆内的红色点有m个
则n分之m近似等于
单位圆面积与正方形的面积比
已知正方形的面积为4
则单位圆的面积即圆周率pi
可用4倍的n分之m近似
这个近似关系的理论基础是大数定律
设第k次撒点落入单位圆内时
随机变量Xk等于1
否则Xk等于0
则对所有的大于等于1小于等于n的k
Xk服从取值为0,1
对应概率分别为1减4分之pi
和4分之pi的离散分布
且相互独立
Xk的期望等于4分之pi
而n次撒点中
落入单位圆内的的次数m
为随机变量
等于X1到Xn的求和
根据大数定律
对任意的正数ε
当n趋于无穷时
n分之X1加X2一直加到Xn
减期望的绝对值
大于等于ε的概率趋于0
也就是 当n比较大时
n分之m与期望4分之pi的偏差
大于ε的概率会比较小
可以用n分之m近似4分之pi
Monte Carlo方法的基本想法
是构造一个随机变量
使得所希望计算的量
是这个随机变量的某个数字特征
(通常是数学期望)
然后通过随机模拟的方法
得到这个数字特征的估计
从而得到所希望计算的量的估计
可利用中心极限定理
对Monte Carlo方法的精度
作进一步的分析
设随机变量X1,X2
到X2n相互独立
且均服从0,1区间的均匀分布
对大于等于1小于等于n的整数k
定义随机变量Yk
当X(2k-1)的平方
加X(2k)的平方小于1时
Yk等于4
其他情况下Yk等于0
对任意给定的正整数n
定义Y一把等于Y1,Y2
到Yn的算数平均
证明随机变量Y一把的期望等于pi
根据这一结论
即可用Y1到Yn的平均值近似pi
得到一个近似圆周率pi的
Monte Carlo算法
利用中心极限定理估计 n=100时
Y一把减pi的绝对值小于0.1的概率
这实际上是对Monte Carlo的精度
进行概率意义下的分析
分析当用100个Yk的平均值
近似pi时
误差不超过0.1的概率
最后 利用另一个概率估计工具
切比雪夫不等式
估计n取多大值时
可保证Y一把与pi的偏差
小于0.1的概率不小于0.9
先证明第一问
对所有的k Yk服从两点分布
k等于4的概率等于
X(2k-1)的平方加X(2k)的平方
小于1的概率
X(2k-1)和X(2k)是
相互独立的0,1区间的均匀随机数
由这两个值作为坐标的点
均匀地落在0,1围成的正方形内
X(2k-1)的平方加
X(2k)的平方小于1时
坐标落入单位圆的第一象限
所以Yk等于4的概率等于4分之pi
Yk等于0的概率为1减4分之pi
Yk的期望为pi
所以Y一把的期望等于
n分之Y1直到Yn求和的期望
等于n分之Y1到Yn期望的求和
等于pi
再看第二问
Y一把的期望等于pi
Y1的方差容易计算
为pi乘以(4减pi)
所以Y一把的方差等于
100分之pi乘以(4减pi)
根据中心极限定理
Y一把近似服从期望为pi
方差为100分之pi乘以
(4减pi)的正态分布
对Y一把做减去期望
除以标准差的标准化后
得到根号pi乘以(4减pi)分之
10乘以(Y一把减pi)
近似服从标准正态分布
Y一把减pi的绝对值
小于0.1的概率
转化为标准正态分布的概率近似
约等于2倍的phi
(根号pi乘以(4减pi)分之1)减1
等于0.46
可以看到 Monte Carlo方法的
精度非常的低
用100个样本平均
得到pi的绝对误差
小于0.1的估计的概率不足1/2
Monte Carlo 方法
比较传统方法的优势
并不在于二、三维空间面积与体积的近似
科学、工程计算中常常需要计算
非常高维空间的体积的问题
维数可能达到几千万甚至上亿的规模
这时传统的方法都不再有效
只有借助于Monte Carlo方法
才可能得到有效的结果
最后 利用切比雪夫不等式
估计n取多大值时
可保证Y一把与pi的偏差
小于0.1的概率不小于0.9
注意到pi是Y一把的期望
Y一把减pi的绝对值小于0.1的概率
就是Y一把减它的期望的绝对值
小于0.1的概率
利用切比雪夫不等式
此概率
大于等于1减去0.1的平方分之
Y一把的方差
1减去0.1的平方分之Y一把的方差
等于1减去n分之
100乘以pi乘以(4减pi)
使得这个值大于等于0.9
解得n大于等于2697
也就是n大于2697时
可保证Y一把与pi的偏差
小于0.1的概率不小于0.9
-随机试验与随机事件
-古典概型
--1.2 古典概型
--第一周:古典概型
-事件间的关系与事件的运算
--第一周:事件间的关系与事件的运算
-两个著名的例子
--第一周:两个著名的例子
-讲义
-条件概率
--2.1 条件概率
--第二周:条件概率
-有关条件概率的三个重要计算公式
--第二周:有关条件概率的三个重要计算公式
-事件的独立性
--第二周:事件的独立性
-应用实例
--2.4 应用实例
--第二周:应用实例
-网球比赛胜率的计算
--Video
-讲义
-随机变量及分布函数
--第三周:随机变量及分布函数
-离散型与连续型随机变量
--第三周:离散型与连续型随机变量
-分布函数的性质与特殊的例子
--第三周:分布函数的性质与特殊的例子
-概率论所需微积分要点回顾
--第三周:概率论所需微积分要点回顾
-讲义
-二项分布与负二项分布
--第四周:二项分布与负二项分布
-泊松分布
--4.2 泊松分布
--第四周:泊松分布
-几何分布与指数分布
--第四周:几何分布与指数分布
-正态分布
--4.4 正态分布
--第四周:正态分布
-讲义
-随机变量函数的分布
--第五周:随机变量函数的分布
-随机变量的数学期望
--第五周:随机变量的数学期望
-随机变量的方差
--第五周:随机变量的方差
-原点矩与中心矩
--第五周:原点矩与中心矩
-期望和方差的一些补充性质
--第五周:期望和方差的一些补充性质
-讲义
-二项分布与泊松分布的期望与方差
--第六周:二项分布与泊松分布的期望与方差
-几何分布的期望与方差
--第六周:几何分布的期望与方差
-均匀、指数和正态分布的期望与方差
--第六周:均匀、指数和正态分布的期望与方差
-随机变量数学期望的应用实例
--第六周:随机变量数学期望的应用实例
-快速排序算法的平均计算量分析
--Video
-讲义
-多维随机变量
-第七周:多维随机变量
-常见多维随机变量举例
--第七周:常见多维随机变量举例
-随机变量的独立性
--第七周:随机变量的独立性
-独立随机变量期望和方差的性质
--第七周:独立随机变量期望和方差的性质
-讲义
-条件分布
--8.1条件分布
--第八周:条件分布
-条件期望
--8.2 条件期望
--第八周:条件期望
-全期望公式(上)
--第八周:全期望公式(上)
-全期望公式(下)
--第八周:全期望公式(下)
-讲义
-随机变量函数的期望
--第九周:随机变量函数的期望
-协方差
--9.2 协方差
--第九周:协方差
-相关系数
-- 9.3 相关系数
--第九周:相关系数
-相关与独立
--第九周:相关与独立
-讲义
-独立随机变量和的分布
--第十周:独立随机变量和的分布
-独立正态分布和的分布
--第十周:独立正态分布和的分布
-最大值、最小值分布
--第十周:最大值、最小值分布
-顺序统计量
--第十周:顺序统计量
-讲义
-正态分布的相关与独立
--第十一周:正态分布的相关与独立
-边缘密度均为正态,联合分布不是二元正态的例子
--第十一周:边缘密度均为正态,联合分布不是二元正态的例子
-二项分布的正态近似
--第十一周:二项分布的正态近似
-正态近似计算实例
--第十一周:正态近似计算实例
-讲义
-大数定律
--12.1大数定律
--第十二周:大数定律
-中心极限定理
--第十二周:中心极限定理
-蒙特卡洛(Monte Carlo)算法
-伪随机数和随机模拟
-讲义
-统计学实例
-总体与样本
-常用统计量
--第十三周:常用统计量
-三种重要的统计分布和分位数
--第十三周:三种重要的统计分布和分位数
-讲义
-参数的矩估计
--第十四周:参数的矩估计
-参数的极大似然估计
--第十四周:参数的极大似然估计
-参数点估计的无偏性和有效性
--第十四周:参数点估计的无偏性和有效性
-参数点估计应用实例
--第十四周:参数点估计应用实例
-讲义
-区间估计的基本思想
--第十五周:区间估计的基本思想
-区间估计的构造方法
--第十五周:区间估计的构造方法
-两个正态总体的区间估计
--第十五周:两个正态总体的区间估计
-大样本置信区间
--第十五周:大样本置信区间
-讲义
-假设检验问题的提示和标准步骤
--第十六周:假设检验问题的提示和标准步骤
-假设检验问题的两类错误和P值
--第十六周:假设检验问题的两类错误和P值
-单个正态总体参数的假设检验
--第十六周:单个正态总体参数的假设检验
-拟合优度检验
--第十六周:拟合优度检验
-讲义
-利用条件概率计算网球比赛胜率
-利用期望的计算性质分析快速排序算法的平均计算量
-讲义
-事件
--事件
-分布函数
--分布函数
-正态
--正态
-指数与二项
--指数与二项
-随机变量函数的分布
-指数分布期望
--指数分布期望
-切比雪夫不等式
--切比雪夫
-二元离散
--二元离散
-协方差
--协方差
-二元特征
--二元特征
-统计量
--统计量
-无偏估计
--无偏估计
-点估计
--点估计
-假设检验
--假设检验
-选择
--选择
-填空
--填空
-大题
--大题