Game Theory (Part 9)

Last time we talked about independence of a pair of events, but we can easily go on and talk about independence of a longer sequence of events. For example, suppose we have three coins. Suppose:

• the 1st coin has probability p_H of landing heads up and p_T of landing tails up;
• the 2nd coin has probability q_H of landing heads up and q_T of landing tails up;
• the 3rd coin has probability r_H of landing heads up and r_T of landing tails up.

Suppose we flip all of these coins: the 1st, then the 2nd, then the 3rd. What’s the probability that we get this sequence of results:

(H, T, T)

If the coin flips are independent, the probability is just this product:

p_H \, q_T \, r_T

See the pattern? We just multiply the probabilities. And there’s nothing special about coins here, or the number three. We could flip a coin, roll a die, pick a card, and see if it’s raining outside.

For example, what’s the probability that we get heads with our coin, the number 6 on our die, an ace of spades with our cards, and it’s raining? If these events are independent, we just calculate:

the probability that we get heads, times
the probability that we roll a 6, times
the probability that we get an ace of spades, times
the probability that it’s raining outside.

Let’s solve some puzzles using this idea!

Three flips of a fair coin

Example 1. Suppose you have a fair coin: this means it has a 50% chance of landing heads up and a 50% chance of landing tails up. Suppose you flip it three times and these flips are independent. What is the probability that it lands heads up, then tails up, then heads up?

We’re asking about the probability of this event:

(H, T, H)

Since the flips are independent this is

p_{(H,T,H)} = p_H \, p_T \, p_H

Since the coin is fair we have

\displaystyle{ p_H = p_T = \frac{1}{2} }

so

\displaystyle{ p_H p_T p_H = \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8} }

So the answer is 1/8, or 12.5%.

Example 2. In the same situation, what’s the probability that the coin lands heads up exactly twice?

There are 2 × 2 × 2 = 8 events that can happen:

(H,H,H)
(H,H,T), \; (H,T,H), \; (T,H,H)
(H,T,T), \; (T,H,T), \; (T,T,H)
(T,T,T)

We can work out the probability of each of these events. For example, we’ve already seen that (H,T,H) is

\displaystyle{ p_{(H,T,H)} = p_H p_T p_H = \frac{1}{8} }

since the coin is fair and the flips are independent. In fact, all 8 probabilities work out the same way. We always get 1/8. In other words, each of the 8 events is equally likely!

But we’re interested in the probability that we get exactly two heads. That’s the probability of this subset:

S = \{ (T,H,H), (H,T,H), (H,H,T) \}

Using the rule we saw in Part 7, this probability is

\displaystyle{ p(S) = p_{(T,H,H)} + p_{(H,T,H)} + p_{(H,H,T)} = 3 \times \frac{1}{8} }

So the answer is 3/8, or 37.5%.

I could have done this a lot faster. I could say “there are 8 events that can happen, each equally likely, and three that give us two heads, so the probability is 3/8.” But I wanted to show you how we’re just following rules we’ve already seen!

Three flips of a very unfair coin

Example 3. Now suppose we have an unfair coin with a 90% chance of landing heads up and 10% chance of landing tails up! What’s the probability that if we flip it three times, it lands heads up exactly twice? Again let’s assume the coin flips are independent.

Most of the calculation works exactly the same way, but now our coin has

\displaystyle{ p_H = 0.9, \quad p_T = 0.1 }

We’re interested in the events where the coin comes up heads twice, so we look at this subset:

S = \{ (T,H,H), (H,T,H), (H,H,T) \}

The probability of this subset is

\begin{array}{ccl} p(S) &=& p_{(T,H,H)} + p_{(H,T,H)} + p_{(H,H,T)} \\ &=& p_T \, p_H \, p_H + p_H \, p_T \, p_H + p_H \, p_H \, p_T \\ &=& 3 p_T p_H^2 \\ &=& 3 \times 0.1 \times 0.9^2 \\ &=& 0.3 \times 0.81 \\ &=& 0.243 \end{array}

So now the probability is just 24.3%.

Six flips of a fair coin

Example 4. Suppose you have a fair coin. Suppose you flip it six times and these flips are independent. What is the probability that it lands heads up exactly twice?

We did a similar problem already, where we flipped the coin three times. Go back and look at that if you forget! The answer to that problem was

\displaystyle{ 3 \times \frac{1}{8} }

Why? Here’s why: there were 3 ways to get two heads when you flipped 3 coins, and each of these events had probability

\displaystyle{ \left(\frac{1}{2}\right)^3 = \frac{1}{8} }

We can do our new problem the same way. Count the number of ways to get two heads when we flip six coins. Then multiply this by

\displaystyle{ \left(\frac{1}{2}\right)^6 = \frac{1}{64} }

The hard part is to count how many ways we can get two heads when we flip six coins. To get good at probabilities, we have to get good at counting. It’s boring to list all the events we’re trying to count:

(H,H,T,T,T,T), (H,T,H,T,T,T), (H,T,T,H,T,T), …

So let’s try to come up with a better idea.

We have to pick 2 out of our 6 flips to be H’s. How many ways are there to do this?

There are 6 ways to pick one of the flips and draw a red H on it, and then 5 ways left over to pick another and draw a blue H on it… letting the rest be T’s. For example:

(T, H, T, T, H, T)

So, we’ve got 6 × 5 = 30 choices. But we don’t really care which H is red and which H is blue—that’s just a trick to help us solve the problem. For example, we don’t want to count

(T, H, T, T, H, T)

as different from

(T, H, T, T, H, T)

So, there aren’t really 30 ways to get two heads. There are only half as many! There are 15 ways.

So, the probability of getting two heads when we flip the coin six times is

