Distribution of a string of random variables

probability

Let $X_1,X_2,\cdots,X_{n-1}$ be iid random variables s.t. $X_i\in\{0,1\}$ w.p. $1/2$ each for $1\leq i \leq n-1$. Let $X_n=X_1+X_2+\cdots X_{n-1}(\mod 2)$. I am trying to find the distribution of the string $X_1X_2X_3\cdots X_n$?

Since $X_1,\cdots X_{n-1}$ are iid binary random bits, the string $X_1X_2\cdots X_{n-1}$ is uniform over $\{0,1\}^{n-1}$. But I am not sure how to take into account the definition of $X_n$ to find the distribution of the string $X_1X_2\cdots X_n$. Any ideas?

Best Answer

$X_n$ is a deterministic function of $X_1,\ldots, X_{n-1}$ so you're basically done. You can express it as "strings where the first $n-1$ bits are uniform over $\{0,1\}^{n-1}$ and where the $n$th bit is the number of $1$s in the first $n-1$ bits."

I'm guessing the more "elegant" expression would be "uniform over all $n$-bit strings with an even number of $1$s."

Related Question