0
$\begingroup$

If $X_i$'s are $3$ independent random variables defined over $\{0,1\}$ with biases $\epsilon_i$'s for $1\le i \le 3 \;$ and $\epsilon_1 = \epsilon_3 = 0.$ Then $X_1 \oplus X_2$ and $X_2 \oplus X_3$ are independent.

What I have done is, since $\epsilon_1 = \epsilon_3 =,$ hence $\Pr[X_1 = 0] = \frac{1}{2} = \Pr[X_3 =0].\\\\$ Also since $X_i$'s are independent, hence $X_1\oplus X_2, \;X_2 \oplus X_3$ and $X_3 \oplus X_1$ are uniform over $\{0,1\}.$

Now, $\Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b] = \dfrac{\Pr[X_1\oplus X_2 = b, X_2 \oplus X_3 = b]}{\Pr[X_2 \oplus X_3 = b]}, b\in \{0,1\}.$

$X_1\oplus X_2 = b, X_2 \oplus X_3 = b \implies X_1 \oplus X_3 = 0$ and $\Pr[X_1 \oplus X_3 = 0] = \frac{1}{2},$

We know $\Pr[X_2 \oplus X_3 = b] =\frac{1}{2}.$ Hence $\Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b] = 1.$

But $\Pr[X_1 \oplus X_2 = b] = \frac{1}{2}.$ Since $\Pr[X_1 \oplus X_2 = b] \neq \Pr[X_1\oplus X_2 = b \mid X_2 \oplus X_3 = b]$ so they are not independent.

What am I missing ? This is a question from Douglas R. Stinson's book "Cryptography-Theory and Practise" with question number $4.12$, page $134.$ Can anyone help me through this. Thank you.

$\endgroup$
1
$\begingroup$

If two binary RVs are uniform, they are independent if and only if the probability that they are equal is the same as the probability that they are unequal (so knowing one does not help in guessing the other). $$ P[X_1 \oplus X_2=X_2\oplus X_3]=P[X_1=X_3] =P[X_1\oplus X_3=0] $$ which is clearly $1/2$ since $X_1,X_3$ are unbiased and independent.

$\endgroup$
3
  • 1
    $\begingroup$ Also $Pr[X_1 \oplus X_2 \neq X_2 \oplus X_3] = \Pr[X_1 \neq X_3] = \Pr[X_1 \oplus X_3 = 1] = \frac{1}{2}$ due to the same unbiased and independence. Hence the probability of being equal of the two random variables is equal to the probability of being unequal. So they are independent. Is this right ? $\endgroup$ May 26 at 0:33
  • $\begingroup$ So where am I missing ? What is wrong in my work in the question ? Can you help me. Thank you $\endgroup$ May 26 at 0:35
  • $\begingroup$ An idea: It may be because the events on the top of your conditional probability expression are not disjoint but it seems like you are assuming them to be so; and carrying around the unspecific $b$ does not help the reasonong. $\endgroup$
    – kodlu
    May 26 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.