文章标签 ‘算法’

正态分布随机数的生成 (2)

2015年11月16日 1 条评论

没有看过上一篇的同学请看正态分布随机数的生成 (1)

接受—拒绝法

求反变换固然还可行,但是碰到无法解析求逆的函数,用数值方法总归比较慢。下面我们就来说说另一个能够适合任何概率密度分布的方法——接受—拒绝法 (Acceptance-Rejection Method),国内也有翻译成叫做舍选法的。接受—拒绝法的思路其实很简单——比如说你想要正态分布,我们就弄个方框框把它框起来,然后均匀地往里面扔飞镖。扔到曲线以下我就留着,扔到曲线以上就不要了。这样搞好以后来看,曲线之下的点就是(二维)均匀分布的。那这些点的横坐标就正好满足我们要的分布——高的地方的点就多,低的地方的点就少嘛。

accept-rejection

阅读全文…

正态分布随机数的生成 (1)

2015年11月1日 没有评论

正态分布——听起来非常耳熟,用起来也很顺手——因为很多语言都已经内置了有关正态分布的各种工具。但其实,在这个最普遍、最广泛的正态分布背后,要生成它还有很多学问呢。

$$f(x \; | \; \mu, \sigma) = \frac{1}{\sigma\sqrt{2\pi} } \; e^{ -\frac{(x-\mu)^2}{2\sigma^2} }$$
normal

难道教科书上没有讲吗?看看概率书上是怎么说的……比如我手头这本浙大版的《概率论与数理统计》(第四版)第 378 页上说……“标准正态变量的分布函数 $\Phi(x)$ 的反函数不存在显式,故不能用逆变换法产生标准正态变量……”
阅读全文…

蓄水池抽样浅说 (3)

2015年10月23日 没有评论

加个权吧

前面说的是均匀抽样,要是想加个权怎么办呢?先说加权有什么用呢?比如我们已经统计好了搜索的关键字和词频,那么有了加权就可以直接用这个数据来抽样而无需把关键字重复好多遍了。

我们先来看看这个抽样应该是怎么样的。假设这总共 $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} $$

这有什么用呢?别着急,先记下这个结果,我们下面来说说算法怎么做。

阅读全文…

蓄水池抽样浅说 (2)

2015年10月22日 没有评论

没有看过前一篇的同学请看这里:蓄水池抽样浅说 (1)

跳跳跳!—— Algorithm X

前面介绍的方法都很好,但是要计算 $n-k$ 个随机数实在是有点浪费时间…… 有兴趣的同学可以把那个调用函数换成比如 reservoirSample(range(10**8), 10**5),就知道这东西还是要算上一会儿的了。

再来看看这个过程吧——把前 $k$ 个元素放进去之后,随机决定接下来的元素要不要放进去,但是每次决定时都需要产生一个随机数。要是我们能够确定应该跳过多少个元素,不就可以省掉很多生成随机数的工夫了吗?每一步过程就变成了

  • 确定该跳过多少个元素 $S(k, n)$
  • 跳过 $S(k, n)$ 个元素
  • 从前 $k$ 个元素中随机产生一个要替换的元素,用下一个元素替换

阅读全文…

蓄水池抽样浅说 (1)

2015年10月21日 没有评论

jar_of_marbles

我们有时候会有进行数据抽样的需要,比如要从文件中随机取出若干行,或从数据集中随机取出若干数据进行分析。通常情况下这并不是什么难事,比如 Python 中直接提供了 random.sample() 来做这件事,Numpy 中更提供了功能更为强大的 numpy.random.choice()。然而这些东西都有一个问题,就是你必须把整个数据集读到内存里。如果数据集超出了内存的限制,或者要对一个持续的输入流做抽样,即从包含 $n$ 个项目的集合中(等概率)选取 $k$ 个样本,其中 $n$ 为很大或未知,又该怎么做呢?

阅读全文…

素数求和的动态规划方法

2015年9月29日 没有评论

怎么求出从 $2$ 到 $N$ 之间的所有素数之和?

素数求和是数论中一个很典型的问题。这事情乍听起来并不难,只要把素数都求出来再加起来就好了嘛。可能你已经了解了一些求素数的方法,比如最简单的试除。写过这个程序的同学都知道这样搞有多慢。或者常用的是埃氏筛法,简单来说,就是列好从 $2$ 到 $N$ 的范围,先用 $2$ 去筛,把从 $2 \times 2$ 开始的 2 的倍数剔掉;再用下一个素数 3 筛,把 $3 \times 3$ 开始的 3 的倍数剔除掉…… 一直筛完不大于 $\sqrt{N}$ 所有素数为止。我直接从 wiki 上借了一个动画来演示这个过程,有兴趣的同学可以自己写一个试试看。

Sieve_of_Eratosthenes_animation

本文中的方法来自于解决了 ProjectEuler 全部问题的大神 Lucy_Hedgehog。
阅读全文…