44
$\begingroup$

If nine coins are tossed, what is the probability that the number of heads is even?

So there can either be 0 heads, 2 heads, 4 heads, 6 heads, or 8 heads.

We have $n = 9$ trials, find the probability of each $k$ for $k = 0, 2, 4, 6, 8$

$n = 9, k = 0$

$$\binom{9}{0}\bigg(\frac{1}{2}\bigg)^0\bigg(\frac{1}{2}\bigg)^{9}$$

$n = 9, k = 2$

$$\binom{9}{2}\bigg(\frac{1}{2}\bigg)^2\bigg(\frac{1}{2}\bigg)^{7}$$

$n = 9, k = 4$ $$\binom{9}{4}\bigg(\frac{1}{2}\bigg)^4\bigg(\frac{1}{2}\bigg)^{5}$$

$n = 9, k = 6$

$$\binom{9}{6}\bigg(\frac{1}{2}\bigg)^6\bigg(\frac{1}{2}\bigg)^{3}$$

$n = 9, k = 8$

$$\binom{9}{8}\bigg(\frac{1}{2}\bigg)^8\bigg(\frac{1}{2}\bigg)^{1}$$

Add all of these up:

$$=.64$$ so there's a 64% chance of probability?

$\endgroup$
  • 20
    $\begingroup$ Either Heads or Tails but not both must be even, so $.5$ $\endgroup$ – lulu Mar 4 at 15:44
  • $\begingroup$ I fixed it, for k = 0 that part was equal to $.001$ so it didn't really make a difference in the sum, so it's still 64%? $\endgroup$ – Stuy Mar 4 at 15:45
  • 3
    $\begingroup$ Your arithmetic is wrong somewhere because it should sum to $0.50$. You can match the chance of $k$ heads with the chance of $9-k$. The powers of $\frac 12$ always give $\frac 1{2^9}$, so it is probably in your computation of the combination numbers. Your approach is fine, if much harder than the symmetry arguments. $\endgroup$ – Ross Millikan Mar 4 at 15:46
  • 5
    $\begingroup$ Ross Millikan is correct; you need to double-check your arithmetic. The last two terms of each product multiply to 1/512. The first terms of each product are 1, 36, 126, 84 and 9. Those add to 256. So you should be getting 256/512 which is 1/2. Always check your arithmetic. $\endgroup$ – Eric Lippert Mar 4 at 17:59
  • 1
    $\begingroup$ @Anush: I've added an answer that treats "unfair" coins in terms of a recurrence, and as a side benefit, this yields additional insight into the case of a fair coin as well. $\endgroup$ – Brian Tung Mar 10 at 18:44

13 Answers 13

150
$\begingroup$

The probability is $\frac{1}{2}$ because the last flip determines it.

$\endgroup$
  • 61
    $\begingroup$ Though this answer is correct for this specific question, it is interesting to consider why it works. Consider: an unfair coin comes up heads 75% of the time, tails 25% of the time. We flip it nine times. Again, the last flip determines whether the total is odd or even. In this case, is it even 75% of the time, because the last flip is heads 75% of the time, or is it even 50% of the time, as it was before? Or is it even some other percentage of the time? Before you do the math, what's your gut feeling? And can you explain why your argument is only valid for a fair coin? $\endgroup$ – Eric Lippert Mar 4 at 22:50
  • 38
    $\begingroup$ That's a good analysis. My reason for bringing it up is: plainly the OP is relatively new to probability, so I think it is important to call out the assumptions when giving "shortcut" reasoning like this answer. The underlying assumption is that with eight coins, an even number of heads or tails is also 1/2. I think it is worthwhile calling that out. I wouldn't want the OP to deduce that for more general problems, they only need to consider the probability of the final flip. $\endgroup$ – Eric Lippert Mar 4 at 23:42
  • 23
    $\begingroup$ I disagree that the underlying assumption is "with eight coins, an even number of heads occurs with probability $1/2$" -- that assumption is not necessary for the answer at all. If you flip 8 coins of varying biases, but the 9th and final one is a fair coin, then this answer is still correct. $\endgroup$ – Mees de Vries Mar 5 at 11:50
  • 8
    $\begingroup$ This answer is correct but gets 0 points on an exam as no argument is made as to why the last flip determines it - it's just asserted without proof. $\endgroup$ – orlp Mar 5 at 11:53
  • 5
    $\begingroup$ @orlp: It's a bit abbreviated, but many people recognize the logical consequences of symmetry without particularly thinking about them. If the first 8 flips had an even number of heads, then the odds of the next flip causing the total to be even will be 50-50. If the first 8 flips had an odd number of heads, the odds of the next flip causing the total to be even will be 50-50. So the total is 50-50 regardless. $\endgroup$ – supercat Mar 5 at 15:13
