Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Coin flipping to get a random digit

  1. Jan 18, 2014 #1

    Zafa Pi

    User Avatar
    Gold Member

    The lowest value for {the expected number flips of a fair coin to get a random (uniform) digit} seems to be 4.6.
    Can you prove this?
    Can this be beat with a biased coin?
     
  2. jcsd
  3. Jan 18, 2014 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    What is relationship between the coin flips and the random digit?
     
  4. Jan 18, 2014 #3

    Zafa Pi

    User Avatar
    Gold Member

    By flipping a fair coin 4 times you can generate a random (uniform) integer in [0,15]. If that integer is in [0,9] you've now got a random digit, if not you must do some more flipping. There is no fix finite number of flips that will suffice, but the best procedure I can find will get a random digit with the expected number of flips being 4.6:
    4*(10/16) + 5*(6/16)*(5/6) + 8*(1/16)*(10/16) + ...
     
  5. Jan 18, 2014 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    What do you mean by that cryptic expression?

    You have to be very careful how you are doing the rejection sampling. If the generated number is 10 or more and you completely redo a set of four coin flips you will indeed have a random digit between 0 and 9. That procedure however leads to the expected number of flips being about 6.4, not 4.6. If you are doing something more creative, have you made sure that you truly are a generating a random digit (i.e., p(0) = p(1) = p(2) = … = p(9) = 1/10)?
     
  6. Jan 18, 2014 #5

    Zafa Pi

    User Avatar
    Gold Member

    OK, I gave the calculation for my procedure, the procedure is this: if after the 1st 4 flips you are in [0,9] done. If > 9 subtract 10 and you get a random # (assume uniform unless otherwise stated) in [0,5]. Now make one more flip to get 0 or 1 and multiply that by 6 and add it to the # in [0,5]. What you get is a random # in [0,11], if that # is in [0,9] done, otherwise subtract 10 to get either 0 or 1 50/50. Count that bit as one flip and make 3 more flips to end up with a total of 8 flips with a fresh 4 flips and start over.
    So you see I don't need to completely start over again if the 1st 4 flips gives a # > 9.
     
  7. Jan 18, 2014 #6

    Zafa Pi

    User Avatar
    Gold Member

    D H - Thank you BTW for for making it clear that I should have included my recipe to begin with. I feel quite confident that it's the best that can be done, but I don't have a proof. And I don't know if one can do better with a biased coin.
     
  8. Jan 18, 2014 #7

    Zafa Pi

    User Avatar
    Gold Member

    Oh my, I just found a method that gives 4+6/11 rather than 4+6/10.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Coin flipping to get a random digit
  1. Flip a coin (Replies: 8)

  2. Coin flipping (Replies: 6)

  3. Coin flip (Replies: 3)

  4. Flipping coin (Replies: 8)

Loading...