Coin flipping to get a random digit

  • Context: Undergrad 
  • Thread starter Thread starter Zafa Pi
  • Start date Start date
  • Tags Tags
    Random
Click For Summary

Discussion Overview

The discussion revolves around the expected number of flips of a fair coin required to generate a random digit uniformly distributed between 0 and 9. Participants explore various methods and calculations related to this problem, including the potential for improvement using biased coins.

Discussion Character

  • Exploratory
  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant claims that the expected number of flips for a fair coin to generate a random digit is 4.6 and asks for proof.
  • Another participant questions the relationship between coin flips and the generation of a random digit.
  • A method is proposed where flipping a fair coin 4 times can yield a uniform integer in [0,15], with further steps required if the integer exceeds 9, leading to an expected number of flips of 4.6.
  • A participant challenges the initial claim, suggesting that a different rejection sampling method could lead to an expected number of flips closer to 6.4 instead of 4.6.
  • One participant describes a specific procedure involving conditional steps based on the results of the initial flips, asserting that it allows for fewer total flips than starting over completely.
  • A participant expresses confidence in their method being optimal but admits to lacking a formal proof and questions whether a biased coin could yield better results.
  • Another participant mentions discovering a method that results in an expected number of flips of 4 + 6/11, indicating ongoing exploration of the problem.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the expected number of flips required, with multiple competing views and methods presented. The discussion remains unresolved regarding the optimal approach and the potential for improvement with biased coins.

Contextual Notes

Some calculations and assumptions regarding uniformity and the effectiveness of different methods are not fully resolved, and the discussion includes various interpretations of the rejection sampling technique.

Zafa Pi
Messages
631
Reaction score
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
What is relationship between the coin flips and the random digit?
 
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) + ...
 
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)?
 
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.
 
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.
 
Oh my, I just found a method that gives 4+6/11 rather than 4+6/10.
 

Similar threads

Undergrad Random variable vs Random Process
  • · Replies 2 ·
Replies
2
Views
2K
High School Is the Coin Biased Towards Heads? Statistical Test and Conclusion
  • · Replies 21 ·
Replies
21
Views
3K
MHB Rejecting the Hypothesis of a Fair Coin: Confidence Level?
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Probability of 10 consecutive tails with 30 coin flips
  • · Replies 20 ·
Replies
20
Views
3K
Undergrad How many tosses to flip a coin HHTH?
  • · Replies 41 ·
2
Replies
41
Views
9K
Undergrad Average Number of Coin Flips to Reach a certain Head-Tail Difference?
  • · Replies 18 ·
Replies
18
Views
4K
Graduate What Is the Probability of a Third Head After Two Heads with a Biased Coin?
  • · Replies 8 ·
Replies
8
Views
2K
MHB The Probability of a Biased Coin: n Flips, m Heads
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Type 1 Error Increases with Sample Size?
  • · Replies 9 ·
Replies
9
Views
4K
Undergrad Guessing a coin toss correctly
  • · Replies 6 ·
Replies
6
Views
2K