14.2.1 算法从什么随机性出发
下面假设可以取得无限序列 \(U_1,U_2,\ldots\)，各项相互独立且服从 \(U(0,1)\)。这个理想模型把生成目标分布的问题转化为可测函数的构造。若同一个算法需要两个独立均匀变量，就必须消耗两次独立抽样；把同一个 \(U\) 同时代入两个位置，通常改变联合分布。
计算机中的伪随机发生器由有限内部状态和确定性递推产生数字。固定种子后结果可重现，但输出并不是数学意义上的无限独立连续序列。统计检验可以发现某些缺陷，不能证明完全独立。本节证明针对理想模型；实际实现还需考虑发生器质量、有限精度以及端点是否可能取到。
“同一个种子”是复现实验的条件，不是各次运行相互独立的保证。特别是并行模拟中，让每个工作单元从完全相同的种子重新启动，会复制同一段数列。对算法的验证应分开检查目标分布推导、随机源的使用方式与数值运算，直方图相似只能作为其中一项经验检查。
14.2.2 广义逆变换涵盖跳跃与混合分布
对任意实分布函数 \(F\)，在 \(0<u<1\) 上定义广义逆
若 \(U\sim U(0,1)\)，则 \(X=Q(U)\) 的分布函数就是 \(F\)。不要求 \(F\) 连续、严格递增或存在密度。
当 \(0<u<1\) 时，分布函数在两端的极限保证定义中的集合非空且有有限下界；单调性与右连续性保证该下界也在集合内。因此 \(Q(u)\le x\) 当且仅当 \(u\le F(x)\)。这同时证明 \(Q\) 可测，并给出
分布函数的一次跳跃对应 \(u\) 轴上一段区间，这段区间会全部映到同一个原子。对连续严格递增的 \(F\)，广义逆退化为普通反函数。相比之下，\(F(X)\) 对一般离散或混合分布并不均匀，不能把逆变换结论随意反过来使用。
设 \(P(X=0)=0.3\)，其余 \(0.7\) 的概率按速率 \(2\) 的指数分布取值。则 \(x<0\) 时 \(F(x)=0\)，\(x\ge0\) 时 \(F(x)=1-0.7e^{-2x}\)。逐段解不等式得到
因此 \(u=0.2\) 生成 \(0\)；\(u=0.65\) 生成 \((\ln2)/2\approx0.346574\)，代回分布函数恰得 \(0.65\)。这里将原子和连续部分都用一个均匀变量处理。也可先独立选择混合成分，再在指数成分内抽样；两种方法的随机数消耗不同，但目标分布相同。
离散分布同样适用：把各质量依次累加，选择累计概率第一次达到 \(u\) 的取值即可。如果没有显式反函数，但能稳定计算 \(F\)，可以先找到包含分位点的区间，再二分求解；有限步数只给近似值，应记录分位点误差。连续分布在密度很小的尾部，微小的 CDF 误差可能对应较大的位置误差。
14.2.3 接受拒绝法的正确性与代价
设目标密度为 \(f\)，另有容易生成的提议密度 \(g\)，并找到有限常数 \(M\) 使 \(f(x)\le Mg(x)\) 几乎处处成立。两密度相对同一个基准测度，离散情形可用计数测度。积分立即给出 \(M\ge1\)。提议分布必须覆盖目标质量所在区域；只在画图范围内验证上界还不够。
| 步骤 | 操作 | 条件 |
|---|---|---|
| 1 | 生成 \(Y\sim g\) 与 \(V\sim U(0,1)\) | 彼此独立，且与之前各轮独立 |
| 2 | 若 \(V\le f(Y)/(Mg(Y))\)，输出 \(Y\) | 阈值在 \([0,1]\) 内；\(g=0\) 的点可任意定义 |
| 3 | 否则丢弃本轮并回到步骤 1 | 拒绝后重新生成两个变量 |
记一轮的接受事件为 \(A\)。对任意可测集合 \(B\)，由独立性和条件积分，
取全集得 \(P(A)=1/M\)，相除便得 \(P(Y\in B\mid A)=\int_Bf(y)\,dy\)。各轮独立时，第一次接受出现在第 \(n\) 轮的概率为 \((1-1/M)^{n-1}/M\)，所以提议次数 \(N\) 服从从 \(1\) 开始的几何分布，\(EN=M\)。更直接地，输出落在 \(B\) 的概率是 \(\sum_{n\ge1}(1-1/M)^{n-1}M^{-1}\int_Bf=\int_Bf\)。对每个输出都继续使用未用过的独立随机源，重复输出的样本也相互独立。
令 \(f(x)=6x(1-x)\mathbf1_{(0,1)}(x)\)，这是 \(\operatorname{Beta}(2,2)\) 密度。取 \(g(x)=1\) 于 \((0,1)\)，最大密度 \(f(1/2)=1.5\)，故可取 \(M=1.5\)，接受规则为 \(V\le4Y(1-Y)\)。例如 \(Y=0.2,V=0.5\) 时阈值为 \(0.64\)，接受；\(Y=0.9,V=0.5\) 时阈值为 \(0.36\)，拒绝。每轮接受率为 \(2/3\)，平均每个输出需要 \(1.5\) 轮，即 \(3\) 次独立均匀抽样。
如果只知道未归一化函数 \(h\)，其积分 \(Z\) 有限且为正，并有 \(h\le Cg\)，则用 \(h(Y)/(Cg(Y))\) 接受即可。相同计算给出接受率 \(Z/C\)，输出密度为 \(h/Z\)。算法判断中不需要知道 \(Z\)，但必须有真正成立的包络常数 \(C\)；把超过 \(1\) 的阈值强行截为 \(1\) 通常会改变目标分布。
14.2.4 Box–Muller 变换的二维推导
取独立的 \(U_1,U_2\sim U(0,1)\)，令
则 \(Z_1,Z_2\) 相互独立，且均为标准正态。相同的半径并不会造成两个直角坐标的依赖；这里必须用联合密度证明。
对 \(r\ge0\)，\(P(R>r)=P(U_1<e^{-r^2/2})=e^{-r^2/2}\)，故 \(f_R(r)=re^{-r^2/2}\)。独立性给出 \((R,\Theta)\) 的联合密度为 \(re^{-r^2/2}/(2\pi)\)。变换 \((r,\theta)\mapsto(r\cos\theta,r\sin\theta)\) 的雅可比行列式绝对值为 \(r\)，所以除去零测的原点与角度接缝，
密度分解为两个标准正态密度，故结论成立。若改用均匀半径，雅可比约去后不会得到正态密度；仅仅“方向均匀”不足以证明二维正态。
例如 \(U_1=e^{-2},U_2=1/8\) 时，\(R=2\)、\(\Theta=\pi/4\)，两输出恰为 \(\sqrt2\)。这只是一次代入示范，并不代表重复输出相等。对 \(N(\mu,\sigma^2)\)，取 \(\mu+\sigma Z\) 即可；例如 \(\mu=3,\sigma=2\) 时，该输入生成 \(3+2\sqrt2\approx5.828427\)。
14.2.5 数值实现与检验
对数变换要保证输入严格大于零。若实现给出的均匀数可能等于零，可重新抽样这个端点，或使用明确产生开区间数值的接口约定；不能让 \(\ln0\) 进入后续运算。极小概率的尾部也受有限精度限制，增加样本数并不能恢复发生器从未表示过的值。
先用解析证明核对分布，再检验若干已知量。例如例 2 的均值为 \(1/2\)、方差为 \(1/20\)、接受率为 \(2/3\)。有限样本下这些经验量会波动，不应要求完全相等；合理误差尺度需要下一节的蒙特卡洛方差与中心极限定理。检查相邻输出的相关性有助于发现重复使用随机数的错误，但零经验相关也不等于独立。
在接受拒绝循环中，记录提议数与接受数能发现包络过松造成的计算浪费。换一个更贴近目标的提议分布，可降低 \(M\)，但其自身的生成成本也应计算。若只有转移机制容易构造、独立提议始终很难覆盖目标，可以进一步使用马尔可夫链蒙特卡洛；那时必须重新处理样本之间的依赖，不能沿用本节 iid 输出的结论。
14.2.6 习题与解答
习题 14.2-1 · 离散广义逆的端点
变量在 \(-1,0,2\) 上的概率依次为 \(0.2,0.5,0.3\)。写出 \(Q(u)\)，求 \(Q(0.2),Q(0.7),Q(0.9)\)，并判断 \(F(X)\) 是否均匀。
解答。在 \((0,0.2]\)、\((0.2,0.7]\)、\((0.7,1)\) 上，广义逆依次为 \(-1,0,2\)。所以三个答案为 \(-1,0,2\)。端点归属由“第一次达到”决定，改变有限多个端点不会改变理想连续均匀输入的输出分布。\(F(X)\) 只取 \(0.2,0.7,1\) 三个值，故不是连续均匀分布。
习题 14.2-2 · 选择提议分布
目标密度为 \(f(x)=3x^2\) 于 \((0,1)\)。分别用均匀密度及 \(g(x)=2x\) 作提议，给出最小包络常数、接受概率与提议的生成方法。
解答。均匀提议下 \(f/g=3x^2\)，本质上确界为 \(3\)，故 \(M=3\)、接受率 \(1/3\)。第二种提议下 \(f/g=3x/2\)，取 \(M=3/2\)，接受率 \(2/3\)，规则为 \(V\le Y\)。其 CDF 为 \(G(y)=y^2\)，所以可用 \(Y=\sqrt U\) 生成。目标本身也能直接用 \(X=U^{1/3}\) 生成，因此这个例子主要用于比较包络，而不是主张必须用拒绝法。
习题 14.2-3 · 平均提议数与方差
证明接受拒绝法的提议次数满足 \(EN=M\)、\(\operatorname{Var}(N)=M(M-1)\)。
解答。设 \(a=1/M\)、\(q=1-a\)，则 \(P(N=n)=aq^{n-1}\)。由等比级数两次求导，有 \(\sum_{n\ge1}nq^{n-1}=(1-q)^{-2}\)、\(\sum_{n\ge1}n(n-1)q^{n-2}=2(1-q)^{-3}\)。所以 \(EN=1/a\)、\(E[N(N-1)]=2q/a^2\)，从而 \(\operatorname{Var}(N)=q/a^2=M(M-1)\)。当 \(M=1\) 时每轮必接受，两个结论也直接成立。
习题 14.2-4 · 重复使用一个均匀变量
令 \(U\sim U(0,1)\)，\(X=-\ln U\)、\(Y=-\ln(1-U)\)。二者边缘都为速率 \(1\) 的指数分布。证明它们不独立，并求 \(P(X>\ln2,Y>\ln2)\)。
解答。第一事件要求 \(U<1/2\)，第二事件要求 \(U>1/2\)，交集为空，所以联合概率为零。若独立，该概率应为 \((1/2)^2=1/4\)。边缘正确不能保证联合分布正确，这正是用一个随机输入代替两个独立输入产生的问题。
关键术语
- 理想均匀源：相互独立的连续均匀变量序列。
- 伪随机发生器：有限状态的确定性数列生成机制。
- 广义逆：分布函数第一次达到给定概率的取值。
- 接受拒绝法：以密度比筛选提议样本。
- 包络常数：使目标密度被提议密度的常数倍控制。
- 接受率：每轮产生有效输出的概率。
- Box–Muller 变换：由独立均匀变量构造独立正态变量。
- 有限精度：计算机数值表示给算法带来的额外限制。