我想快速生成离散随机数,我有一个已知的CDF。本质上,该算法是:高效地生成离散随机数
- 构建CDF矢量(0,1)随机数
u
- 如果
u < cdf[1]
选择(从0开始以1增加矢量和结束)cdf
- 产生均匀1
- 否则,如果
u < cdf[2]
选择2 - 否则,如果
u < cdf[3]
选择3 * ...
- 如果
例
首先产生CDF:
cdf = cumsum(runif(10000, 0, 0.1))
cdf = cdf/max(cdf)
接着生成N
均匀随机数:
N = 1000
u = runif(N)
现在采样值:
##With some experimenting this seemed to be very quick
##However, with N = 100000 we run out of memory
##N = 10^6 would be a reasonable maximum to cope with
colSums(sapply(u, ">", cdf))
而作为“如果替换为真,则使用沃克的别名法(里普利,1987年)时,有超过250个合理可能的值”,它是有效的时间复杂度是O(n)的 – colinfang 2013-11-21 14:52:21