Generating discrete uniform from coin flips

Question

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 1

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