Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not.

Is $z = x \oplus y$ uniform?


Yes, if $x$ and $y$ are chosen independently of each other.

One way to quickly see this is to note that the map $x \mapsto x \oplus y,$ for some constant $y,$ is a permutation of $\{0,1\}^n.$ This means that if $x$ is uniformly distributed over $\{0,1\}^n$ and $y$ is constant, then $x \oplus y$ is also uniformly distributed. And since $x \oplus y$ is uniformly distributed for every constant $y,$ it follows that, if we make $y$ itself a random variable (independent of $x$), then the distribution of $x \oplus y$ will be a mixture of uniform distributions, and thus uniform.

Or we can just do the math:

$$\begin{aligned} {\rm P}(x \oplus y = a) &= \sum_{b \in \{0,1\}^n} {\rm P}(x \oplus y = a \land y = b) \\ &= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b \land y = b) \\ &= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b)\ {\rm P}(y = b) & (x \perp y) \\ &= \sum_{b \in \{0,1\}^n} \frac1{2^n}\ {\rm P}(y = b) & (x \sim \mathcal U\{0,1\}^n) \\ &= \frac1{2^n} \sum_{b \in \{0,1\}^n} {\rm P}(y = b) \\ &= \frac1{2^n}. \end{aligned}$$

However, the assumption of independence is absolutely necessary here — without it, it's easy to come up with counterexamples, such as letting $x$ be uniformly distributed over $\{0,1\}^n$ and letting $y = x,$ which of course implies that $x \oplus y = 0^n.$


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.