Question on random bits

Question

Sample a uniformly random bit. Let $X$ be the corresponding random variable.

Here is a randomized procedure to create two more output bits, denoted by random variables $Y_1$ and $Y_2$. To generate each output bit $Y$:

1. First toss $t$ fair coins. If all of these coins are heads, let $Y = X$.
2. Else, output a uniformly random $Y$.

I am trying to compute:

\begin{equation} \Pr[Y_1=x_1, Y_2=x_2], \end{equation}

for each of the bits $x_1 \in \{0, 1\}$ and $x_2 \in \{0, 1\}$.

---

Here is my attempt:

\begin{equation} \Pr[Y_1=x_1, Y_2=x_2] = \Pr[Y_1=x_1]\Pr[Y_2=x_2~|~Y_1=x_1]. \end{equation}

Now, for any $x_1 \in \{0, 1\}$,

\begin{align} \Pr[Y_1 = x_1] &= \Pr[X = x_1] \Pr[Y_1=x_1|X=x_1] + \Pr[X = \bar{x_1}] \Pr[Y_1=x_1|X=\bar{x_1}] \\ &= \frac{1}{2}\left(\frac{1}{2^{p}} + \left(1 - \frac{1}{2^{p}}\right)\frac{1}{2} \right) + \frac{1}{2} \left(1 - \frac{1}{2^{p}}\right)\frac{1}{2} \\ &= \frac{1}{2}. \end{align}

This is because $Y_1$ is filled with $X$ with probability $\frac{1}{2^{p}}$ and is a random bit with probability $1 -\frac{1}{2^{p}}$.

However, I cannot find the probability \begin{equation} \Pr[Y_2=x_2~|~Y_1=x_1]. \end{equation}

Answer 1

You can use the following equality: $$p(A) = \sum\limits_n p(A|B_n)p(B_n)$$

For you, $A=Y_2=x_2|Y_1=x_1$. I am using the notation $x^*$ for bit inversion

$$P[Y_2=x_2|Y_1=x_1] $$ $$= P[Y_2=x_2|Y_1=x_1, X=x_1]P[X=x_1] + P[Y_2=x_2|Y_1=x_1, X=x_1^*]P[X=x_1^*]$$

You know that $P[X=x_1]=P[X=x_1^*]=0.5$. You can calculate the rest in the same way that you calculated the other part.