# How to prove uniform distribution of $m\oplus k$ if $k$ is uniformly distributed?

All values $m, k, c$ are $n$-bit strings. $\oplus$ stands for the bitwise modulo-2 addition.

How to prove uniform distribution of $c=m\oplus k$ if $k$ is uniformly distributed? $m$ may be of any distribution and statistically independant of $k$.

For example you have a $m$-bit string that is with probability p=1 always '1111...111'. Adding it bitwise to a random $k$-bit string which is uniformly distributed makes the result also uniformly distributed. Why?

-
$\oplus$ is the bitwise xor operation ? –  mercio Jul 12 '13 at 11:54
yes the sign stands for bitwise xor operation. –  Yannick Wald Jul 12 '13 at 13:06

If $X$ is a (vector) random variable that takes on each of the $2^n$ values $$\{00\cdots 00, \quad 00\cdots 01,\quad 00\cdots 10,\quad \ldots\ , \quad 11\cdots 10,\quad 11\cdots 11\}$$ with equal probability $2^{-n}$, then for any fixed $n$-bit vector $m$, $Z = X\oplus m$ also has the same distribution since for all choices of $n$-bit vector $a$ we have that $$P\{Z = a\} = P\{m\oplus X = a\} =P\{X = m\oplus a\} = 2^{-n}\tag{1}$$ But suppose that $Y$ is another random variable taking on the same $2^n$ values with arbitrary distribution (including the possibility that $Y$ takes on some values with probability $0$) and suppose that $Z = X \oplus Y$. Given that the event $\{Y = m\}$ occurs, suppose that the conditional distribution of $X$ conditioned on $\{Y = m\}$ is uniform on the $2^n$ values of $X$. Then, we have that $$P\{Z = a\mid Y = m\} = P\{X\oplus Y = a\mid Y = m\} = P\{X = m\oplus a \mid Y = m\} = 2^{-n}. \tag{2}$$ Equation $(2)$ shows that $P\{Z = a \mid Y = m\}$, the conditional probability that $Z = X\oplus Y$ equals $a$ given that $Y = m$ is $2^{-n}$. If $(2)$ holds for all $m$, then since the unconditional probability that $Z = a$ is, by the law of total probability, a weighted sum of the conditional probabilities, we also have that $$P\{Z = a\} = \sum_m P\{Z=a\mid Y = m\}P\{Y = m\} = 2^{-n}\sum_m P\{Y = m\} = 2^{-n}.$$ Note that we have implicitly assumed that $X$ and $Y$ are independent because we have assumed that for all choices of $m$, the conditional distribution of $X$ given that $\{Y = m\}$ is a uniform distribution on the $2^n$ values of $X$, that is the conditional distribution of $X$ is the same regardless of the choice of the value of $Y$.

Two points are worth noting here.

• It is not necessary that $Y$ also be uniformly distributed on the $2^n$ values as long as $X$ and $Y$ are assumed to be independent. In fact, as $(1)$ indicates, $Z = X\oplus Y$ is uniformly distributed on the $2^n$ even if $Y$ is a degenerate random variable taking on value $m$ with probability $1$. (Note that even in this case, $X$ and $Y$ are independent random variables nonetheless).

• While $X$ and $Y$ being independent is sufficient for $Z$ to inherit the uniform distribution on the $2^n$ values that $X$ enjoys, independence of $X$ and $Y$ is not necessary either. For example, with $n=2$ and $X$ uniformly distributed on $\{00, 01, 10, 11\}$, consider the joint distribution given below: $$P\{X = 00, Y = 00\} = \frac{1}{4}, \quad P\{X = 11, Y = 00\}= \frac{1}{4},\\ P\{X = 01, Y = 11\} = \frac{1}{4}, \quad P\{X = 10, Y = 11\}= \frac{1}{4},$$ where $X$ and $Y$ are clearly not independent, $Y$ is not uniformly distributed on $\{00, 01, 10, 11\}$ (though it is uniformly distributed on $\{00, 11\}$), and yet $Z$ is uniformly distributed on $\{00, 01, 10, 11\}$ just as $X$ is.

-
this proof is very convincing! –  Yannick Wald Jul 12 '13 at 13:10
if $P\{Y = X\} > 2^{-n}$ we get $P\{X\oplus Y = 0\} > 2^{-n}$ so it can't be uniformly distributed. I don't think there is any simple condition except independance of $X$ with $Y$ that makes $X \oplus Y$ uniformly distributed. –  mercio Jul 12 '13 at 14:12
@mercio You are correct. I have changed my answer accordingly. –  Dilip Sarwate Jul 14 '13 at 3:59
+1. Dissects very clearly the situation. –  Did Jul 14 '13 at 8:42
@Did Thanks for the upvote. I have added a couple of paragraphs at the end that might interest you. I wonder what the necessary conditions are for $Z=X\oplus Y$ to be uniformly distributed since independence of $X$ and $Y$ is not necessary, merely sufficient. –  Dilip Sarwate Jul 15 '13 at 17:12
This is not true. For example, if $m = k$, $c$ is not uniformly distributed.
I'm pretty sure that the question requires that $m$ is distributed independently of $k$, so I disagree with this answer. –  Twiceler Jul 12 '13 at 12:16
I would have read it that way if there were no mention of the distribution of $m$ at all. –  Tunococ Jul 12 '13 at 12:28
yes, i forgot to mention that $k$ is independant of $m$. But does it matter at all? Can $k$ be uniformly distributed and still statistically dependant of $m$? –  Yannick Wald Jul 12 '13 at 13:05
in my opinion, if $c$ is a zero string, because of $m=k$, $c$ is still uniformly distributed, because the zero-string can still be randomly picked from the whole range of n-bit strings. –  Yannick Wald Jul 12 '13 at 13:23