86
$\begingroup$

If there are an even number of heads then there must be an odd number of tails. But heads and tails are symmetrical, so the probability must be $1/2$.

$\endgroup$
  • 3
    $\begingroup$ best argument, relying only on the symmetries of the problem $\endgroup$ – lurscher Mar 8 at 16:17
  • 1
    $\begingroup$ Nice idea, even though it works "only" for odd numbers of coins. $\endgroup$ – Hagen von Eitzen Mar 10 at 9:10
46
$\begingroup$

Your approach is good also, you probably made a mistake in calculations. The number of favorable outcomes is $$\binom{9}{0}+\binom{9}{2}+\binom{9}{4}+\binom{9}{6}+\binom{9}{8}=1+36+126+84+9=256$$ The number of all possible outcomes is $512$ thus the probability to get even number of heads is $0.5$.

$\endgroup$
  • $\begingroup$ Comparing the number of favorable outcomes with all possible outcomes in this way only works for a fair (50% heads/50% tails) coin. $\endgroup$ – Richard Ward Mar 5 at 17:09
  • 21
    $\begingroup$ In probability exercises, coins are assumed to be fair unless otherwise stated. (In real life, one should not make this assumption) $\endgroup$ – Stig Hemmer Mar 6 at 9:35
25
$\begingroup$

The easiest way to see this : Consider the number of heads we have in the first $8$ coins.

  • If this number is even, we need a tail, we have probability $\frac{1}{2}$
  • If this number is odd, we need a head, we have probability $\frac{1}{2}$

Hence no matter what the $8$ coins delivered, we have probability $\frac{1}{2}$ , which is the answer.

$\endgroup$
  • 1
    $\begingroup$ This is , by the way, true for EVERY number of coins (even for one coin). $\endgroup$ – Peter Mar 4 at 15:49
  • 17
    $\begingroup$ Pedantic point: If zero coins are tossed, the probability of an even number of heads is 100%. $\endgroup$ – Brian Mar 4 at 18:24
  • 4
    $\begingroup$ This answer presupposes that having an even number of heads and an odd number of heads in eight flips is equally likely, but we haven't proved that lemma. $\endgroup$ – Eric Lippert Mar 4 at 22:52
  • 9
    $\begingroup$ @EricLippert: No it doesn't. If the probability in both cases is the same, then the probability overall is the same... $\endgroup$ – user21820 Mar 5 at 7:18
  • 7
    $\begingroup$ @EricLippert No. If the probability of an even number of heads in 8 tosses is p (and the probability of an odd number of heads is 1-p), without assuming the value of p, the probability of an even number in all 9 tosses is p·(1/2) + (1-p)(1/2), which turns out to be exactly 1/2. $\endgroup$ – dgstranz Mar 5 at 9:17
20
$\begingroup$

There are two cases here:

  • There's an even number of heads: 0, 2, 4, 6 or 8 heads
  • There's an odd number of heads: 1, 3, 5, 7 or 9 heads

But notice that having an odd number of heads means having an even number of tails (e.g. 5 heads means 4 tails), so the second case is the same as:

  • There's an even number of tails: 0, 2, 4, 6 or 8 tails

Since heads and tails are equally probable, we can, by symmetry, see that these two cases have the same probability. Therefore each must have probability $1/2$.

$\endgroup$
  • 2
    $\begingroup$ Ethan Bolker already gave this explanation 2 hours ago. $\endgroup$ – Paul Sinclair Mar 4 at 17:54
  • 5
    $\begingroup$ @PaulSinclair Yes, he did. But I found this explanation clearer than Ethan's, which skips a number of steps. $\endgroup$ – CJ Dennis Mar 5 at 1:27
  • 2
    $\begingroup$ I didn't understand Ethan's answer and I understood this one perfectly. $\endgroup$ – Todd Wilcox Mar 5 at 14:58
  • 1
    $\begingroup$ @TheGreatDuck - To repeat an answer that already existed before you even started answering is poor behavior if you don't add anything to it. And if you are adding something to it (which admittedly was done here), you should still acknowledge what someone else has already provided. I didn't downvote this post, but I thought it best to point out the repetition, because continuing the practice will eventually cause trouble. $\endgroup$ – Paul Sinclair Mar 6 at 0:05
  • 3
    $\begingroup$ @PaulSinclair An answer should stand on its own and not refer to other answers. It definitely shouldn't be an exact duplicate of any previous answer, although a partial duplicate can be justified on a case-by-case basis if it adds extra information, or explains concepts in a clearer way. There should be a good reason for thinking that it's better than, or at least adds significantly to any previous answer, without forcing the reader to read a different answer for context or missing information. $\endgroup$ – CJ Dennis Mar 8 at 2:22
