Biasedness of the XOR variable of two independent biased boolean variable

hiren_garai

8/26/24, 3:39 AM

My question is very basic one. Suppose there are two independent boolean variable $X_1$ and $X_2$. It is given that $X_1$ is biased towards $0$ and $X_2$ is biased towards $1$ with same amount of bias. Now will their XOR variable be biased or unbiased ?

My try: Since their bias is same, probability that $X_1$ takes $0$ value is same as the probability of the $X_2$ variable taking value $1$. If we assume the probability to be $p$, then we have $\Pr[X_1 \oplus X_2 =0] = \Pr[X_1 =0, X_2 =0] + \Pr[X_1 =1, X_2 = 1] = p(1-p)+p(1-p) = 2p(1-p)$, which may not be equal to $0.5$ always. Hence their XOR variable is not unbiased.

Is this approach right ? Also can we use the piling up lemma to show that it is biased ?

Thanks in advance.

1 + 0

xor

linear-cryptanalysis

probability

Score:2

Crypto

kodlu

8/26/24, 4:05 AM

I don't understand your question. What you wrote is exactly the piling up lemma. Solving the quadratic $$ 2p(1-p)=\frac{1}{2} $$ shows that the XOR is unbiased if and only if the two original variables are unbiased.

You had the constraint that they had the same bias in magnitude but in opposite directions. If you relax that, you can have a more general solution, i.e., if the probabilities of being 1 are $p$ and $q$ then you need to solve the more general bivariate quadratic $$ p(1-q)+q(1-p)=\frac{1}{2} $$ and obtain the conditions for unbiasedness.

Edit:

The generalized version of this problem is the study of linear cryptanalysis. You have constant vectors say $a,b \in \{0,1\}^n,$ and vector random variables, say $X,Y=S(X)$ where $S$ is some mapping (usually an S-box). Then you study the distribution (in particular bias of) the quantity $$ a \cdot X \oplus b \cdot Y $$ as $X$ varies over $\{0,1\}$ according to some distribution. I suggest the tutorial by Heys, available here, as a good starting point. You could also have $k\times n$ matrices $A,B$ and study the distribution of $$ A \cdot X \oplus B \cdot Y. $$

+ 3

hiren_garai

8/26/24, 4:48 AM

Actually I was informally thinking the XOR to be unbiased, but that was not matching with the formal calculation so, I was confused. Your answer helped. One more doubt, if we had the ADDITION of the variables then also we would end up with a biased variable right ?(unless p = 0.5) @kodlu

kodlu

8/26/24, 4:50 AM

define what you mean by addition, what would be the value of $1+1$? it's not in the set $\{0,1\}$.

hiren_garai

8/26/24, 5:05 AM

I got the answer. If I define 1+1 = 0,then it would be the same as the XOR, if 1,then also it would be biased. Thank you. Can you suggest me any resource where I can find more problems like this ? @kodlu

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Biasedness of the XOR variable of two independent biased boolean variable

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.