产生各种概率分布的随机数.ppt

5 3产生各种概率分布的随机数 广师Ray xing 5 3 1求逆法 求逆法是基于概率积分反变换的法则 是从许多种离散分布中获得采样值的基本方法 求逆法的基本步骤如下 计算所要的随机变量X的概率分布函数F X 在X的取值范围内 置F X R 由于X是一个随机变量 因此R也是一个随机变量 可以证明 R是区间 0 1 上的均匀分布 解方程F X R 用R来表示X 即是求F X 的逆 产生所要的在 0 1 上的均匀分布随机数并由下式计算所要的随机变量 若X为一个随机变量 它的分布函数为F X 记为F X 的反函数 U为 0 1 均匀分布随机变量 则随机变量同X具有相同的分布函数 事实上 我们有 算法 1 产生U2 例5 3 产生服从负指数的随机数x 负指数密度函数 其分布函数 易得F x 的反函数为 设U为 0 1 即为所求的随机数 又因U是 0 1 上均匀分布的随机数 所以 1 U 也是 0 1 上均匀分布的随机数 故上式可以简化为 均匀分布 则 例5 4产生服从集合分布的随机数 几何分布的密度函数为 其分布函数为 设U是 0 1 上均匀分布的随机数 令 可求得 又因 1 u 也是 0 1 上均匀分布的随机数 上式可简化为 求逆法的优点显而易见 但是在实际应用时往往会遇到一些困难 问题在于分布函数的反函数难以求得 或者计算反函数的工作量过大 以至于无法实现 5 3 2舍选法 舍选法的实质是从许多均匀分布的随机数中选出一部分 使其成为具有给定分布的随机数 它可生产任意有界的随机变量 假设要生成随机变量X服从1 4到1之间的均匀分布 一种方法是 1 产生随机数R2 若R 1 4 接受X R 否则舍去R 转回13 重复该过程至结束 设某一随机数变量的密度函数f x 满足 当x b或x a时 f x 0 用舍选法产生该随机数的方法为以下步骤 1 产生二个 0 1 均匀分布随机数R1 R22 令 并计算函数值3 判别 M为f x 最大值 若成立 X为f x 的随机变量 否则 转入1 若随机变量X的概率密度函数f x 中的X值的下限和上限各为a和b f x 的上界为M 则用舍选法产生X的随机数的步骤如下 1 产生两个独立随机数r1 r22 计算x0 a r1 b a y0 M r23 y0 f x0 则接收x0作为输出 否则舍去该组数据 重新从1开始 重复此过程 a M y b O x x0 舍去 选取 y f x0 y f x 定理 设R2为 0 1 上均匀随机数 R为 a b 区间上的均匀随机数 R与R2相互独立 是 a b 区间上的某一随机变量的密度函数 取一正常数 使得成立 则有 证明 定理得证 由上面可以看到 舍选法不能每次都得到一个随机数 究竟多少次才能求得一个符合判别准则的随机数呢 注意到 我们称之为舍选法的效率 例5 5求服从Beta分布的随机数 Beta分布的密度函数为 其中 为参数 r s 1 解 计算f x 的最大值 求解步骤 1 根据r s 求f x 的最大值M2 产生 0 1 均匀分布随机数R1 R2 3 检验是否成立 若成立R1为Beta分布的随机数 否则转2 例 用舍选法生成具有下面密度的随机数 分析 由于随机变量在 0 1 上取值 不妨取 确定C使得 求微分 得最大值 点 于是 于是有 舍选法只用到了密度函数f x 所以比较方便简单 但其效率低 算法 1 生成随机数和 2 如果 停止迭代 令 否则返回1 生成一个X步骤1的平均迭代次数为 5 3 3组合法 在本节中我们要用到凸组合的概念 它的定义如下 设 是 中点集X的k个点 若存在 满足 使 也属于X 则称 为 对于 的凸组合 组合法的主要思想是这样的 当我们要生成的随机数数列服从的分布函数 可以用其它分布函数 的凸组合表达 并且 远比 时 我们可以先生成服从 的随机数数列 然后再 的随机数数列 要简单 利用这些随机数数列得到服从 具体来说 我们假定对所有x 可以写成 这里 每一个 是一个分布函数 则假定它可以写成 这里 是其密度函数 在离散情况下 组合法依 同样若x为密度函数 然适用 有时我们能给出组合法的几何解释 例如对于X上一个具有密度的连续随机变量 我们可将下的面积分为 区域 对应于将分解为凸组合表示 然后我们可以认为第一步是选一个域 而第二步则是从所选域对应的分布中产生随机数 例双指数 或拉普拉斯 分布具有密度函数 x为实数 由图5 5可见 除了因子0 5之外 可以看 成是由两个背靠背的指数函数组成 我们可把 表示为 这里 表示集合A的指示函数 它定义为 如 其他 于是 可看作 和 的凸组合 和 都是密度函数 且 因此 我们可用 和 的组合来产生X R2 如果 则令 返回 同样 则令 返回 首先产生两个在 0 1 上服从均匀分布的随机数R1 若 图5 5双指数分布的概率密度函数 5 3 4经验分布法 经验分布法又称为表搜索法 主要用于产生离散分布的随机数 也可通过离散近似抽样产生连续分布的随机数 现实中很多随机现象的理论分布往往是不知道的 而其经验分布常常是可以得到的 为了仿真这些随机现象 通常根据它们的经验分布来产生抽样值 下面介绍用经验分布法来产生离散分布随机数的方法 设随机变数X的取值 的概率为 即 i 1 2 k 且 将 0 1 区间划分为k个小区间 每个区间长度分别等于 令 i 1 2 k 其中称为累积分布函数 即 现任取 0 1 上均匀分布的随机变数 若 则 这是因为我们有 综上所述 产生离散分布的随机数主要步骤如下 1 编制如表5 3所示的表格 并存入计算机内 为了缩短搜索时间 累积分布函数可按 排列计算 2 产生 0 1 上均匀分布的随机数r 3 进行表搜索 若 则 例 在研究消防队工作人员和消防员可能备选的调度策略的仿真中 收集到了消防队接到报警后的响应时间的5个观测值 min 数据如下 2 761 830 801 451 24 在收集更多的数据之前 希望以这5个观测值为基础的响应时间分布建立一个初始仿真模型 首先 可以假设响应时间X的范围为0 X c c是未知的 但我们用观测值的最大值作为其估计值 将观测数据由小到大排列 假定每个间隔的概率为1 n n表示观测值的个数 由此 可以得到经验分布函数的估计值 0 5 1 0 3 0 2 5 2 0 1 5 x 1 0 0 8 0 6 0 4 0 2 F x 0 R1 0 71 X1 X1 1 45 1 90 0 71 0 60 1 66 第i条线段的斜率是 因此 当i 1 n R i n时 计算累积分布函数的逆 0 5 1 0 3 0 2 5 2 0 1 5 x 1 0 0 8 0 6 0 4 0 2 F x 0 R1 0 71 X1 X1 1 45 1 90 0 71 0 60 1 66 5 3 5近似法 近似法是指一种利用一些定理或公式来近似地产生所需随机数的方法 这种方法一般用于分布函数比较复杂 难以对其求解的情况 如正态分布 下面主要介绍用该方法产生正态分布随机数的问题 1 利用中心极限定理 设 为n个的在 0 1 区间上的均匀分布随 机数 它们相互独立 则有 根据中心极限定理 服从标准正态分布N 0 1 如果作线性变换 则可以得到一个服从正态分布N 的随机变量 在实际应用中 只要取就可以了 2 Box Muller近似方法 设R1 R2为在 0 1 区间上服从均匀分布的随机数 利用Box Muller公式 可以产生和两个服从标准正态分布N 0 1 的随机数 谢谢