Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
$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
3  
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

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
2  
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)$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.