Probability that a $(n, \frac12)$-binomial random variable is even

Question

Let $X$ be a $(n, \frac12)$-Binomial RV. Show that $X$ is even with probability $\frac12$.

Answer 1

A more general question might be "What is the probability that a $(n,p)$-Binomial random variable $X$ is even?" Generalizing on my hint on the main question, $$ \begin{align*} \left((1-p) + p\right)^n &= \sum_{k=0}^n\binom{n}{k}p^k(1-p)^{n-k}\\ &= \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k}p^{2k}(1-p)^{n-2k} + \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k+1}p^{2k+1}(1-p)^{n-(2k+1)}\\ &= P\{X~\text{even}\} + P\{X~\text{odd}\} \end{align*} $$ and $$ \begin{align*} \left((1-p)-p\right)^n &= \sum_{k=0}^n \binom{n}{k}(-p)^k(1-p)^{n-k}\\ &= \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k}p^{2k}(1-p)^{n-2k} - \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k+1}p^{2k+1}(1-p)^{n-(2k+1)}\\ &= P\{X~\text{even}\} - P\{X~\text{odd}\} \end{align*} $$ giving that $$P\{X~\text{even}\} = \frac{1}{2}(1 + (1-2p)^n) = \frac{1}{2} + \frac{1}{2}(1-2p)^n$$ which is $\frac{1}{2}$ if $p = \frac{1}{2}$ and converges to $\frac{1}{2}$ as $n \to\infty$ except when $p = 1$, in which case the probability alternates between $0$ and $1$ depending on the parity of $n$ (as is obvious without all the above calculation).

Answer 2

If $n$ is odd, this is clear by the symmetry $X \to n - X$. If $n$ is even, consider $X$ as the sum of a Bernoulli random variable and a Binomial with parameters $(n-1,1/2)$.

Answer 3

Of course you can realize $X$ as the number of heads obtained when flipping $n$ fair coins. Let's write $X_n$ instead of $X$ for the number of heads in $n$ coin flips; similarly $X_{n-1}$ will be the number of heads among the first $n-1$ coin flips.

Flip $n-1$ fair coins. You'll either have an even or an odd number of heads. It doesn't matter which.

If you have an even number of heads among the first $n-1$ coins, then you need to get a tail with the $n$th coin to have an even number of heads total. If you have an odd number of heads among the first $n-1$ coins, you need the last coin to be a head. In either case the "good" result (which makes the total even) has probability $\frac12$. So $$P(X_n\ \text{even}) = P(X_{n-1}\ \text{odd}) P(n\text{th coin head}) + P(X_{n-1}\ \text{even}) P(n\text{th coin tail})$$ hence $$P(X_n\ \text{even}) = P(X_{n-1}\ \text{odd})\tfrac12+ P(X_{n-1}\ \text{even})\tfrac12$$ and $X_{n-1}$ is either odd or even, so $P(X_{n-1}\ \text{odd})+ P(X_{n-1}\ \text{even})=1$ hence $P(X_n\ \text{even}) =\frac12$.

Answer 4

Proof 1. Here's another bijective proof. Call a string odd (resp. even) if it contains an odd (resp. even) number of $1$'s. It suffices to show that the number of odd and even strings are equal.

Fix the string $a = 1 \circ 0^{n-1}$; i.e., $a$ contains a single $1$ concatenated with $n-1$ zeroes. Note that for any $x \in \{0,1\}^n$, the string $x \oplus a$ is odd if and only if $x$ is even. That is, the involution* mapping $x$ to $x \oplus a$ takes odd strings to even strings and vice-versa. Therefore, the desired conclusion follows.

*Verify that this is indeed an involution!

---

More details for proof 1. Here I present the same solution with some more details. Let $E$ and $O$ denote the set of even and odd strings respectively. For any set $A \subseteq \{0,1\}^n$, define $A \oplus a := \{ x \oplus a \mid x \in A \}$. Convince yourself that $A \oplus a$ has the same size as $A$.

Xoring a string by $a$ amounts to flipping the first coordinate; consequently this also flips the parity of the string. Therefore, if $x$ is even, then $x \oplus a$ is odd; similarly if $x$ is odd, then $x \oplus a$ is odd. That is, $E \oplus a \subseteq O$ and $O \oplus a \subseteq E$. So we have $|E| = |E \oplus a | \leqslant |O|$ and $|O| = |O \oplus a| \leqslant |E|$. Combining these two observations, it follows that $|E| = |O|$.

---

EDIT:

Proof 2. Denote by $Y$ the random variable $X_1 \oplus X_2 \oplus \cdots \oplus X_n$. The following facts are standard and often useful:

1. The parity of $X$ is equal to (the parity of) $Y$. That is, $X$ is even if $Y = 0$ and odd otherwise.

2. If $X_1$ and $W$ are independent $0/1$ random variables such that $X_1$ is uniformly distributed over $\{0,1\}$, then $X_1 \oplus W$ is also uniformly distributed over $\{0,1\}$.

It is instructive to prove these claims as an exercise. Taking $W = X_2 \oplus X_3 \oplus \cdots \oplus X_n$ in (2.), we find that $Y = X_1 \oplus X_2 \oplus \cdots \oplus X_n$ is uniformly distributed over $\{0,1\}$. So, by (1.), the parity of $X$ is uniformly distributed in $\{ \text{even}, \text{odd} \}$.