Question

Suppose that we want to generate a random variable \(X\) that is equally likely to be either 0 or 1 , and that all we have at our disposal is a biased coin that, when flipped, lands on heads with some (unknown) probability \(p\). Consider the following procedure: 1\. Flip the coin, and let \(0_{1}\), either heads or tails, be the result. 2\. Flip the coin again, and let \(0_{2}\) be the result. 3\. If \(0_{1}\) and \(0_{2}\) are the same, return to step 1 . 4\. If \(0_{2}\) is heads, set \(X=0\), otherwise set \(X=1\). (a) Show that the random variable \(X\) generated by this procedure is equally likely to be either 0 or 1 . (b) Could we use a simpler procedure that continues to flip the coin until the last two flips are different, and then sets \(X=0\) if the final flip is a head, and sets \(X=1\) if it is a tail?

Short answer

In summary, the given procedure generates a random variable X with equal probabilities for both outcomes (0 and 1), as shown by P(X=0) = P(X=1) = p*(1-p). The proposed simpler procedure, which continues flipping the coin until the last two flips are different and sets X=0 if the final flip is a head or X=1 if it is a tail, also provides equal probabilities for X=0 and X=1 and can be used as an alternative.

Step-by-step solution

Understanding the given procedure

The given procedure consists of the following steps: 1. Flip the coin and record the result (0₁). 2. Flip the coin again and record the result (0₂). 3. If both results are the same, repeat steps 1-2. 4. If 0₂ is heads, set X=0. If 0₂ is tails, set X=1. Now, let's analyze this procedure.

Finding probabilities

We have two outcomes for each flip, heads (H) and tails (T): - First flip: \(0_{1}\) = H with probability p; \(0_{1}\) = T with probability (1-p). - Second flip: \(0_{2}\) = H with probability p; \(0_{2}\) = T with probability (1-p). The pairs of outcomes for both flips are: (HH), (HT), (TH), (TT). Their probabilities are: - P(HH) = p*p = \(p^2\) - P(HT) = p*(1-p) - P(TH) = (1-p)*p = p(1-p) - P(TT) = (1-p)*(1-p) = \((1-p)^2\) According to the given procedure, we only consider the cases where the outcome of two flips are different (HT or TH). So, let's calculate P(X=0) and P(X=1) using the probabilities of these cases.

Probabilities of X

Based on the procedure: - X = 0 when \(0_{2}\) is heads, i.e., the pair is (HT). - X = 1 when \(0_{2}\) is tails, i.e., the pair is (TH). So, - P(X=0) = P(HT) = p*(1-p) - P(X=1) = P(TH) = p*(1-p) As we can see, the probabilities of X = 0 and X = 1 are equal. Now let's analyze the simpler procedure proposed in (b).

Simpler procedure

The simpler procedure suggests to continue flipping the coin until the last two flips are different, and then set X=0 if the final flip is a head, and set X=1 if it is a tail. We must show that this procedure also returns equal probabilities for X = 0 and X =1. Let's consider the sequence of flips: - If the first two flips are already different (HT or TH), we immediately have equal chances for X, as shown above. - If the first two flips are the same (HH or TT), we continue flipping: - If the first two flips were HH, then P(HT)=p*(1-p). As before, HT defines X=0, and we do not proceed further with TH because the first two flips were not different. - If the first two flips were TT, then P(TH)=p*(1-p). As before, TH defines X=1, and we do not proceed further with HT because the first two flips were not different. The proposed simpler procedure also satisfies the condition of equal probabilities for X=0 and X=1, so it can be used as an alternative.