Alias采样算法

1. 离散分布

离散分布：给你一个概率分布，是离散的，比如 [ 1 2 , 1 3 , 1 12 , 1 12 ] [\frac{1} {2}, \frac {1} {3}, \frac {1} {12}, \frac {1} {12}] [21​,31​,121​,121​]，代表某个变量属于事件 A A A的概率为 1 2 \frac{1} {2} 21​， 属于事件 B B B的概率为 1 3 \frac {1} {3} 31​，属于事件 C C C的概率为 1 12 \frac {1} {12} 121​，属于事件 D D D的概率为 1 12 \frac {1} {12} 121​。

离散分布的随机变量的取样问题：
一个随机事件包含四种情况，每种情况发生的概率分别为： 1 2 , 1 3 , 1 12 , 1 12 \frac{1} {2}, \frac {1} {3}, \frac {1} {12}, \frac {1} {12} 21​,31​,121​,121​，问怎么用产生符合这个概率的采样方法。

2. 时间复杂度为o(N)的采样算法

首先将其概率分布按其概率对应到线段上，像下图这样：

接着产生0~1之间的一个随机数，然后看起对应到线段的的哪一段，就产生一个采样事件。比如落在0 ~ 1/2之间就是事件A，落在1/2~5/6之间就是事件B，落在5/6 ~ 11/12之间就是事件C，落在11/12~1之间就是事件D。

复杂度分析：

• 如果顺序查找线段的话，查找时间复杂度为O(N)，
• 如果二分查找的话，查找的时间复杂度为O(logN)。

3. 时间复杂度O(1)的采样算法————Alias

3.1 做表

将概率分布的每个概率乘上N，画出柱状图。其中N为事件数量。

其总面积为N，可以看出某些位置面积大于1某些位置的面积小于1。将面积大于1的事件多出的面积补充到面积小于1对应的事件中，以确保每一个小方格的面积为1，同时，保证每一方格至多存储两个事件，这样我们就能看到一个1*N的矩形。

表里面有两个数组：

• 一个数组存储的是事件i占第i列矩形的面积的比例，即 P r a b [ 2 / 3 , 1.1 / 3 , 1 / 3 ] Prab[2/3, 1. 1/3, 1/3] Prab[2/3,1.1/3,1/3]
• 另一个数组存储第i列中不是事件i的另一个事件的编号,即 A l i a s [ 2 , n u l l , 1 , 1 ] Alias[2,null,1,1] Alias[2,null,1,1]

3.2 采样

1. 产生两个随机数
2. 第一个产生一个1~N 之间的整数 i，决定落在哪一列
3. 第二个产生一个0~1之间的随机数，判断其与 P r a b [ i ] Prab[i] Prab[i]大小
4. 采样
   • 如果小于 P r a b [ i ] Prab[i] Prab[i]，则采样 i i i
   • 如果大于 P r a b [ i ] Prab[i] Prab[i]，则采样 A l i a s [ i ] Alias[i] Alias[i]