累积法-Gibbis采样中的一个疑点

大家好，我是Pancho,今天记录一下我在LDA中遇到的一个算法，仅仅是理解，可能也有错误。

1.上帝玩一个掷骰子：骰子有K个面，每个面投到的概率不一致，每一个面上面有对应的一个数字。请聪明的人类来帮助上帝设计一个算法，随机投掷骰子，然后得到骰子某个面上的数字。

2.好，我作为人类的代表，呲溜地窜到了上帝面前，咳咳，?(?‘ω‘?)? 说道：“亲爱的上帝，我来帮助你完成这个任务。”然后，上帝微微点头，表示允诺。

这个算法，主要的是怎么随机投掷到面，然后获取面的数字。

3.算法如下

?

步骤1：初始化数组p[]

骰子的每个面的概率就是 array[ ]里面每个index都有对应的概率值array[i]，我们把每个面对应的数字就看成是index=0,1,2,3...，也就是看作列表元素的下标。

步骤2：这里先拷贝array到数组p.

步骤3：然后逐项累加，从第2想开始，每一个都是前面2个面的概率和，最后一位是所有的概率和，这里总概率和可以不为1。

比如：p[1/3,1/5,2/15,1/15],则经过第四步骤后，p变为p[1/3,8/15,10/15,11/15].

步骤4：设置u,u=随机数[0,1]*p[last index],u就是一个0-1的随机数乘以所有概率的和，上一步已经存到了最后一位数组中了。

步骤5：比较累积和与u的大小，若某项index的累积和大于u,则表示该index的累积概率足够大于随机概率。弹出index即可。完成。

这个算法一次只玩一个号。要达到所有面都弹出来，外面还要加循环。

4.参考

《LDA漫游指南》P56