18
$\begingroup$

All the possible sequences of tosses (which are all equally likely) may be divided into the two categories "even number of heads" and "odd number of heads". You can then pair up each sequence in one category with the "flipped" version (flip every coin in the sequence around) in the other category. This shows that there are equally many sequences in each of the two categories. So the probability of landing in a specific one of them must be $\frac12$.

$\endgroup$
10
$\begingroup$

There's a way to do it with barely any maths:

It's clear that if there's an odd number of heads, there's an even number of tails and vice versa, so P(even number of heads) + P(even number of tails) = 1.

Formally rename "heads" to "tails". The problem remains unchanged.

So P(even number of heads) = P(even number of tails) = 1/2.

$\endgroup$
  • $\begingroup$ Unless (channeling Twilight Zone), one of the flips lands on edge. $\endgroup$ – Carl Witthoft Mar 8 at 19:40
9
$\begingroup$

$$=\frac{\color{red}{\binom{9}{0}}+\color{blue}{\binom{9}{2}}+\color{orange}{\binom{9}{4}}+\color{green}{\binom{9}{6}}+\color{purple}{\binom{9}{8}}}{\color{red}{\binom{9}{0}}+\color{purple}{\binom{9}{1}}+\color{blue}{\binom{9}{2}}+\color{green}{\binom{9}{3}}+\color{orange}{\binom{9}{4}}+\color{orange}{\binom{9}{5}}+\color{green}{\binom{9}{6}}+\color{blue}{\binom{9}{7}}+\color{purple}{\binom{9}{8}}+\color{red}{\binom{9}{9}}}$$

$$=\frac{\color{red}{\binom{9}{0}}+\color{blue}{\binom{9}{2}}+\color{orange}{\binom{9}{4}}+\color{green}{\binom{9}{3}}+\color{purple}{\binom{9}{1}}}{\color{red}{\binom{9}{0}}+\color{purple}{\binom{9}{1}}+\color{blue}{\binom{9}{2}}+\color{green}{\binom{9}{3}}+\color{orange}{\binom{9}{4}}+\color{orange}{\binom{9}{5}}+\color{green}{\binom{9}{6}}+\color{blue}{\binom{9}{7}}+\color{purple}{\binom{9}{8}}+\color{red}{\binom{9}{9}}}$$

$$=\frac{\color{red}{\binom{9}{0}}+\color{purple}{\binom{9}{1}}+\color{blue}{\binom{9}{2}}+\color{green}{\binom{9}{3}}+\color{orange}{\binom{9}{4}}}{\color{red}{\binom{9}{0}}+\color{purple}{\binom{9}{1}}+\color{blue}{\binom{9}{2}}+\color{green}{\binom{9}{3}}+\color{orange}{\binom{9}{4}}+\color{orange}{\binom{9}{5}}+\color{green}{\binom{9}{6}}+\color{blue}{\binom{9}{7}}+\color{purple}{\binom{9}{8}}+\color{red}{\binom{9}{9}}}$$

$$=\frac{\color{red}{\binom{9}{0}}+\color{purple}{\binom{9}{1}}+\color{blue}{\binom{9}{2}}+\color{green}{\binom{9}{3}}+\color{orange}{\binom{9}{4}}}{\color{red}{\binom{9}{0}}+\color{purple}{\binom{9}{1}}+\color{blue}{\binom{9}{2}}+\color{green}{\binom{9}{3}}+\color{orange}{\binom{9}{4}}+\color{orange}{\binom{9}{4}}+\color{green}{\binom{9}{3}}+\color{blue}{\binom{9}{2}}+\color{purple}{\binom{9}{1}}+\color{red}{\binom{9}{0}}}$$

$$=\frac{a}{a+a}$$

$$=\frac{1}{2}$$