\displaystyle{ 15 \times \frac{1}{64} = \frac{15}{64} \approx .234 }

where the squiggle means ‘approximately’. So: about 23.4%.

Binomial coefficients

Now for some jargon, which will help when we do harder problems like this. We say there are 6 choose 2 ways to choose 2 out of 6 things, and we write this as

\displaystyle{ \binom{6}{2} }

This sort of number is called a binomial coefficient.

We’ve just shown that

\displaystyle{ \binom{6}{2} = \frac{6 \times 5}{2 \times 1} = 15 }

Why write it like this funky fraction: \frac{6 \times 5}{2 \times 1}? Because it’ll help us see the pattern for doing harder problems like this!

Nine flips of a fair coin

If we flip a fair coin 9 times, and the flips are independent, what’s the probability that we get heads exactly 6 times?

This works just like the last problem, only the numbers are bigger. So, I’ll do it faster!

When we flip the coin 9 times there are 2^9 possible events that can happen. Each of these is equally likely if it’s a fair coin and the flips are independent. So each has probability

\displaystyle{ \frac{1}{2^9} }

To get the answer, we need to multiply this by the number of ways we can get heads exactly 6 times. This number is called ‘9 choose 6’ or

\displaystyle{ \binom{9}{6} }

for short. It’s the number of ways we can choose 6 things out of a collection of 9.

So we just need to know: what’s 9 choose 6? We can work this out as before. There are 9 ways to pick one of the flips and draw a red H on it, then 8 ways left to pick another and draw a blue H on it, and 7 ways left to pick a third and draw a orange H on it. That sounds like 9 × 8 × 7.

But we’ve overcounted! After all, we don’t care about the colors. We don’t care about the difference between this:

(T, H, T, T, H, T, T, H, T)

and this:

(T, H, T, T, H, T, T, H, T)

In fact we’ve counted each possibility 6 times! Why six? The first H could be red, green or blue—that’s 3 choices. But then the second H could be either of the two remaining 2 colors… and for the third, we just have 1 choice. So there are 3 × 2 × 1 = 6 ways to permute the colors.

So, the actual number of ways to get 6 heads out of 9 coin flips is

\displaystyle{ \frac{9 \times 8 \times 7}{3 \times 2 \times 1} }

In other words:

\displaystyle{ \binom{9}{6} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} }

To get the answer to our actual problem, remember we need to multiply 1/2^9 by this. So the answer is

\displaystyle{ \frac{1}{2^9} \times \binom{9}{6} }

If you’re a pure mathematician, you can say you’re done now. But normal people won’t understand this answer, so let’s calculate it out. I hope you know the first ten powers of two: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. So:

\displaystyle{ 2^9 = 512 }

I hope you can also do basic arithmetic like this:

\displaystyle{ \binom{9}{6} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84}

So, the probability of getting 6 heads when you do 9 independent flips of a fair coin is

\displaystyle{ \frac{1}{2^9} \times \binom{9}{6} = \frac{84}{512} = 0.164025 }

or 16.4025%. I broke down and used a calculator at the last step. We’re becoming serious nerds here.

Okay, that’s enough for now. We’ve been counting how many ways we can get a certain number of heads from a certain number of coin flips. What we’re realy doing is taking a set of coin flips, say n of them, and choosing a subset of k of them to be heads. So, we say

Definition. The binomial coefficient

\displaystyle{ \binom{n}{k} }

called n choose k, is the number of ways of choosing a subset of k things from a set of n things.

We have seen in some examples that

\displaystyle{ \binom{n}{k} = \frac{n(n-1)(n-2) \cdots (n-k+1)}{k(k-1)(k-2) \cdots 1} }

Here there’s a product of k consecutive numbers on top, and k on bottom too. We didn’t prove this is true in general, but it’s not hard to see, using the tricks we’ve used already.

This entry was posted on Tuesday, February 5th, 2013 at 12:56 am and is filed under game theory, mathematics, probability. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

9 Responses to Game Theory (Part 9)

  1. romain says:
    5 February, 2013 at 9:27 am

    In the example 2, there’s a missing “heads” in the question.

    Also, in the next sentence, it’s written 2 x 2 x = 8 without the last 2.

    Reply
  2. pohjois says:
    5 February, 2013 at 1:45 pm

    After you introduce binomial coefficient you write 5 choose 2 equals 6×5 / 2×1 which is an obvious typo.

    Reply
    • John Baez says:
      5 February, 2013 at 2:07 pm

      Thanks. I really appreciate it when people catch mistakes in these notes, since someday they may evolve into a book.

      Fixed!

      Reply
      • pohjois says:
        5 February, 2013 at 7:39 pm

        I still see it in the same place. Just after “We’ve just shown that”

        Reply
      • John Baez says:
        5 February, 2013 at 9:08 pm

        Whoops. I’m trying to eliminate all references to ‘5 choose 2’ and replace them with ‘6 choose 2’, since that’s the problem I’m talking about here. I found and fixed a lot of them but not the one you actually mentioned! Now that’s fixed.

        Reply
  3. Blaise Pascal says:
    11 April, 2013 at 10:57 pm

    In your “9 flips, 6 heads” example, you don’t compute {9 \choose 6} , but rather {9 \choose 3} . You pick out a red head, a blue head, and an orange head to get 9*8*7 in the numerator, and then claim you are overcounting by a factor of 3*2*1.

    I know {n \choose k} = {n \choose n-k} , so you get the right answer in either case, but you never mention that fact about binomial coefficients.

    Reply
  4. Lulu says:
    8 May, 2013 at 1:55 am

    Dear John,

    In the last paragraph, there is a major flaw: the number of factors in the numerator should be k, too!

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

This site uses Akismet to reduce spam. Learn how your comment data is processed.