Even vs Odd Heads and Coin Fairness
This is a three-part problem about the parity of heads in coin flips.
Part 1. You flip a fair coin 10 times. What is the probability of getting an even number of heads? What about an odd number of heads?
Part 2. You flip a single coin $n \geq 1$ times (where the coin has some unknown probability $p$ of landing heads). You observe that the probability of getting an even number of heads equals the probability of getting an odd number of heads. Does this imply the coin is fair (i.e., $p = 1/2$)?
Part 3. Now you have 10 different coins with unknown head probabilities $p_1, p_2, \ldots, p_{10}$. You flip each coin once. You observe that the probability of the total number of heads being even equals the probability of it being odd. Does this imply that at least one of the coins is fair?
Hints
- Think about what happens when you evaluate a polynomial at $z = -1$ -- which terms survive and which cancel?
- The probability generating function for the number of heads in $n$ flips of a coin with bias $p$ is $(pz + (1-p))^n$. The difference $P(\text{even}) - P(\text{odd})$ equals $f(-1)$.
- For independent coins, the joint PGF is the product of individual PGFs. So $f(-1) = \prod_i (1 - 2p_i)$, and a product is zero iff at least one factor is zero.
Worked Solution
How to Think About It: The key tool here is a classic trick for separating even and odd terms in a sum: evaluate the generating function at $+1$ and $-1$ and take the difference. For a single coin flip with bias $p$, the probability generating function (PGF) is $p z + (1-p)$. When you plug in $z = -1$ you get $(1 - 2p)$, which measures the "imbalance" between even and odd outcomes. This is the thread that ties all three parts together.
Quick Estimate: For a fair coin, $(1 - 2p) = 0$, so even and odd are always equally likely regardless of the number of flips. That handles Part 1 immediately. For an unfair coin, $(1 - 2p)^n = 0$ only if $p = 1/2$, and for multiple independent coins, $\prod(1 - 2p_i) = 0$ only if at least one factor is zero. So the answer to all three parts should confirm fairness -- let's verify.
Approach: Use the generating function evaluation trick $P(\text{even}) - P(\text{odd}) = f(-1)$ where $f(z)$ is the PGF of the total number of heads.
Formal Solution:
Part 1. Let $X$ be the number of heads in 10 fair coin flips. The PGF is:
$$f(z) = \left(\frac{1 + z}{2}\right)^{10}$$
The difference between even and odd probabilities is:
$$P(\text{even}) - P(\text{odd}) = f(-1) = \left(\frac{1 + (-1)}{2}\right)^{10} = 0$$
Since $P(\text{even}) + P(\text{odd}) = 1$ and $P(\text{even}) - P(\text{odd}) = 0$, we get:
$$P(\text{even}) = P(\text{odd}) = \frac{1}{2}$$
Alternatively, you can see this directly from the binomial theorem: $\sum_{k=0}^{10} (-1)^k \binom{10}{k} (1/2)^{10} = (1 - 1)^{10} / 2^{10} = 0$.
Part 2. Now the coin has bias $p$ and is flipped $n$ times. The PGF is:
$$f(z) = (pz + (1-p))^n$$
The even-odd difference is:
$$P(\text{even}) - P(\text{odd}) = f(-1) = (1 - 2p)^n$$
Setting this to zero: $(1 - 2p)^n = 0$. Since $n \geq 1$, this forces $1 - 2p = 0$, i.e., $p = 1/2$.
Yes, the coin must be fair. There is no unfair coin that produces equal even/odd probabilities over any positive number of flips.
Part 3. Now we have 10 independent coins with biases $p_1, \ldots, p_{10}$, each flipped once. The total number of heads $X = X_1 + \cdots + X_{10}$ where each $X_i \sim \text{Bernoulli}(p_i)$, and by independence the PGF is:
$$f(z) = \prod_{i=1}^{10} (p_i z + (1-p_i))$$
The even-odd difference is:
$$P(\text{even}) - P(\text{odd}) = f(-1) = \prod_{i=1}^{10} (1 - 2p_i)$$
Setting this to zero: $\prod_{i=1}^{10} (1 - 2p_i) = 0$. A product of real numbers is zero if and only if at least one factor is zero, so $1 - 2p_j = 0$ for some $j$, meaning $p_j = 1/2$.
Yes, at least one of the 10 coins must be fair.
Answer:
- Part 1: $P(\text{even}) = P(\text{odd}) = 1/2$ for a fair coin.
- Part 2: Yes, equal even/odd probabilities imply $p = 1/2$. The coin must be fair.
- Part 3: Yes, at least one coin must have $p_i = 1/2$. The generating function factorizes as a product, and the product is zero only when a factor is zero.
Intuition
The generating function trick $P(\text{even}) - P(\text{odd}) = f(-1)$ is one of the most useful identities in discrete probability. It shows up whenever you need to reason about the parity of a count. The deep reason it works is that $(-1)^k$ acts as a "parity filter" -- it adds even terms and subtracts odd terms. Evaluating the PGF at $z = -1$ applies this filter automatically.
The really elegant part is Part 3. Independence means the joint PGF factors into a product, and a product of real numbers is zero only when at least one factor is zero. This is a beautiful connection between algebraic structure (factorization) and probabilistic structure (independence). In practice, this kind of reasoning appears in signal processing (where you test whether a system has a zero at a particular frequency), in characteristic function arguments, and in any setting where you need to infer properties of individual components from an aggregate observation.