0
$\begingroup$

Let $a_1,\dots,a_n$ and $b_1,\dots,b_n$ be independent random binary strings of length $k$. Let $A$ be the bitwise exclusive OR (that is the XOR) of all the binary strings $a_i$ and let $B$ be the bitwise exclusive OR of all the binary strings $b_i$.

What is the $P(A=B)\;?$

$\endgroup$
  • $\begingroup$ I wonder if there any reason to believe that the chance is not $0.5^k$ ? try to think of it in inductive manner.Note that XOR with a given number is Injective function. that is: $x$ XOR $y$ = $x$ XOR $z$ implies $y=z$. Moreover, if you know that $z$ = $x$ XOR $y$ , and only $z$ and $x$ are known, you can deduce from the equation unique value of $y$ $\endgroup$ – d_e Jul 28 '16 at 15:45
  • $\begingroup$ @d_e Shouldn't it also depend on $k$? $\endgroup$ – user66307 Jul 28 '16 at 15:47
  • $\begingroup$ I missed that. you right. the chance is not dependent of $n$ , but only on $k$. $\endgroup$ – d_e Jul 28 '16 at 15:48
  • $\begingroup$ @d_e OK so the key point is that it is independent of $n$. That's interesting. $\endgroup$ – user66307 Jul 28 '16 at 15:50
2
$\begingroup$

For $1 \leq i \leq n$ and $1 \leq j \leq k$:

Let $a_{ij}$ be the $j$th bit of string $a_i$, and let $b_{ij}$ be the $j$th bit of string $b_i$.

Define $x \oplus y$ as $x$ xor $y$, and define $x \parallel y$ as the concatenation of $x$ and $y$.

Then $A = \parallel_{j=1}^{k}\bigoplus_{i=1}^{n} a_{ij}$ and $B = \parallel_{j=1}^{k}\bigoplus_{i=1}^{n} b_{ij}$.

We want to know the probability that $A=B$, or when $\parallel_{j=1}^{k}\bigoplus_{i=1}^{n} a_{ij} = \parallel_{j=1}^{k}\bigoplus_{i=1}^{n} b_{ij}$

Since each bit column is independent, and the bits are assigned randomly, we can compute the result for a single column and extend this to the rest of the columns.

In other words, $P(A=B) = P\left(\bigoplus_{i=1}^{n} a_{i1} = \bigoplus_{i=1}^{n} b_{i1}\right)^k$.

This is the same as asking when $(\bigoplus_{i=1}^{n} a_{i1}) \oplus (\bigoplus_{i=1}^{n} b_{i1}) = 0$, since $x \oplus x = 0$. And this is the same as asking when $(\bigoplus_{i=1}^{2n} c_{i1}) = 0$ for some randomly-assigned bitcolumn $c_{i1}$.

The probability that a sequence of random bits xors to $0$ is the same as the probability that there is an even number of $1$'s present, which occurs with probability $1/2$ overall, independent of $n$.

$$P(A=B) = \frac{1}{2^k}$$

$\endgroup$
1
$\begingroup$

With no other information provided:

  • A and B are uniformly distributed in the same sample space
  • The size of that sample space is $2^k$
  • Hence $P(A=B)=\frac{2^k}{2^k\cdot2^k}=\frac{1}{2^k}$
$\endgroup$
0
$\begingroup$

the chance is $0.5^k$. that chance in independent of $n$

here we will give the proof by induction on the length of $n$. We will show that the chance to have each sequence after $N$ XOR operations is the same and equal to $0.5^N$

  • for $n=1$ the is is clear, that the chance for every sequence is $0.5^k$

  • for $n=m+1$ if we XOR the first $m$ elements, we know by the the chance for every sequence is the same. Now we have to XOR 2 random sequences (the first is the XOR result of the first $m$ elements, and the second is the $m+1$ element). the XOR of 2 pure random sequence is a pure random sequence. that is because XOR on a given number, is both injective and Surjective function.

so, if we XOR $a_n$ sequence, we get result, $x$. but the chance that $x$ will be the result of the XOR of $b_n$ sequence is $0.5^k$

$\endgroup$

Your Answer

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