$\endgroup$
  • 1
    $\begingroup$ I see what you're saying, but $1 / ( 1+1)$ is outright wrong. $n / ( n+n )$ works. $\endgroup$ – AakashM Mar 6 at 11:50
  • $\begingroup$ @AakashM Thanks for pointing that out! $\endgroup$ – MCCCS Mar 6 at 11:53
  • 2
    $\begingroup$ You can also highlight with different colors on what changes between lines. It's hard to see currently. $\endgroup$ – justhalf Mar 6 at 20:31
  • 2
    $\begingroup$ It's worth mentioning that about 10% of the male population has some form of colorblindness, which would limit the effectiveness of a presentation like this. $\endgroup$ – Rick Decker Mar 7 at 16:42
7
$\begingroup$

The probability generating function of a Binomiall random variable $X\sim \text{Bin}(n, 1/2)$ with probability of success $1/2$ is given by $$ g_{X}(t)=Et^X=\sum_{k=0}^nP(X=k)t^k=\sum_{k=0}^n\binom{n}{k}\frac{t^k}{2^n}=\frac{1}{2^n}(1+t)^n $$ In particular the probability that $X$ is even is given by $$ \sum_{0\leq k\leq n\, k\,{\text{even}}}P(X=k)=\frac{g(1)+g(-1)}{2}=\frac{1+0}{2}=\frac{1}{2}. $$

$\endgroup$
4
$\begingroup$

If $h$ denotes getting a heads and $p$ denotes getting tails, let's write $\frac{1}{2}h+\frac{1}{2}p$ for the notion of a fair coin: half the time it turns up heads, and half the time tails.

If we expand out the following product while keeping track of multiplication order, $$\left(\frac{1}{2}h+\frac{1}{2}p\right)\left(\frac{1}{2}h+\frac{1}{2}p\right)=\frac{1}{4}hh+\frac{1}{4}hp+\frac{1}{4}ph+\frac{1}{4}pp,$$ we see that the sequences $hh$, $hp$, $ph$, and $pp$ are equally likely. Forgetting about multiplication order, which we want to do because we only care about how many times heads or tails showed up, corresponds to just treating this like a polynomial: $$=\frac{1}{4}h^2+\frac{1}{2}hp+\frac{1}{4}p^2.$$ We can keep multiplying copies of a fair coin together to find the probability that a certain number of heads or tails happened, where the coefficient in front of $h^kp^\ell$ is the probability of $k$ heads and $\ell$ tails.

Nine coins is the expansion $$\left(\frac{1}{2}h+\frac{1}{2}p\right)^9=\sum_{k=0}^9\binom{9}{k}\left(\frac{1}{2}h\right)^k\left(\frac{1}{2}p\right)^{9-k}=\sum_{k=0}^9\frac{1}{2^9}\binom{9}{k}h^kp^{9-k}.$$ So far, all this has done is explain why you were adding up $2^{-9}\binom{9}{k}$ for $k=0,2,4,\dots,8$. Here, now, is a nice trick. If we formally set $h=1$ and $p=1$, then we get $$1=\sum_{k=0}^9\frac{1}{2^9}\binom{9}{k},$$ and if we formally set $h=-1$ and $p=1$, then we get $$0=\sum_{k=0}^9\frac{1}{2^9}\binom{9}{k}(-1)^k.$$ The average of these two equations is $$\frac{1}{2}=\sum_{k=0,k\text{ even}}^9\frac{1}{2^9}\binom{9}{k},$$ since $\frac{1}{2}(1+(-1)^k)$ is $1$ or $0$ depending on whether $k$ is even or odd. Thus the probability of an even number of heads is $\frac{1}{2}$.

Notice that this did not use the fact nine coins were tossed at any point! (Other than the fact that at least one coin was tossed. In the case of tossing no coins, an even number of heads happens with probability $1$. What part of my argument goes wrong for the case of zero coins?)

$\endgroup$
1
$\begingroup$

Nine coins, so that two events

$\mathscr{E}_1$ = #heads is even and

$\mathscr{E}_2$ = #tails is even

are mutually exclusive (the number of tails is 9 - number of heads, so former is even iff latter odd) and comprise all possibilities, thus $P(\mathscr{E}_1) + P(\mathscr{E}_2) =1$. But if the coins are fair, then the probabilities must be unchanged if we swap the roles of heads and tails. Hence $P(\mathscr{E}_1)= P(\mathscr{E}_2)$ and we immediately see both probabilities must be $\frac{1}{2}$.


