Coin flipping to get a random digit

[Zafa Pi]

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?

 

[mathman]

What is relationship between the coin flips and the random digit?

 

[Zafa Pi]

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) + ...

 

[D H]

4*(10/16) + 5*(6/16)*(5/6) + 8*(1/16)*(10/16) + ...

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

 

[Zafa Pi]

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.

 

[Zafa Pi]

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.

 

[Zafa Pi]

Oh my, I just found a method that gives 4+6/11 rather than 4+6/10.