01一维非均匀随机数的产生

Lingfeng 2025-02-18

01一维非均匀随机数的产生

1. 常用连续非均匀随机数的产生

1.1 逆变换抽样法

Theorem (逆变换同分布)

设连续型随机变量 $\eta$ 的分布函数 $F(x)$ 连续且严格单增，其反函数存在且记为 $F^{-1}(x)$ ，则 $F(\eta)\sim U(0,1)$ 且 $F^{-1}(U)\stackrel{ d }{=} \eta$

Corollary (推论)

若 $\xi\sim G(x)$ ， $\eta\sim F(x)$ ， $F^{-1}(x)$ 存在，则有 $F^{-1}(G(\xi))\sim F(x)$

设 $f(\cdot)$ ， $g(\cdot)$ 分别为概率密度函数， $h(\cdot)$ 为给的函数，此时若 $X\sim f(x)$ ， $Y\sim g(y)$ ，且 $X$ ， $Y$ 独立。若 $Y\leq h(X)$ ，令 $\eta=X$ 。此时 $\eta$ 概率密度函数为 $p(z)=\frac{f(z)G(h(z))}{\int _{-\infty}^{+\infty}f(x)G(h(x)) \, dx }$ 其中 $G(y)$ 为随机变量 $Y$ 分布函数。

证明
注意到 $\{ \eta\leq z \}\iff \{ X\leq z \mid Y\leq h(X) \}$ ，因此考虑 $\begin{align*} P\{ X\leq z \mid Y \leq h(X) \} & = \frac{P\{ X\leq z,Y\leq h(X) \}}{P\{ Y\leq h(X) \}} \\ & = \frac{\int_{-\infty}^{z} G(h(x))f(x) \, dx }{\int_{-\infty}^{\infty} G(h(x))f(x) \, dx } \end{align*}$ 求导有 $p(z)=\frac{f(z)G(h(z))}{\int _{-\infty}^{+\infty}f(x)G(h(x)) \, dx }$

Corollary (舍选抽样法)

设概率密度函数 $p(z)\leq M(z)$ 且 $\int_{-\infty}^{\infty} M(z) \, dz=C<\infty$ ，令 $f(x)=\frac{M(x)}{C}$ 。此时若 $X\sim f(x)$ ， $Y\sim U(0,1)$ 。若 $Y\leq \frac{p(X)}{M(X)}$ ，令 $\eta=X$ 。此时 $\eta$ 概率密度函数为 $p(z)$ 。

证明
由 $Y\sim U(0,1)$ ，只需证 $\begin{align*} p(z) & =\frac{f(z)h(z)}{\int_{-\infty}^{\infty} f(x)h(x) \, dx } \\ & = \frac{\frac{f(z)}{M(z)} }{\int_{-\infty}^{\infty} \frac{f(x)}{M(x)}p(x) \, dx }p(z) \end{align*}$ 又由 $\frac{f(x)}{M(x)}=C$ ，故证毕。

Corollary (简单舍选法)

设 $\eta$ 在 $(a,b)$ 上取值，概率密度函数 $p(z)$ 且 $\sup_{z\in(a,b)} p(z) = M<\infty$ 。此时若 $X\sim U(a,b)$ ， $Y\sim U(0,1)$ 。若 $Y\leq \frac{p(X)}{M}$ ，令 $\eta=X$ 。此时 $\eta$ 概率密度函数为 $p(z)$ 。

证明
取 $M(x)=M\cdot I\{ x \in(a,b) \}$ 此时 $\int_{-\infty}^{\infty} M(x) \, dx =(b-a)M$ 故此时只需取 $f(x)=\frac{1}{b-a}I\{ x \in(a,b) \}$ ，即 $X\sim U(a,b)$ 。故证毕。

Corollary (分离舍选抽样法)

若概率密度函数 $p(z)$ 满足 $p(z)=Lh(z)f(z)$ 其中 $L>1$ ， $0\leq h(z)\leq 1$ ， $f(z)$ 为概率密度函数。则取 $X\sim f(x)$ ， $Y\sim U(0,1)$ 。若 $Y\leq h(X)$ ，令 $\eta=X$ 。此时 $\eta\sim p(z)$ 。

1.3 变换抽样法

Lemma (单调概率密度变换公式)

