时间复杂度为O(1)的抽样算法——别名采样(alias sample method)

  当我们得到一个概率分布,如何根据这个概率分布抽样是一个常见的问题。这篇文章将介绍alias method(别名采样),这种算法的运行时间复杂度为O(1)的,当然提前需要复杂度为O(n)的预处理。下面我将通过一个例子介绍别名采样算法。

问题背景

  假设一共存在A,B,C,D四种情况,它们的概率分别为 0.3,0.1,0.1,0.5。如何实现按概率抽样呢?
  比较常用的一种方法是生成一个数组:1,2,2,3,3,3,4,4,4,4,其中1对应A,2对应B,以此类推。然后随机在数组中抽取一个即可。这种方法简单易实现,但是这是仅仅有4种情况时。当情况变多,这种方法就会占用很大的空间了,所以并不适用于大规模的通用情况。
  另外,可以根据它们的概率密度分布生成累积分布:0.3,0.4,0.5,1。然后生成一个0-1之间的随机数,看它落在哪个区间。然而,这时需要与临界点进行比较。我们知道,插入有序数列最好的时间复杂度为O(logn),所以这种方法复杂度较大。
  我们这篇文章提到的alias method可以实现以运行复杂度为O(1)的方式抽样。当然它需要预处理预处理的时间复杂度为O(n),但是重复跑的时候,运行时间复杂度低才是重要的。

别名采样算法

  下面介绍alias method的处理过程。
  我们知道等概率分布抽样的时间复杂度为O(1),考虑一种情况,如果A,B,C,D概率分布均为0.25,那我们随机生成1,2,3,4,抽中哪个就是哪个,复杂度自然为O(1),这是等概率分布抽样的情况
  我们知道二项不等概率分布抽样的时间复杂度也为O(1),如果只有两个变量,比如A,B概率分布为 0.2,0.8.那我们用累积分布的方法,小于0.2就是A, 大于就是B,只需比较一次,所以复杂度也是O(1),这是二项分布抽样的情况
  alias method就是把这两种方法结合起来。
  仍然以本文一开始提出的例子为例。原来的概率分布如下,我们用绿色代表A,蓝色代表B,紫色代表C,橙色代表D:
原始
首先我们把原概率分布乘以N(为后面的拼接做准备),这里是N=4。得到:1.2,0.4,0.4,2.0,如图所示。
乘4后
  我们把它拼成等概率分布和二项不等概率分布:
处理后
  注意拼接的过程中,每一列最多有两种情况,这样才能让每一列都符合二项分布。
  做完以上处理后,我们就可以开始抽样了。首先我们以等概率分布抽一列,然后生成一个0-1之间的随机数。
  举例来说,例如我们首先抽中了第四列(概率为0.25)。然后在第四列中进行二项分布抽样,如果小于0.8,绿色,代表A,反之,就是橙色,代表D。这两个操作的复杂度均为O(1),故总时间复杂度也为O(1)。
  那么这样抽样是正确的吗?换句话说,在原概率分布中抽到A的概率是0.3,那使用alias方法抽到的概率还是0.3吗?
  我们仍然以抽取A情况为例。原来抽中a的概率为0.3。运用alias method方法后,抽中a的概率为抽中第一列+抽中第四列且随机数小于0.2,算起来为0.25+ 0.25 * 0.2) = 0.3,完全一样。

参考文献

1, http://blog.csdn.net/sky_zhe/article/details/10051967
2, https://www.cnblogs.com/zqiguoshang/p/5885455.html