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

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

-
$E[X] = n/2$ is a constant and not necessarily an integer. What do you mean when you ask for the probability that it is even? Is $n$ itself a random variable (e.g. $n$ is a geometric random variable, or a uniformaly distributed on $\{1,2,\ldots. 10\}$ or something? – Dilip Sarwate Nov 16 '11 at 22:12
@DilipSarwate, I made a mistake with the question. I was asking for the probability of X, not E[X]. I have edited the question to fix it. – jamesio Nov 16 '11 at 22:17
Prof. Israel has given you a very elegant and concise answer, so let me just give you a hint for another way of looking at the problem. Apply the binomial theorem to expand $\left(\frac{1}{2}+\frac{1}{2}\right)^n$ and show that the sum is $P\{X~\text{even}\}+P\{X~\text{odd}\}$. Apply the binomial theorem to expand $\left(\frac{1}{2}-\frac{1}{2}\right)^n$ and show that the sum is $P\{X~\text{even}\}-P\{X~\text{odd}\}$. Solve the resulting equations for $P\{X~\text{even}\}$ and $P\{X~\text{odd}\}$. – Dilip Sarwate Nov 16 '11 at 23:09

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

-
This argument shows that the result holds as soon as one of the flips is fair and the flips are independent. In other words: for every independent $\pm1$ random variables $Y$ and $Z$, if $Y$ is uniform then $YZ$ is (and in fact $YZ$ is uniform if and only if $Y$ or $Z$ is). – Did Nov 17 '11 at 6:53

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

-

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

-

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

-