设随机变量 $\xi$ 具有概率密度函数 $f(x)$ ，若 $h(\cdot)$ 单调，其反函数 $h^{-1}(\cdot)$ 且其导函数存在，则 $\eta=h(\xi)$ 概率密度函数为 $p(z)=\frac{f(x)}{\lvert h'(x) \rvert}$ 其中 $x=h^{-1}(z)$ 。

证明
以单减为例，有 $h^{-1}(z)<0$ ，此时 $\begin{align*} P\{ \eta \leq z \} & =P\{ h(\xi) \leq z \} \\ & = P\{ \xi \geq h^{-1}(z) \} \\ & = \int _{h^{-1}(z)}^{+\infty}f(x) \, dx \end{align*}$ 因此求导得 $p(z)=-\frac{f(h^{-1}(z))}{h'(h^{-1}(z))} =\frac{f(h^{-1}(z))}{\lvert h'(h^{-1}(z)) \rvert }$

Theorem (概率密度变换公式)

设随机变量 $\xi$ 具有概率密度函数 $f(x)$ ，若 $h(\cdot)$ 的导函数存在，则 $\eta=h(\xi)$ 概率密度函数为 $p(z)=\sum_{x \in h^{-1}(z)} \frac{f(x)}{\lvert h'(x) \rvert}$ 其中 $h^{-1}(z)$ 表示方程 $h(x)=z$ 的所有解构成的集合。

证明
将 $h(x)$ 定义域分解为若干个区间 $[a_i,b_i]$ ，将 $h(x)$ 使得 $h(x)$ 在每个区间上严格单调，此时 $\begin{align*} P\{ \eta \leq z \} & =P\{ h(\xi)\leq z \} \\ & = \sum_{i} P\{ h(\xi)\leq z \} I\{ z\in h([a_{i},b_{i}]) \} \end{align*}$ 由于每个区间均单调，由单调概率密度函数公式有 $p(z) = \sum_{i} \frac{f(x_{i})}{\lvert h'(x_{i}) \rvert }$ 其中 $x_{i}=h^{-1}(z), z\in h([a_{i},b_{i}])$ 。令 $h^{-1}(z)=\{ x \in[a,b]\mid h(x)=z \}$ ，因此上式即 $p(z)=\sum_{x \in h^{-1}(z)} \frac{f(x)}{\lvert h'(x) \rvert}$

Theorem (二元概率密度变换公式)

设随机向量 $(\xi_{1},\xi_{2})$ 的联合概率密度函数 $f(x_{1},x_{2})$ ，令 $\eta=g(\xi_{1},\xi_{2})$ 且存在唯一反变换 $\xi_{1}=h(\eta,\xi_{2})$ ，其一阶偏导数存在。则随机变量 $\eta$ 的概率密度函数为 $p(y)=\left\lvert \frac{ \partial h }{ \partial y } \right\rvert \int_{-\infty}^{\infty} f(h(y,z),z) \, dz$

证明
设 $\begin{cases} \eta=g(\xi_{1},\xi_{2}) \\ \zeta = \xi_{2} \end{cases}$ ，有 $\begin{cases} \xi_{1}=h(\eta,\zeta) \\ \xi_{2}=\zeta \end{cases}$ ，雅可比行列式为 $J=\left | \begin{matrix} \frac{ \partial h }{ \partial \eta } & \frac{ \partial h }{ \partial \zeta } \\ 0 & 1 \end{matrix} \right | =\frac{ \partial h }{ \partial \eta }$ 因此联合密度函数为 $p(y,z)=f(h(y,z),z)\left\lvert \frac{ \partial h }{ \partial y } \right\rvert$ 从而边际密度函数为 $p(y)=\left\lvert \frac{ \partial h }{ \partial y } \right\rvert \int_{-\infty}^{\infty} f(h(y,z),z) \, dz$

Theorem (次序统计量分布)

设 $X_{i}$ 独立同分布，概率密度函数和分布函数分别为 $f(x)$ 和 $F(x)$ ，此时

次序统计量 $X_{(k)}$ 密度函数为 $g(y_{k})=\frac{n!}{(k-1)!(n-k)!}(F(y_{k}))^{k-1}(1-F(y_{k}))^{n-k}f(y_{k})$
当 $y_{k}\leq y_{j}$ 时，次序统计量 $X_{(k)}$ 和 $X_{(j)}$ （ $1\leq k\leq j\leq n$ ）的联合密度函数为 $\begin{align*}g(y_{k},y_{j})=&\frac{n!}{(k-1)!(j-1-k)!(n-j)!}(F(y_{k}))^{k-1}\\&(F(y_{j})-F(y_{k}))^{j-k-1}(1-F(y_{j}))^{n-j}f(y_{k})f(y_{j})\end{align*}$
当 $y_{1}\leq y_{2}\leq\dots\leq y_{r}$ ，前 $r$ 个次序统计量联合密度函数为 $g(y_{1},y_{2},\dots,y_{r})=\frac{n!}{(n-r)!}(1-F(y_{r}))^{n-r}f(y_{1})\dots f(y_{r})$

1.4 复合抽样法

Theorem (复合抽样法)

设随机变量 $n$ 的分布函数和概率密度函数分别为 $F(x)$ 和 $f(x)$ ，并且可以写成 $F(x)=\sum_{j = 1}^{k} p_{j}F_{j}(x)\quad \text{或}\quad f(x)=\sum_{j = 1}^{k} p_{j}f_{j}(x)$ 其中 $p_{j}\geq0$ , $\sum_{j = 1}^{k}p_{j}= 1$ ， $F(x)$ 和 $f(x)$ 分别是随机变量 $\xi_{j}$ 的分布函数和概率密度函数。
利用复合抽样法产生随机数的步骤如下：

产生 $U\sim U(0,1)$ ，若 $U\in\left[ \sum_{j = 1}^{i-1}p_{j},\sum_{j = 1}^{i}p_{j} \right)$ ，令 $j=i$
产生分布函数为 $F_{j}(x)$ 或概率密度函数为 $f_{j}(x)$ 的随机数,记为 $\eta$ 。
则 $\eta$ 满足上式的分布函数和概率密度函数。

1.5 近似抽样法

Theorem (正态分布近似抽样)

设 $\{ \xi_{1},\xi_{2},\dots,\xi_{m} \}$ 为独立同分布的随机变量序列，其数学期望 $\mu$ 和方差 $\sigma^{2}$ 存在。则其和的标准化形式 $\eta_{m}=\frac{1}{\sqrt{ m }\sigma}\left( \sum_{i = 1}^{m} \xi_{i}-m\mu \right)$ 满足中心极限定理。随机变量 $\eta_{m}$ 的分布函数记为 $F_{m}(x)$ ，有 $\lim_{ m \to \infty } F_{m}(x)=\Phi(x)$ 即 $\eta_{m}\stackrel{d}{\longrightarrow}N(0,1)$

Definition (Bulter抽样法)

产生 $R\sim U(0,1)$ ，令 $k=[mR+1]$
产生概率密度函数为 $g_{k(x)}$ 的随机数。独立产生 $U_{1},U_{2}\sim U(0,1)$ ，当 $U_{2}\leq d_{k}$ 时，令 $\eta=\begin{cases} x_{k-1}+(x_{k}-x_{k_{1}})\sqrt{ U_{1} }, & f(x_{k})>f(x_{k-1}) \\ x_{k}-(x_{k}-x_{k-1})\sqrt{ 1-U_{1} },& f(x_{k})<f(x_{k-1}) \end{cases}$ 当 $U_{2}>d_{k}$ 时，令 $\eta=x_{k-1}+(x_{k}-x_{k-1})U_{1}$ ，则由此得到 $\eta$ 为近似服从分布的 $f(x)$ 的随机数。

2. 离散分布随机数的抽样法

Theorem (逆变换法)

设 $\{ x_{i} \}$ 为离散型随机变量 $\xi$ 所有可能的取值， $p_{i}$ 是 $\xi$ 取 $x_{i}$ 概率，即 $P\{ \xi=x_{i} \}=p_{i}$ ， $\xi$ 的分布函数为 $F(x)=P\{ \xi\leq x \}=\sum_{x_{i} \leq x}p_{i}$ 。则

产生 $R\sim U(0,1)$
如果 $R\leq F(x_{1})$ ，则令 $\xi=x_{1}$ ；如果 $F(x_{i-1})<R\leq F(x_{i})$ ，则令 $\xi=x_{i}$
则 $\xi$ 是分布 $F(x)$ 的随机数。