没有看过上一篇的同学请看正态分布随机数的生成 (1)。
求反变换固然还可行，但是碰到无法解析求逆的函数，用数值方法总归比较慢。下面我们就来说说另一个能够适合任何概率密度分布的方法——接受—拒绝法 (Acceptance-Rejection Method)，国内也有翻译成叫做舍选法的。接受—拒绝法的思路其实很简单——比如说你想要正态分布，我们就弄个方框框把它框起来，然后均匀地往里面扔飞镖。扔到曲线以下我就留着，扔到曲线以上就不要了。这样搞好以后来看，曲线之下的点就是（二维）均匀分布的。那这些点的横坐标就正好满足我们要的分布——高的地方的点就多，低的地方的点就少嘛。
正态分布——听起来非常耳熟，用起来也很顺手——因为很多语言都已经内置了有关正态分布的各种工具。但其实，在这个最普遍、最广泛的正态分布背后，要生成它还有很多学问呢。
$$f(x \; | \; \mu, \sigma) = \frac{1}{\sigma\sqrt{2\pi} } \; e^{ -\frac{(x-\mu)^2}{2\sigma^2} }$$
难道教科书上没有讲吗？看看概率书上是怎么说的……比如我手头这本浙大版的《概率论与数理统计》（第四版）第 378 页上说……“标准正态变量的分布函数 $\Phi(x)$ 的反函数不存在显式，故不能用逆变换法产生标准正态变量……”
Continue reading “正态分布随机数的生成 (1)”
前面说的是均匀抽样，要是想加个权怎么办呢？先说加权有什么用呢？比如我们已经统计好了搜索的关键字和词频，那么有了加权就可以直接用这个数据来抽样而无需把关键字重复好多遍了。
我们先来看看这个抽样应该是怎么样的。假设这总共 $n$ 项都摆在你面前了，设第 $i$ 项的权值为 $w_i$，那么我们抽到这一项概率应该是
$$P_i = \frac{w_i}{w_1 + w_2 + \cdots + w_n}$$
我们现在来看看，如果把这 $n$ 项按照第 $n$ 项、第 $n-1$ 项、…… 第 $2$ 项、第 $1$ 项的顺序抽出来，这个概率是多少。因为这 $n$ 项的顺序是可以随便摆的，所以它求出来是有一定普遍意义的。
第一次抽出第 $n$ 项的概率是
$$P_n(1) = \frac{w_n}{w_1 + w_2 + \cdots + w_n}$$
第 $n$ 项已经被抽走了，那第二次抽到第 $n-1$ 项的概率是
$$P_{n-1}(2) = \frac{w_{n-1}}{w_1 + w_2 + \cdots + w_{n-1}}$$
以此类推，按照这个顺序抽出所有元素的概率就是
$$P(S) = \prod_{i=1}^n \frac{w_i}{w_1+w_2+\cdots w_i} $$
这有什么用呢？别着急，先记下这个结果，我们下面来说说算法怎么做。
没有看过前一篇的同学请看这里：蓄水池抽样浅说 (1)
前面介绍的方法都很好，但是要计算 $n-k$ 个随机数实在是有点浪费时间…… 有兴趣的同学可以把那个调用函数换成比如 reservoirSample(range(10**8), 10**5)，就知道这东西还是要算上一会儿的了。
再来看看这个过程吧——把前 $k$ 个元素放进去之后，随机决定接下来的元素要不要放进去，但是每次决定时都需要产生一个随机数。要是我们能够确定应该跳过多少个元素，不就可以省掉很多生成随机数的工夫了吗？每一步过程就变成了
我们有时候会有进行数据抽样的需要，比如要从文件中随机取出若干行，或从数据集中随机取出若干数据进行分析。通常情况下这并不是什么难事，比如 Python 中直接提供了 random.sample() 来做这件事，Numpy 中更提供了功能更为强大的 numpy.random.choice()。然而这些东西都有一个问题，就是你必须把整个数据集读到内存里。如果数据集超出了内存的限制，或者要对一个持续的输入流做抽样，即从包含 $n$ 个项目的集合中（等概率）选取 $k$ 个样本，其中 $n$ 为很大或未知，又该怎么做呢？
