Game Theory (Part 9)

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

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:

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

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?

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

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

\( (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 outcomes. 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 outcomes is equally likely!

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

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

I could have done this a lot faster. I could say "there are 8 outcomes 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.

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

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

\( \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}\)

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

Why? Here's why: there were 3 ways to get two heads when you flipped 3 coins, and each of these outcomes 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 outcomes we're trying to count:

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

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:

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

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

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

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} = \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 outcomes that can happen. Each of these is equally likely if it's a fair coin and the flips are independent. So each has probability

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

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:

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.

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

\( \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{ \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

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

\( \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.

You can also read comments on Azimuth, and make your own comments or ask questions there!