假设你有一枚公平的硬币，你可以随意翻转它（可能无限次）。是否可以在上生成离散均匀分布， 在哪里不是 2 的幂吗？你会怎么做？
如果这太笼统，请回答可能会很有趣。
从硬币翻转生成离散均匀
机器算法验证
随机生成
均匀分布
2022-03-27 03:03:44
1个回答
就像我在上面的评论中所说的那样，论文http://arxiv.org/pdf/1304.1916v1.pdf详细说明了如何从硬币翻转的离散均匀分布中生成，并给出了一个非常详细的证明和结果部分，说明了为什么方法有效。
作为概念证明，我编写了他们的伪代码，R以展示他们的方法是多么快速、简单和高效。
#Function for sampling from a discrete uniform distribution
rdunif = function(n){
v = 1
c = 0
a = 0
while(a > -1){
v = 2*v
c = 2*c + rbinom(1,1,.5) #This is the dice roll part
if(v >= n){
if(c < n){
return(c)
}else{
v = v-n
c = c-n
}
}
}
}
#Running the function k times for n = 11
n = 11
k = 10000
random.samples = rep(NA,k)
for(i in 1:k){
random.samples[i] = rdunif(n)
}
counts = table(random.samples)
barplot(counts,main="Random Samples from a Discrete Uniform(0,10)")
