同一个随机来源
模拟时,我们常常先得到一个介于零和一之间的均匀随机数 ,但所需的结果可能是偏斜的、离散的,甚至同时含有连续部分和原子。怎样用同一种输入产生所有这些分布?设想从左到右累积概率:累积分布函数(CDF)告诉我们到某个位置为止已累积了多少概率,而分位数指出首次累积到指定比例的位置。
设 是累积分布函数。 单调不减、右连续,并满足 和 。它可以有跳跃,也可以在某些区间上保持不变,因此普通的反函数未必存在。
定义 29.1.1
(广义分位数)
对 ,累积分布函数 的广义分位数为
由 在两端的极限,这个集合非空且有下界,所以 是实数。若输入在 上均匀分布, 和 处的取值不影响结果的分布,也不必在端点处硬性指定有限值。
定理 29.1.2
(反变换构造)
若 在 上服从均匀分布, 是累积分布函数 的广义分位数,则 的累积分布函数是 。这一结论对连续、离散及混合分布同样成立。
证明
(分位数的事件等式)
我们证明:对任意实数 和 ,
若 ,则 属于定义 的集合,所以其下确界满足 。反过来,由于 单调不减,定义集合是一个向右无界的区间。取集合中的点 (若 本身已在集合中,可取 )。则 ,由右连续性得 。若 ,由单调性就有 。
由于 在 上均匀分布,上述等式对每个实数 给出
包括 和 的情形。因此 的累积分布函数是 。
证明透视
右连续性与下确界在哪里用上
整个证明就是这个事件等式;有了它,均匀分布只需一行就把 化为数值 。等式有容易的一半和精细的一半。容易的一半 只用到下确界的定义。精细的一半需要 ,即下确界可以取到;这是唯一用到右连续性的地方。
“”与“”的搭配是有意的选择。若改用左连续版本的 ,取到下确界这一步在原子处可能失败,而等式恰好会在那些使离散分布成为可能的跳跃处失效。论证中没有假设 连续或严格递增;正因为如此,同一个构造适用于离散、连续及混合分布。
三个分位数计算
例题 29.1.3
(离散分布)
设 、、。累积分布函数在 处跳跃,因此
三个区间的长度分别是 ,恰好给出所需的概率。对于连续的均匀输入,改变分界点处的输出不会改变分布;上式中端点的归属是由 的定义决定的。
例题 29.1.4
(指数分布)
设 ,当 时 ,当 时 。对 ,当 时 不成立;当 时它等价于 ,即 。因此
此例中直接解方程 也得到同一答案,因为 在 上连续且严格递增。验算:对 ,。
例题 29.1.5
(左端带原子的混合分布)
设 以概率 等于 ,否则在 上服从均匀分布,于是当 时 ,当 时 ,当 时 。若 ,则 ,而 时 ,所以 。若 ,则 当且仅当 ,所以 。
边界情形出现在原子处。整段输入 都被映到同一个值 ,给出 ;在 上,映射 把剩下的概率均匀地铺在 上。这里当 时方程 无解,但 仍有定义。
反方向的变换
定理 29.1.6
(概率积分变换)
若 的累积分布函数 在整条实轴上连续,则 在 上服从均匀分布。这里不要求 严格递增。
证明
(利用水平集的右端点)
固定 ,令 。由两端的极限,这个集合非空且有上界,所以 有限。集合中的点从左侧趋于 ,由连续性得 ; 右侧的点满足 ,由连续性得 。因此 。若 ,则 ;若 ,则 。所以
由于 取值于 ,且上式对每个 成立, 在 上服从均匀分布。
证明透视
为什么平坦部分无妨而跳跃不行
关键一步是把 取为水平集 的右端点,而不是去解 。若 在高度 的某个区间上是平的,方程就有许多解;取上确界选出一个点 ,使 ,而平坦区间本来就没有概率。
连续性用了两次,分别得到 和 。若 在 处跨过 跳跃,就可能有 ,而 ,计算结果会是 而不是 。没有任何一步用到严格递增,所以定理不作这一假设。
连续性确实重要:若 在 处有原子,则 以至少 的概率等于 ,而均匀分布没有原子。单纯套用 不可能把一个原子拆成一段连续的取值区间。
反例模式
公平硬币的 CDF 值并不均匀
设 。这时 以各 的概率取值 和 。例如 ,而不是 。对同一个不连续的 ,反变换 仍然有效;反方向的结论则需要连续性。
用独立的随机性填补跳跃
有一个有用的补救办法。记左极限 ,于是 是 处的跳跃。
定理 29.1.7
(随机化概率积分变换)
设 的累积分布函数为 , 与 独立且在 上服从均匀分布。则
在 上服从均匀分布,无论 属于哪种类型。
证明
(按 相对于分位数的位置分情形)
固定 ,令 。事件等式给出 ,而每个 都有 ,所以 。按 的位置拆分事件 。
若 ,则 ,所以这种情形贡献 。
若 ,则 。在有正跳跃的点处, 给出 。在没有跳跃的点处, 迫使 ,于是 落在 右侧一个 为常数的区间内,而这样的区间概率为零。这种情形贡献 。
若 且跳跃 为正,由 的独立性,
因为这个比值在 内。若 ,则 且 ,贡献 仍然一致。三种情形相加得 。
在原子 处,这个式子把它的概率均匀地分配到跳跃区间 上;没有跳跃时 。
常见错误
常见错误
(对含原子的分布解 )
对原子位于 的离散分布,方程 无解: 在 处从 跳到 。反变换抽样并不需要方程有解。广义分位数给出 ,即累积概率首次达到 的点。
常见错误
(以为分位数是具有该概率的唯一点)
对取值于 的公平硬币,每个 都满足 和 ,所以每个这样的 都是中位数。广义分位数并没有找出“真正的”中位数,而是作出一个确定的选择 ,即累积分布函数达到 的最小点。
练习
快速检查
(设 、、。求广义分位数,并计算 。)
先列出 在三个原子处的值。
解答 · 答案
、、。因此当 时 ;当 时 ;当 时 。事件 就是 ,概率为 。
快速检查
(设 ()、()、()。求 以及均匀 下的 。)
在 上,累积分布函数连续且严格递增。
解答 · 答案
对 ,在 时 即 ,所以 。因此 ,与 一致。
快速检查
(设 是伯努利(Bernoulli)变量,,其中 。求 的分布,并解释它为什么不是均匀分布。)
计算 在两个可能取值处的值。
解答 · 答案
,;因此 以概率 取值 ,以概率 取值 。它有原子,所以不是连续的均匀分布。
快速检查
(在伯努利情形中,令 是独立的均匀变量。分别写出 、 时的随机化变换 ,并验证 时 。)
先求 和 。
解答 · 答案
由于 、: 时 ; 时 。若 ,只有 有贡献,;若 ,概率为 。两个条件均匀区间恰好填满 。