9

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.

renrenthehamster
  • 387
  • 4
  • 7
  • 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: http://arxiv.org/pdf/1304.1916v1.pdf –  Sep 15 '13 at 16:05
  • @renrenthehamster: Yes! It's not the most efficient algorithm, but it shows an intuitive idea behind it. Similar approaches work much more generally. This question may be of some interest to you. – cardinal Sep 15 '13 at 16:29
  • @BabakP: What are you referring to in your comments? The example scheme was meant to be illustrative rather than optimal, but it's already not far off. In particular, an analogous scheme for general $k$ requires only $\lceil \log_2 k\rceil$ coins and the uncoded "remainder" is always smaller than $k$, for any $k$. So, on average it takes no more than $2 \log_2 k$ flips. That's already of the same order as the algorithm in the paper you link to! – cardinal Sep 15 '13 at 16:34
  • Perhaps I misread what he was suggesting. I thought if say $k=4$ then you would need HHH,HTH,HHT,THH,...etc and that would grow as $k$ did. –  Sep 15 '13 at 16:37
  • @BabakP: What I meant is find the smallest power of 2 larger than or equal to k, and then flip that number of coins, discarding enough combinations so that we are back to uniform on k. Landing on those discarded combinations would demand reflipping. So it's probably O(logk) algorithm – renrenthehamster Sep 15 '13 at 16:42
  • 1
    @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
  • 1
    @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

1 Answers1

5

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

enter image description here