Now you are wondering why your approach doesn't work, because it is basically sound. You've simply made a slip.

You're approach is: sum every second term in the 10 member (i.e. an even number of terms) sequence whose $n^{th}$ term is the probability of $n$ heads. So the sum is:

$$S_1=\sum_{k=0}^{N/2} \binom{N}{2\,k}\left(\frac{1}{2}\right)^N$$

with $N$ odd (here equal to 9).

But, by dint of $\binom{N}{2\,k} = \binom{N}{N-2\,k}$, this sum is equal to the sum of all the other terms

$$S_2 =\sum_{k=0}^{N/2} \binom{N}{N-2\,k}\left(\frac{1}{2}\right)^N$$

in the sequence that don't belong to the first sum. So $S_1=S_2$ and clearly $S_1+S_2=1$, because this sum is the sum of probabilities of all possible mutually exclusive outcomes, therefore 1, or, alternatively, call up the binomial theorem and see that $S_1+S_2=\left(\frac{1}{2} + \frac{1}{2}\right)^9=1$

$\endgroup$
1
$\begingroup$

Here's an analytical answer with greater emphasis on reasoning than anything specific to probability which might lend greater insight into the problem.

Consider if there was only one coin. The probability to have an even number of heads is $1\over2$, since there are two possible outcomes and we are only interested in one of them.

Now, let there be $N \gt 1$ coin tosses. The $N^{\text{th}}$ coin toss will either give a heads or tails. If the $N-1$ tosses resulted in an even number of heads the probability of the $N$ coin tosses resulting in an even number of heads is $1\over2$ since the $N^{\text{th}}$ coin toss will add either $0$ or $1$ to the number of heads from the $N-1$ tosses, and we are only concerned with the parity of the count.

The conclusion is the same for the $N-1$ coin tosses resulting in an odd number of heads.

This approach is valid as this reasoning applies to all possible values of $N$ in our given domain.

$\therefore$ The probability of $N$ coin tosses resulting in an even number of heads is $1\over2$, with $N \in \mathbb{N}$.

$\endgroup$
1
$\begingroup$

A useful way to think about this problem, especially for the case of generally unfair coins, is in terms of a recurrence. Let $p$ be the probability that the coin flips heads, and let $q_n$ be the probability, after $n$ flips, that the number of flips is even. So, in particular, $q_0 = 1$: Before the coin has been flipped at all (after $0$ flips, in other words), the probability that the number of heads is even equals $1$.

We can write a recurrence for $q_{n+1}$ in terms of $q_n$ as follows:

  • If the parity (the even-or-oddness of the heads) was even after $n$ flips, which happens with probability $q_n$, then it stays even with probability $1-p$.

  • If the parity was odd after $n$ flips, which happens with probability $1-q_n$, then it turns even with probability $p$.

(We assume, as is typical in these problems, i.i.d. flips.) With these two observations in mind, we get

$$ q_{n+1} = q_n(1-p) + (1-q_n)p $$

which we can rewrite as

$$ q_{n+1} = p + (1-2p)q_n $$

If this recurrence has a limit $q_n \to q$, then we can put

$$ q = p+(1-2p)q $$ $$ 2pq = p $$

from which we get that either $p = 0$ (in which case, clearly, $q_n = 1$ for all $q$—if you only flip tails, then the parity of heads will always be even), or $q = 1/2$; that is, the limiting probability of even parity is $1/2$ (and the same for odd parity, too, obviously). If there is no limit, it will be because $p = 1$, and we continually alternate between even and odd parity. I do not show this, but it is not difficult.

It is also not difficult to show that the recurrence has the solution

$$ q_n = \frac12 + \frac12(1-2p)^n $$

and this lays out why the symmetry arguments work out well for fair coins: $(1-2p)^n = 0$ for all $n > 0$, leaving us with just $q_n = 1/2$.


It may help to see this recurrence in the form of a Markov chain with two states:

enter image description here

Since the transition probabilities from one state to the other are equal ($p = p$), the state probabilities at equilibrium (if such exists) must also be equal, and therefore both equal to $1/2$.

$\endgroup$
  • $\begingroup$ This is very nice. Thank you. $\endgroup$ – Anush Mar 11 at 5:04
  • 1
    $\begingroup$ @Anush: You're welcome, and thanks for the kind words! $\endgroup$ – Brian Tung Mar 11 at 16:25

protected by Aloizio Macedo Mar 8 at 23:13

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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