水塘抽样与阶层固化
简单抽样
简单抽样算法就是从固定的n个元素里随机选出k个元素，这样每个元素被选的概率都是平等的k/n。简单抽样是最简单的抽样算法，同样也是使用最为普遍的算法。
简单抽样有个前提就是必须提前知道目标总体的大小n。我们看看python里面的简单抽样算法。
>>> import random
>>> random.sample([1, 2, 3, 4, 5], 3) # Choose 3 elements
[4, 1, 5]
>>> random.sample([1, 2, 3, 4, 5], 3) # Choose 3 elements
[5, 3, 1]
>>> random.sample([1, 2, 3, 4, 5], 3) # Choose 3 elements
[1, 4, 3]
python内置的简单抽样是无重复抽样，选出来的元素没有重复的。
再细看一下源码实现
def sample(self, population, k):
n = len(population)
if not 0 <= k <= n:
raise ValueError("sample larger than population")
random = self.random
_int = int
result = [None] * k
setsize = 21
if k > 5:
# setsize的值随着k的递增而递增
# k=1 setsize=4
# k=[2-5] setsize=16 + 21
# k=[6-21] setsize=64 + 21
# k=[22-85] setsize=256 + 21
# k=[86-341] setsize=1024 + 21
# ...
setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
if n <= setsize or hasattr(population, "keys"):
# 如果总数相对太小，就直接使用无放回抽样，因为有放回时重复性较大
# 每抽出一个元素，原始数组中该元素就空了，然后就被数组尾部的元素替换
# 数组长度也跟着减1，砍掉数组尾部的元素（不是物理砍掉，而是缩小随机范围）
pool = list(population) # 需要复制母体，如果母体太大，开销就大
# 如果是xrange，list()会强迫计算所有元素
for i in xrange(k): # 无放回抽k次
j = _int(random() * (n-i)) # 缩小随机范围，相当于砍掉数组尾部
result[i] = pool[j] # 抽到一个拿走
pool[j] = pool[n-i-1] # 用数组尾部元素替换被抽走的位置
else:
# 如果总数较大，有放回抽样时重复概率不高
# 尤其适用于xrange这种，无须算出所有元素，xrange是延迟计算的
# 所以可以使用有放回抽样 + 重复重试法
try:
selected = set() # 用于鉴定重复的容器
selected_add = selected.add
for i in xrange(k):
j = _int(random() * n)
while j in selected: # 重复了，就重试
j = _int(random() * n)
selected_add(j)
result[i] = population[j] # 抽中一个
except (TypeError, KeyError):
# 下面不用看了
if isinstance(population, list):
raise
return self.sample(tuple(population), k)
return result
代码为xrange这种延迟列表进行了优化，无须强制计算出所有元素即可以抽样，比如下面的代码可以瞬间出结果，因为len(population)和population[i]都是可以快速计算的。
>>> x=xrange(1,100000000000,8)
>>> random.sample(x, 5)
[683594665, 654156625, 493934665, 580926705, 506506385]
水塘抽样
区别于简单抽样，水塘抽样是一种动态的抽样方法。
抽样的目标总体有一个收集的过程，它是一个动态的过程。简单抽样是要等到这个动态过程彻底冷却下来了，确定了总体的数量之后才会进行一次性抽样。如果目标总体数量又增加了，就必须重新抽样。
动态抽样是渐进式的抽样，它的过程是持续性的。总体在变化，样本也跟着变化，在抽样的过程中是不知道最终会有多少总量的，也就是n不确定。
举个例子
原始的部落山寨之间要打战，寨主要选100人参战，而这个寨子里总共有999人。 于是寨主对这999人进行了简单的抓阄抽样，选出了100个人，准备送上战场，剩下的899人开心了。
但是这时突然有人告诉寨主，还有1个人刚刚从外地回来，其实总共有1000人。
这倒霉的100个被选中的人就觉得很不公平了，怎么这刚回来的人就不用筛了呢，这不公平，我们要重新筛选。他们想借此大做文章，这样就有机会不用打战了。
但是另外899人不同意，好不容易松弛下来，现在又要来一遍，我们不干。
那该怎么办呢？寨主很快想出了一个办法
可以让这个刚来的小伙伴进行一次抓阄，从1～1000的数中随机拿出一个数，看看它是否小于100，10%的概率。 如果小于100的话，很不幸，他就必须上战场。同时之前的100个抽中的人中可以随机一个被换下来。 这样就可以保证公平，而不会影响之前的900个幸运的人，还会给之前抽中的悲惨的100人带来一点点小惊喜。
如果接下来又冒出了一个人，那就可以接着上面的方法进行下去，而不会造成混乱。
其实整个过程可以理解为刚开始寨子里只有100人，就全部上战场。然后剩下的900人一个一个的冒出来，各进行一次随机，随机了900次，最终确定了上战场的100人选。
越是进行到后面，人选就越固定。因为抓阄的几率是不断变化的。从第101人时几率为100/101降低到最后一个人的几率为100/1000。
你会想，这是不是不太公平。其实这是公平的，虽然前面的人被筛进去的几率要高于后面的，但是越早进去的人也就有更大的几率被后面的人替换出来。而最后一个人一旦被筛进去了，就再无翻身的可能。
下面我们使用代码来实现水塘抽样
def reservoir_sampling(items, k):
# 第一波全部上战场，不用害怕，后面他们会渐渐被新人替换下来
sample = items[0:k]
for i in range(k, len(items)): # 随机n-k次
j = randrange(1, i + 1) # 抓阄
if j <= k:
# 很不幸，中标了，替换掉一个老家伙
sample[j] = items[i]
return sample
如果不考虑性能，我们完全可以使用水塘抽样来代替简单抽样。水塘抽样是可以实时看到动态的抽样结果的。
阶层固化
我们时常抨击时政，说中国的阶层固化了，上流的城堡，后面来的人挤破了头皮再也进不去。但是也偶有各种中国梦案例在我们身边在各种新闻里出现，告诉我们这不完全正确，城堡守卫虽然森严，进去还是有各种路子的。
如果我们将这个问题类比上面的水塘抽样，就会发现这在数学上是正常现象。
我们将抽样的目标k个样本位置比喻成那个城堡，n就是全体想往城堡里面挤的中国人。
在改革开放初期，并没有多少人在想着往城堡里面挤。所以n还是一个比较小的数，目标k个样本也是在急剧变化，所谓乱世出英雄也就是这个意思。
但是如今是和平年代，抽样过程已经持续了几十年之久了，城堡里的人选自然就渐渐固化下来了，但也不是完全固化的，后面的人还是有机会进入的，只是几率要小很多。而在城堡里面的人也不是完全稳固的，他们可能随时会掉下来，几率也很小。
数学证明
有条件的可以访问外国网站看youtube动画视频 Reservoir Sampling(https://www.youtube.com/watch?v=A1iwzSew5QY)
没条件的看看维基百科也是可以的 水塘抽样(https://zh.wikipedia.org/wiki/%E6%B0%B4%E5%A1%98%E6%8A%BD%E6%A8%A3)