討論下算法導(dǎo)論第5章一道概率題

meistudios

好題。我想樓上的算法是對(duì)的。
rejection sampling，隨機(jī)數(shù)生成的range是[0..next_pow_of_2(n))，合法段是[0..n)。如果生成的數(shù)落在合法段就接受。否則重新sample。
顯然最終結(jié)果是合法段上的均勻（整數(shù)）分布。
期望的接受概率是 n / next_pow_of_2(n)，嚴(yán)格大于1/2.
期望運(yùn)行的時(shí)間是log(n)，也就是log(b -a ).
更具體點(diǎn)是上限 (log2(b - a) + 1) * next_pow_of_2(n) / n * time_of_call_random(0, 1).