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.

**Answer**

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

**Attribution***Source : Link , Question Author : renrenthehamster , Answer Author : Community*