Generating uniform random variable from biased coin flips

[Somefantastik]

I need help getting started on this.

Want to generate a random variable X, equally likely 0, 1, using biased coin (heads probability p).

1. Flip coin, result is labled $$0_{1}$$
2. Flip coin, result is labeled $$0_{2}$$
3. $$0_{1} = 0_{2}$$=> return to step 1
4. $$0_{2}$$= heads => X = 0, $$0_{2}$$ = tails => X = 1

Show X is equally likely to be 0 or 1.

A good place to start would be showing P{X = 0} = P{X = 1}. Can you show me how to find those two probabilities?

 

[mathman]

In order to get past step 3, you have to have had one head and one tail on the two flips. Since the probs of HT and TH are equal, step 4 will give you 2 equiprobable results.

 

[Somefantastik]

Keeping in mind that this is a biased coin, can someone please show me how to explicitly find P{X = 0}? I understand that it is equal to 1/2 but I need to see how to get there.

 

[mathman]

Prob(HT)=Prob(TH)=p(1-p). Prob(get to step 4) is 2p(1-p), therefore prob(X=0)=prob(X=1)=p(1-p)/(2p(1-p))=1/2.

 

[Somefantastik]

Is there a simpler way to do this where you continuously flip a coin until the last 2 results are different, that sets X = 0 if the final flip is a head, X = 1 if final flip is a tail?

 

[mathman]

Is there a simpler way to do this where you continuously flip a coin until the last 2 results are different, that sets X = 0 if the final flip is a head, X = 1 if final flip is a tail?

No. A sequence of heads followed by one tail has a different probability than a sequence of tails followed by one head. You always need to start fresh as described in your original statement.