Suppose you are given a coin for which the probability of heads, say p , is unkn

Question

Suppose you are given a coin for which the probability of heads, say p, is unknown. How can you use this coin to generate unbiased, i.e., Pr[H] = Pr[T] = 1/2, coin flips?
Give an algorithm for which the expected number of flips of the biased coin for extracting one unbiased coin flip is no more than 1/[p(1 p)].

1. Describe your algorithm in pseudocode. Comment your code.

2. Prove that your algorithm is correct.

3. Analyze your algorithm: what is the expected number of trials that your algorithm performs? Justify your answer.

Explanation / Answer

1) The coin gives head with probability P and tail with the probability (1-P). Lets represent heads with 1 and tails with 0. We consider two cases of biased coin for a fair coin head or tail. Lets call them case1 and case2. The case of fair coin head is (case1=1 and case2=0) and tail is (case1=0 and case2=1). The probability for both of them is P(1-P). Psuedo code is

int throwcoin()

{

//This function returns 1 with probability P and 0 with probability (1-P)

}

int faircoin()

{

int case1 = throwcoin();

int case2 = throwcoin;

if(case1==1 and case2==0)return 1;

if(case1==0 and case2==1)return 0;

return faircoin();

}

2) The algorithm is correct because it gives head and tail with same probability. They will eventually give head or tail with the probability P*(1-P). So the number of tries taken to give a result is 1/P*(1-P)

3) The expected number of trails is 1/P*(1-P)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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