Coin flipping to get a random digit

  • Thread starter Zafa Pi
  • Start date
  • Tags
    Random
In summary, the lowest value for 4.6 is the expected number of flips to get a random (uniform) digit in [0,15].
  • #1
Zafa Pi
631
132
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?
 
Physics news on Phys.org
  • #2
What is relationship between the coin flips and the random digit?
 
  • #3
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) + ...
 
  • #4
Zafa Pi said:
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)?
 
  • #5
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.
 
  • #6
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.
 
  • #7
Oh my, I just found a method that gives 4+6/11 rather than 4+6/10.
 

FAQ: Coin flipping to get a random digit

How does coin flipping produce a random digit?

Coin flipping is a simple and accessible method for generating a random digit. The act of flipping a coin creates an equal probability of landing on either heads or tails, resulting in a 50% chance of obtaining a 0 or 1. This randomness is the basis for using coin flipping as a means of obtaining a random digit.

Is coin flipping truly random?

While coin flipping is often considered a random method, it is not completely random. Factors such as the weight of the coin, the force applied during the flip, and the surface it lands on can affect the outcome. However, for practical purposes, coin flipping is considered a good enough method for generating a random digit.

Can coin flipping be used for more than just obtaining a 0 or 1?

Yes, coin flipping can be used to get a random digit beyond just 0 or 1. This can be achieved by assigning heads to represent one digit and tails to represent another digit. For example, heads can represent 0 and tails can represent 2, resulting in a 33.3% chance of getting either digit.

Why is coin flipping used as a method for obtaining random digits?

Coin flipping is a simple and convenient method that does not require any specialized equipment or technology. It is also widely known and easily understood, making it a popular choice for generating random digits in situations where more complex methods may not be available.

Are there any alternative methods for obtaining random digits?

Yes, there are various alternative methods for obtaining random digits, such as dice rolling, random number generators, and shuffling cards. Each method has its own advantages and limitations, and the choice often depends on the specific needs and constraints of the situation.

Similar threads

Replies
2
Views
2K
Replies
41
Views
5K
Replies
4
Views
2K
Replies
45
Views
4K
Replies
9
Views
2K
Back
Top