50、随机采样技术全解析

随机采样技术全解析

1. 随机采样概述

许多算法都会用到随机数，这就要求我们能根据特定概率密度 $p(x)$ 从集合中选取元素 $x$。多次重复选取后，特定元素 $\tilde{x}$ 出现的频率应与概率 $p(\tilde{x})$ 成正比。下面将介绍从连续和离散随机变量中采样的通用技术。

2. 随机数生成器

2.1 真正随机数与伪随机数

计算机一般无法生成真正的随机数，原因有二：一是数字计算机只能用有限位数近似表示实数；二是计算机算法是确定性的，只能产生有限且可预测的输出，而真正的随机序列是无限且不可重现的。

在实际应用中，伪随机数序列通常就足够了。伪随机数由确定性程序生成，但具有随机数的一些关键特征：
- 序列值在 $[0, 1]$ 上均匀分布。
- 序列元素不相关。
- 即使知道已生成的所有元素，也很难猜出下一个元素的值。

2.2 伪随机数序列的验证

验证伪随机数序列 ${\xi_1, \xi_2, \ldots, \xi_R}$ 在 $[0, 1]$ 上的均匀分布相对容易，只需生成大量元素 $R$ 并绘制频率直方图，随着 $R$ 增大，直方图应快速收敛到均匀分布。检查序列中是否存在相关性稍难，原则上要检查任意阶的相关性，但实际上，两两不相关意味着 $(\xi_n, \xi_{n + 1})$ 在 $[0, 1]^2$ 上均匀分布，三项不相关意味着 $(\xi_n, \xi_{n + 1}, \xi_{n + 2})$ 在单位立方体上均匀分布。

验证伪随机数生成器生成的序列是否不可预测相对困难，大多数经典随机数生成器在特定参数值下会