從硬幣翻轉生成離散均勻

假設你有一枚公平的硬幣，你可以隨意翻轉它（可能無限次）。是否可以在上生成離散均勻分佈， 在哪裡不是 2 的冪嗎？你會怎麼做？

如果這太籠統，請回答可能會很有趣。

就像我在上面的評論中所說的那樣，論文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)")

引用自：https://stats.stackexchange.com/questions/70073