Suppose you have a fair coin that can be flipped independently for an unbounded

Question

Suppose you have a fair coin that can be flipped independently for an unbounded number of times. PROBLEM: Is it possible to design a procedure that samples a number uniformly random over {1, 2, 3, 4, 5, 6} ?. This means that we simulate a fair die. Consider the following cases with analysis (correctness, running time):

- An algorithm that never fails and outputs the correct distribution perfectly, but might not terminate

- An algorithm that might fail, but the output is the perfectly correct under the condition that the algorithm does not fail.

- An algorithm that does not fail and outputs almost correctly.

Suppose you can simulate a fair die using a fair coin (either perfectly or almost correctly). ANSWER ALSO SHOULD - Argue that this implies you can generate random output over {1,2,3,4,5} as well (perfectly or almost correctly, respectively). The argument should be simple (i.e. using only one sentence).

Explanation / Answer

Follow the below steps to find an algorithm that terminates but also gives an accurate answer:

Since 6/8 of the possible outcomes lead to termination in each set, the probability of needing more than l sets of flips to get a die roll is (16/8)^l = 1/(4^l).
Therefore, this method gives results accurately and terminates in practice.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.