9
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – cardinal
    Sep 15, 2013 at 15:37
  • $\begingroup$ 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! $\endgroup$ Sep 15, 2013 at 15:54
  • $\begingroup$ Here is a great paper with psuedo code for exactly what you want to do: arxiv.org/pdf/1304.1916v1.pdf $\endgroup$
    – user25658
    Sep 15, 2013 at 16:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – cardinal
    Sep 15, 2013 at 16:47
  • 1
    $\begingroup$ @ren: Please consider formulating an answer based on your discovery. I, for one, will be happy to upvote. Cheers. :-) $\endgroup$
    – cardinal
    Sep 15, 2013 at 16:48

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.