蓄水池抽样、或者水库抽样(reservoir sampling)是一种online算法，实现等概率随机抽样。

问题描述

情形 1，你需要从海量样本（总数量未知）中等概率抽取k个数据。

情形 2，当前时刻数据库里没有数据，此后每秒中都会一个新数据进入数据库，k+1秒之后，你需要从数据库中等概率抽取k个数据，并且保证每时每刻这k个数据都是从数据库中等概率抽取的。

一般解决方法

情形 1，先把数据数一遍，得到个数之后，再开始等概率抽取。

情形 2，从第k+1秒开始，每一秒都从整个数据中重新抽取k个。

蓄水池抽样算法

情形 1， 先取出数据库中的前k个数据，然后开始读取下一个数据，我们以k/(k+1)的概率保留这个数据，并且从之前的k个数据中随机挑选一个丢弃，以1/(k+1)的概率不做任务操作。我们继续读取下一个数据，我们以k/(k+2)的概率保留这个数据，并且从之前保留的k个数据中随机挑选一个丢弃，以2/(k+2)的概率不做任何操作。归纳起来，对于第j个数据，我们以k/j的概率保留这个数据，并且从之前保留的k个数据中随机挑选一个丢弃，以(j-k)/j的概率不做任何操作。反复进行，直到遍历完整个数据库。

情形 2， 类似地，一开始我们先保留前k秒产生的数据，此后，第j秒的时候（j > k），我们以k/j的概率保留这个数据，并且从之前保留的k个数据中随机挑选一个丢弃，以(j-k)/j的概率不做任何操作。

相比于一般解决方法，蓄水池的优势显而易见！时间上少了，不用不停地遍历整个数据库来随机抽取，更重要的时候，不用保存历史数据，只需要保存k个已经被选择的数据。省时间、省空间！

有$n$个样本，我们有放回的随机从中抽取$n$次。

在第一次抽取时，样本A被选中的概率是$\frac{1}{n}$，不被选中的概率自然就是$1-\frac{1}{n}$。每次抽取都是独立的，所以当抽完$n$次之后，A一次都没有被抽中的概率就是

$$(1-\frac{1}{n})^n.$$

这个式子眼熟吗？这个就是高等数学中那个著名的极限

$$\lim_{n\rightarrow\infty}(1-\frac{1}n)^n=\frac{1}{e}.$$

所以当bootstrap样本总数很大的时候，任意一个样本被抽中的概率就是$1-\frac{1}{e}\approx1-\frac{1}{2.71828}\approx0.632$。

这个问题一直没人回答，我讲一下我的理解。

有时候大规模抽样的成本很高，所以我们就需要一些技巧。滚雪球抽样就是这种技巧，它本质上就是“一传十，十传百”。基本步骤是：

1. 从一个小的范围内抽取符合条件的样本

2. 从符合条件的样本顺藤摸瓜，从每个合格样本在小范围外有联系的样本中再挑出合格样本

3. 反复

这个方法常用在社交网络，比如说要调查喜欢极限运动的人，这种人的总体很小，所以对整体人口调查基本上大海捞针。突破口就是：

1. 先找到一两个喜欢极限运动的人

2. 看他们的朋友(在网络结构里就是一度连接)里有哪些人也是喜欢极限运动的

3. 再看朋友的朋友

这样就会很快收集到足够多的样本

我觉得“Jackknife被称为简单版的Bootstrap”这句话并不准确。由于早年还没有计算机，JackKnife是当时时代的产物，但是现在基于计算机生成随机的抽样越来越方便，bootstrap才越来越普遍。

bootstrap是通过对样本反复有放回地抽样来估计某个估计量的均值、方差等等。

jackknife的思想则是leave one out。比如样本量是10，jackknife则产生10个子样本，每个子样本中有9个数据点，然后通过者10个子样本，来估计估计量的均值、方差等等。（留取样本的方式类似于k-fold cross validatation）

bootstrap和cross-validation本质上是完全两回事。

bootstrap说白了就是有放回的抽样。它的目的是降低estimate的variance。

1. 比如我们可以用bootstrap的方法数值上计算假设检验的p值。

2. 比如我们可以用bootstrap的方法来估计一个总体的某个统计量（比如均值、中位数）

3. 比如建模的时候用bootstrap的方法来选训练样本，得到多个训练模型。对多个模型组合，这个就是Bagging，Bootstrap aggregating。

cross-validation是进行模型验证的。cross-validation中的fold是随机选的，但是绝对不是bootstrap，因为fold抽样不是有放回的。

parametric bootstrap是先假定一个先验分布，然后反复抽样来估计这个分布中的参数，从而确定这个分布，最终可以得到所感兴趣的统计量。

nonparametric bootstrap是非参的，没有模型假设，直接从经验分布中反复抽样，最终来估计感兴趣的统计量。

比如你对df随机选10行

> df[sample(nrow(df), 10), ]

它们比较像，但是不完全一样。

当我们想要获得某个观测量$y$，但是$y$可能不易获得。于是我们借助于某个辅助变量$x$（这个变量比较容易获得）。两阶段抽样是先从总体里随机选取一批样本$S_1$，然后观测每个样本的辅助变量$x$，根据$x$再从$S_1$中挑选一批样本，作为最后的样本来估计$y$。

分层抽样是直接根据某个指标分布来进行抽样，比如想调查某地区小朋友的营养状况，该地区男孩550，女孩450人，所以抽样的时候也是按照这个比例，比如可以抽样22个男生，18个女生。

AB test中分成对照组和实验组，在实验开始前，对照组和实验组的样本和样本相关属性应该是同分布的。

但是实际过程中，由于对照组的样本和实验组的样本都是人为选定的，所以很难做到同分布，往往有偏差，这种偏差就是选择偏差(selection bias)。

比如想通过AB test检验一本辅导教材的效果，对照组是一个普通中学的全体学生，实验组是一个重点中学的全体学生。这两所学校的学生就不是同分布的。

比如想通过AB test检验一个在线汽车广告的效果，对照组是青年女性用户，实验组是中年男性用户。这两批人群也不是同分布的。这样选择样本都会有选择偏差。要做到无偏差，一般会通过完全随机取样。

通俗的讲.如果你想要测试两个产品的好坏，例如网站1.0和2.0。那么单独将拿给两波人用，再进行反馈统计，用户对网站的好评率就是比较的指标。

selection bias就是个来源于测试群体的“样本选择偏差”。再举个例子，例如两种型号键盘通过abtest比较好坏。得到统计结果实验者用a键盘错字率2%，b键盘错字率5%。看上去a键盘更好吧？但如果a键盘实验者是个程序员b键盘实验者是个小白呢？因为测试群体随机性，正如楼上的重点中学和普通中学学生能力不同。会导致*不客观结果*

MAB就是老虎机游戏，老虎机有很多台，每台赚钱的概率不同，Thompson Sampling需要一边探索各个老虎机赚钱的概率，一边又想保证自身的收益。

算法其实很简单，假定你能从一个老虎机赚钱的概率为p，每个老虎机都保持一个beta分布的参数，在没有足够数据的情况下可以假设先验分布为beta(1,1)。每次试验后，选中一个老虎机，摇一下，有收益则该机的wins增加1，否则该机的lose增加1。 

每次选择机器的方式是：用每个机器现有的beta分布产生一个随机数b，产生的随机数中最大的那个机器去摇。