主题: 随机数问题
查看单个帖子
  #11 (permalink)  
旧 2008-04-06
liuxinyu 的头像
liuxinyu liuxinyu 当前离线
高级会员
 
注册日期: 2006-02-09
帖子: 311
文章: 49
liuxinyu 正向着好的方向发展
默认 回复: 随机数问题

给一个思路,用一个骰子可以随机获得1到6任何数字,现在用2个骰子,根据乘法原理,可以获得,6x6等于36种不同排列,并且均匀分布,采用6进制数,骰子1的点数-1,乘以6后加上骰子2的点数-1,就可以机会均等表示0-35。因此用k个骰子,就可以均匀表示0到6^k-1的范围。

值得注意的是,并不能用反复掷一个骰子然后将点数相加来获取1到6n之间的随机数,因为这样概率分布不均匀。

但是,如果n不是正好的6^k-1,则严格说,概率并不均匀。例如我希望通过2个dice,获取0到6这7个数字,必然从8到35代表的数字,超出范围,如果仅仅将结果模n,则就会面对鸽笼原理问题(或叫抽屉原则问题),必然某些数字的概率高,令一些概率低。

一个办法是丢弃,我考虑另一个调整办法,从rand ( m ) 生成rand ( n )。不失一般性,假设(m,n)=1。也就是互素。
首先,寻找k使得m^k<=n<m^(k+1)
令n和m^(k+1)-1的最小公倍数为lcm,并且令
n*p=lcm
(m^(k+1)-1)*p=lcm
我们把生成的随机数乘以q再处以p就将0到m^(k+1)-1均匀分布到0到n-1,附带的scheme代码如下,在MIT scheme上测试通过。
代码:
(define (find-power m n) (define (find-power-from k m n) (if (and (< (expt m k) n) (< n (expt m (+ k 1)))) k (find-power-from (+ k 1) m n))) (find-power-from 0 m n)) (define (generate k m) (if (= k 0) (random m) (+ (* (generate (- k 1) m) m) (random m)))) (define (rand-from n m) (let ((k (find-power m n))) (let ((upper-bound (- (expt m (+ k 1)) 1))) (let ((p (/ (lcm upper-bound n) n)) (q (/ (lcm upper-bound n) upper-bound))) (floor (/ (* (generate k m) q) p))))))

此帖于 2008-04-06 08:21 PM 被 liuxinyu 编辑.
回复时引用此帖