How to show that $y=Px$ is distributed like binary $x$ for random permutation $P$?

Question

Drawing a random binary vector $X\in\{0,1\}^n$ from the uniform distribution, the probability $\mathbb{P}(X=x)$ to get a specific $x\in\{0,1\}^n$ is known ($=\frac{1}{2^n}$).

Let $P\in\{0,1\}^{n\times n}$ be one of the $n!$ possible permutation matrices drawn uniformly.

It seems obvious, that $y=Px$ is distributed like $x$, i.e. $\mathbb{P}(Y=y)=\mathbb{P}(X=x)$.

Is it true? How to show it formally?

Answer 1

joriki's symmetry argument is the best, of course, but here is the computation. We proceed by conditioning on the value of the random matrix $P$. Note that we use the crucial (unstated) assumption that $X$ and $P$ are independent; however $P$ need not be uniformly distributed. \begin{eqnarray*} \mathbb{P}(PX=y) &=&\sum_Q \mathbb{P}(PX=y\mid P=Q)\,\mathbb{P}(P=Q)\\[5pt] &=&\sum_Q \mathbb{P}(QX=y\mid P=Q)\,\mathbb{P}(P=Q)\\[5pt] &=&\sum_Q \mathbb{P}(QX=y)\,\mathbb{P}(P=Q)\\[5pt] &=&\sum_Q \mathbb{P}(X=Q^{-1}y)\,\mathbb{P}(P=Q)\\[5pt] &=&\sum_Q {1\over 2^n} \,\mathbb{P}(P=Q)\\[5pt] &=&{1\over 2^n}. \end{eqnarray*}

Answer 2

This is true by symmetry. Since the entire process is invariant under inversion of any of the coordinates, the distribution must be, too, and the only distribution with this invariance is the uniform one.