1700537167
1700537168
分析与解答
1700537169
1700537170
首先需要明确的是，计算机程序都是确定性的，因此并不能产生真正意义上的完全均匀分布随机数，只能产生伪随机数（伪随机数是指这些数字虽然是通过确定性的程序产生的，但是它们能通过近似的随机性测试）。另外，由于计算机的存储和计算单元只能处理离散状态值，因此也不能产生连续均匀分布随机数，只能通过离散分布来逼近连续分布（用很大的离散空间来提供足够的精度）。
1700537171
1700537172
一般可采用线性同余法（Linear Congruential Generator）来生成离散均匀分布伪随机数，计算公式为
1700537173
1700537174
1700537175
，
1700537176
1700537177
（8.1）
1700537178
1700537179
也就是根据当前生成的随机数xt来进行适当变换，进而产生下一次的随机数xt+1。初始值x0称为随机种子。式（8.1）得到的是区间[0,m−1]上的随机整数，如果想要得到区间[0,1]上的连续均匀分布随机数，用xt除以m即可。
1700537180
1700537181
可以看出，线性同余法得到的随机数并不是相互独立的（下一次的随机数根据当前随机数来产生）。此外，根据式（8.1），该算法最多只能产生m个不同的随机数，实际上对于特定的种子，很多数无法取到，循环周期基本达不到m。如果进行多次操作，得到的随机数序列会进入循环周期。因此，一个好的线性同余随机数生成器，要让其循环周期尽可能接近m，这就需要精心选择合适的乘法因子a和模数m（需要利用代数和群理论）。具体实现中有多种不同的版本，例如gcc中采用 的glibc版本：
1700537182
1700537183
1700537184
1700537185
1700537186
但不管怎样，由计算机程序实现的随机数生成器产生的都是伪随机数，真正的随机数只会存在于自然界的物理现象中，比如放射性物质的衰变，温度、气流的随机扰动等。有一些网站可以提供基于大自然的随机现象的随机生成器，有兴趣的读者可以尝试一下。图8.1是通过大气噪声来产生随机数，可以说是“货真价实”的真随机数生成器了。
1700537187
1700537188
1700537189
1700537190
1700537191
图8.1 闪电产生大气噪声
1700537192
1700537193
·总结与扩展·
1700537194
1700537195
面试时，面试官还可能会针对线性同余法进行深入提问，比如，线性同余法中的随机种子一般如何选定？如果需要产生高维样本或大量样本，线性同余法会存在什么问题？如何证明上述线性同余发生器得到的序列可以近似为均匀分布（伪随机数）？
1700537196
1700537197
1700537198
1700537199
1700537200
百面机器学习：算法工程师带你去面试 [:1700532214]
1700537201
百面机器学习：算法工程师带你去面试 03 常见的采样方法
1700537202
1700537203
1700537204
1700537205
场景描述
1700537206
1700537207
对于一个随机变量，通常用概率密度函数来刻画该变量的概率分布特性。具体来说，给定随机变量的一个取值，可以根据概率密度函数来计算该值对应的概率（密度）。反过来，也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样。因此，从某种意义上来说，采样是概率密度函数的逆向应用。与根据概率密度函数计算样本点对应的概率值不同，采样过程往往没有那么直接，通常需要根据待采样分布的具体特点来选择合适的采样策略。
1700537208
1700537209
知识点
1700537210
1700537211
逆变换采样，拒绝采样，重要性采样
1700537212
1700537213
问题 抛开那些针对特定分布而精心设计的采样方法，说一些你所知道的通用采样方法或采样策略，简单描述它们的主要思想以及具体操作步骤。
1700537214
1700537215
难度：★★★☆☆
1700537216