Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

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.$

StackExchange Computer Science Q#100068, answer score: 3