# Generating discrete uniform from coin flips

Suppose you have a fair coin which you can flip as many times as you want (possibly countably infinite). Is it possible to generate the discrete uniform distribution on $(1,2,...,k)$, where $k$ is NOT a power of 2? How would you do it?

If this is too general, answering $k=3$ would probably be interesting enough.

• Sure! And, the $k=3$ case is actually instructive. Think about flipping coins in pairs (repeatedly, as necessary). What are the possible outcomes? Now, can you map the outcomes of the results of this procedure in such a way to get the desired distribution? – cardinal Sep 15 '13 at 15:37
• Oh right. That's nice. For example, HH=1, HT=2, TH=3, and TT=reflip the pairs. Hohoho, now I'm thinking about entropy from the coin flips and how the information from flips can be maximised (: But I'll do that myself! – renrenthehamster Sep 15 '13 at 15:54
• Here is a great paper with psuedo code for exactly what you want to do: arxiv.org/pdf/1304.1916v1.pdf – user25658 Sep 15 '13 at 16:05
• @renrenthehamster: Yes, it's $O(\log_2 k)$ because, if we define "success" as obtaining a valid outcome from the $\log_2 k$ flips, then the probability of success is always $\geq 1/2$. So, the number of such trials is geometric with a mean less than or equal to 2. Also, the probability of needing more than $m$ such trials decreases exponentially. – cardinal Sep 15 '13 at 16:47
• @ren: Please consider formulating an answer based on your discovery. I, for one, will be happy to upvote. Cheers. :-) – cardinal Sep 15 '13 at 16:48

Like I said above in my comments, the paper http://arxiv.org/pdf/1304.1916v1.pdf, details exactly how to generate from the discrete uniform distribution from coin flips and gives a very detailed proof and results section of why the method works.

As a proof of concept I coded up their pseudo code in R to show how fast, simple and efficient their method is.

#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)")