之前一直用的是 Rand()%(range+1)，昨天发现这个有点问题，概率好像不太对，于是在网上查了发现如果 range 不能被 rand_max 整除的话，确实会出现问题，于是我想了一个解决方案，在这里提出来，想问问有没有什么 bug，思路就是 floor((Rand ()/rand_max)*range)，就是说先把产生的随机数平均分布在[0,1]里面再扩大到 range 里面，请问这种思路有什么 bug 吗？
手机发帖大家凑合看，不知道格式有没有什么问题……
This topic created in 2495 days ago, the information mentioned may be changed or developed.
 |
1
geelaw Aug 13, 2019 via iPhone
这个错误在于 rand()/(RAND_MAX+0.) 并不接近均匀分布的实数，而是离散分布的。
一个简单的做法是 rejection sampling，不过效率比较低。均摊效率更高的做法是批量型 rejection sampling （在把 rand 替换为真随机数后的 hybrid 是完美的分布），或者用 leftover hash lemma （但这样就不完美了）。 |
Select Language