Originally Posted by

**maria_stoeva** I have this problem to solve and I don't know where to start from and how to solve it. Would you help me, please?

We want to generate a r.v. X that is equaly likely to be 0 or 1.

We have a coin when flipped lands at Heads with probability p.

Consider the procedure

1. Flip the coin, and let O1, either heads of tails, be the result.

2. Flip the coin again, and let O2 to be the result.

3. If O1 and O2 are the same, return to step 1.

If O2 is heads, set X=0, otherwise set X=1

Show that the random variable X is equaly likely to be 0 or 1.

Could we use a simpler procedure that continues to flip the coin until the last 2 flips are different, and then sets X=0 if the final flip is a head, and sets X=1 if it is a tail?

You have to prove that $\displaystyle P(X=0)=1/2$.

Here's the idea. Because of the "loop", we are waiting for the first time when O1 and O2 differ. At that time, we have either "O1=tails and O2=heads" or "O1=heads and O2=tails". However, since O1 and O2 are obtained using the same coin, the two situations are equally likely. Hence the result.

Using this informal reasoning, you may however not understand why the simpler procedure doesn't work (indeed it doesn't). In order to show why it is important to use the first procedure (i.e. toss again the coin everytime), a more careful computation is necessary.

What does it mean that $\displaystyle X$ equals 0? It means that the coin was tossed a certain number $\displaystyle 2N$ of times, getting equal pairs of results $\displaystyle O_1=O_2$ every time, before finally we observe $\displaystyle O_1\neq O_2$ and $\displaystyle O_2=\mbox{Heads}$. We decompose the probability according to the value of $\displaystyle N$ (it is the number of times we have to go back to step 1):

$\displaystyle P(X=0)=\sum_{n=0}^\infty P(X=0, N=n)$.

(the comma means "and") Then, we note that $\displaystyle P(X=0,N=n)=P(O_1=O_2)^n P(O_2=\mbox{Heads}, O_1=\mbox{Tails})$ (indeed, it corresponds to $\displaystyle n$ matches before the first difference, and O2 is heads). A short computation then gives you $\displaystyle P(X=0)=1/2$.