Numeracy #5: Combinatorics

In The Most Important Thing, Howard Marks makes the point that:

Only investors with unusual insight can regularly divine the probability distribution that governs future events and sense when the potential returns compensate for the risks that lurk in the distribution’s negative left-hand tail.

For investors to achieve success, they need to be able to find situations where the upside potential far exceeds the downside risk. Since the future is uncertain, we rely on probabilities.

This post is a continuation of my post on permutations. It hopes to explain the concept of combinations. After learning about permutations and combinations, we will be able to work through some interesting problems in probability theory.

Understanding combinations

Before we dive into combinations, let’s review what the big idea behind permutations was. We use permutations when we are given a counting problem where order matters. For example, how many ways can we award 1st, 2nd, and 3rd place prize among the 9 poker players at the final table of the WPT? For 1st, there are 9 possibilities. For 2nd, since we already awarded 1st, there 8 possibilities.  For 3rd, there are 7 possibilities.

1st: 9 possibilities
2nd: 8 possibilities
3rd: 7 possibilities

Total Permutations: 9P3 = 9*8*7 = 504

There are 504 ways of ordering the top 3 out of 9 players. But what if order doesn’t matter? What if we just want to know how many different groups of the top 3 players there could be? In this situation, it wouldn’t matter if you were 1st or 2nd or 3rd. It would only matter that you in the top 3.

This is where combinations come in. Permutations would say [1st:p1, 2nd:p2, 3rd:p3] is different from [1st:p2, 2nd:p3, 3rd:p1] because the orders are different, therefore, we should count them both in our result. For the sake of our questions, it would be redundant to count both, since we don’t care about order.

The key idea behind combinations is that we need to take the permutations and divide them by the redundancies. How do we find the redundancies? It’s pretty simple. We just look at all the possible ways of ordering the first 3 players. This is just a permutation.

Position 1: 3 possibilities
Position 2: 2 possibilities
Position 3: 1 possibility

Total ways to arrange the top 3 players: 3P3 = 3*2*1 = 6

We know the total number of ways we can order 3 out of 9 players is 504, and we know the total way number of ways we can order 3 players is 6. Now, all we need to do is divide the former by the latter.

Total number of ways to choose a group of 3 from 9 players when order doesn’t matter:

9C3 = 504 / 6 = 84

There are 84 different groups of players that could end up in the top 3. 9C3 is just a way of saying 9 choose 3. It is the short hand for combination questions. nPk is the short hand for permutation questions. It is time for some more mathematical speak. The formula for combinations is:

nCk = nPk / k!

nPk = n! / (n-k)!

Mathematical speak isn’t very intuitive, but the reasoning behind it is. We simply figure out how many possibilities can fit each position, multiply those together, and then divide by the number of ways of arranging those spots. This clears out redundancies and leaves us with the combinations.

Combinatorics

Combinatorics refers to both permutations and combinations. It is the branch of mathematics where countable structures are studied. Its applications include: algebra, probability theory, topology, geometry, optimization, computer science, statistical physics, and economics.

We are going to focus on probability theory. The best way to learn is by doing, so let’s solve some problems using what we have learned so far.

Coin flipping problem

What is the probability of getting exactly 2 heads when flipping a coin 5 times?

P(exactly 2 heads) = ?

Well, any probability is simply the number of occurrences we want divided by the total number of occurrences possible. So let’s start by finding the total number of occurrences or possibilities. We can flip HHHHH, TTTTT, HTHTH, and so on. These are just permutations.

Flip 1: 2 possibilities
Flip 2: 2 possibilities
Flip 3: 2 possibilities
Flip 4: 2 possibilities
Flip 5: 2 possibilities

Total possibilities: 2*2*2*2*2 = 2^5 = 32

A good rule of thumb is that total possibilities usually refers to permutations. Now that we know the denominator for our probability, we need to figure out the numerator. How many ways can we get exactly two heads? We could write them all out but this would take a while. Instead, how many ways can we choose 2 heads to fit in 5 positions? The first head has 5 positions it could fit in, and the second head has 4 positions it could fit in.

Heads #1(H1): 5 possibilities
Heads #2(H2): 4 possibilities

Total possibilities: 5*4 = 20

But wait a minute, this is a permutation so it’s counting situations where H1 and H2 simply change places. For example [H1,H2,T,T,T] and [H2,H1,T,T,T] would be counted twice. This doesn’t make any sense. We need to divide our answer by the number of ways we can arrange two things. We need to use combinations.

5C2 = 20 / 2! = 10

So our final probability is:

P(exactly 2 heads) = number of ways to get 2 heads / total possibilities

P(exactly 2 heads) = 10 / 32 = 31%

This could also be done by taking those 10 ways of choosing 2 heads and multiplying them by the probability of getting those arrangements. Since each flip has a 50% chance of heads, the probability of any arrangement would be .5*.5*.5*.5*.5= .031. That answer multiplied by the 10 combinations will also give us 31%. Conceptually, imagine if we figured out every combination by hand. We would have a list of 10 combinations. Now we could figure out the probability for each combination, which is 3.1%. If we add each probability up we will get our answer. This will be useful in the next question.

Free throw problem

What is the probability of a person making at least 8 out of 10 free throws(FT) given that they have a 90% chance of making any single FT.

P(at least 8/10 FT) = ?

The “at least” part is going to be tricky, but lets start the same way as the last question. What is the probability of getting exactly 8 heads? First, how many ways can we choose 8 out of 10 possibilities?

10C8 = 10*9*8*7*6*5*4*3 / 8*4*3*2*1 = 45 choices

Next we need the probability for any of these choices.

P(8 makes 2 misses) = .90^8*.10^2 = 0.0043

This will be true no matter the order:
.90*.90*.90*.90*.90*.90*.90*.90*.10*.10
.10*.90*.10*.90*.90*.90*.90*.90*.90*.90
etc

Next we add up the probabilities for all those individual combinations. Since the probabilities are all the same, we can simply multiply them.

P(exactly 8/10 FT) = 45*.0043 = 0.1935

There is a 19.35% chance of making exactly 8 out of 10 FTs. But we want to know the chance of at least 8/10, not exactly. Well, what other combinations would satisfy this specification? 9/10 and 10/10 should both be included. All we need to do is solve for the cases of 9/10 and 10/10 FTs. If we add the 3 probabilities together we will have our total probability.

P(exactly 8/10 FT) = 0.1935
P(exactly 9/10 FT) = 10C9*.90^9*.10 = 0.3874
P(exactly 10/10 FT) = 10C10*.90^10 = 0.3486

P(at least 8/10 FT) = 0.1935 + 0.3874 + 0.3486 = 0.9295

So given that a person’s FT% is 90%, they have a 93% chance of making at least 8 out of 10 FTs.

Rooks on a chessboard problem

Imagine that 8 rooks are randomly placed on a chessboard. What is the probability that all the rooks will be safe from one another, i.e. that there is no row or column with more than one rook. (a chess board has 8×8 dimensions and 64 spaces)

P(safe arrangement) = ?

This problem is interesting, because we have to use counting in the context of different spacial arrangement. It might seem complicated at first, but we will solve it the same way as that first coin flipping question. First, let’s figure out the total possible arrangements of rooks on the board. This will serve as the denominator of our probability, and we know that this is just a permutation problem.

1st rook placed: 64 possibilities
2nd rook placed: 63 possibilities

8th rook placed: 57 possibilities

Total possibilities:
64P8 = 64! / 56! = 1.78*10^14 (a number in the trillions)

Next we need to count the possible arrangements of rooks that are safe. This is a little trickier. Lets work through this logically. How many locations can we safely place the first rook? There are no other rooks on the board, so we can place it anywhere.

1st rook placed: 64 possibilities

1.png

We can see that parts of the board are now unsafe. When we place our second rook, it will reflect this through a limited number of possibilities.

2nd rook placed: 49 possibilities

1.png

The third rook placed will only have 36 safe spots. If we continue this process, we will quickly realize the amount of possibilities for each subsequent rook is decreasing by perfect squares.

1st rook: 64
2nd rook: 49
3rd rook: 36
4th rook: 25
5th rook: 16
6th rook: 9
7th rook: 4
8th rook: 1

Total safe arrangements:
64*49*36*25*16*9*4*1 = 1.62*10^9

We are ready to answer the question.

P(safe arrangement) = 1.62*10^9 / 1.78*10^14
P(safe arrangement) = 0.0009%

The birthday problem

Consider a birthday party where 30 people are in attendance. For the sake of this question, assume everyone has an equal likelihood of being born on any day of the year and that leap years are ignored. What is the probability that at least two people share a birthday?

P(at least 2 share birthday) = ?

We might be tempted to solve this question the same way we solved the free throw question above. Find the probability of exactly two, then of exactly 3, and so on up until 30. This would take forever. Is there a simpler way to solve this problem? If at least 2 people share a birthday that means everyone doesn’t have a unique birthday. What is the probability that everyone has a unique birthday? If we solve for that, we can take 1 minus the answer and get the answer to our original question.

P(at least 2 share birthday) = 100% – P(no one shares a birthday)

Lets start the same way we usually start and find all the possible birthday permutations.

Person 1: 365 possibilities
Person 2: 365 possibilities

Person 30: 365 possibilities

Total possibilities:
365^30 = 7.39*10^76

Next, let’s find the permutations where no one shares a birthday. Person one will still have 365 possible birthdays, but person two will now only have 364.

Person 1: 365 possibilities
Person 2: 364 possibilities…
Person 30: 336 possibilities

No shared birthday possibilities:
365P30 = 2.17*10^76

Next, let’s solve the probability of no one sharing a birthday.

P(no one shares a birthday) = 2.17*10^76 / 7.39*10^76
P(no one shares a birthday) = 29%

Finally, let’s solve the original question.

P(at least 2 share birthday) = 100% – 29%
P(at least 2 share birthday) = 71%

In a group of 30 people, there is a 71% chance that at least 2 of them share a birthday.

Unfair coin problem

Consider a bag that has 20 coins inside of it. 10 of the coins are fair coins and 10 of the coins are unfair, they have 90% chance of landing on heads. We pick a coin from the bag at random and flip it 5 times. We get 4 out of 5 heads. What is the probability that we picked a fair coin given that we got 4/5 heads?

P(fair | 4/5 heads) = ?

It would be a good time to refresh our knowledge of Bayes Theorem. Bayes Theorem states:

P(event | newinfo) = P(newinfo | event) * P(event) / P(newinfo)
P(fair | 4/5 heads) = P(4/5 heads | fair) * P(fair) / P(4/5 heads)

Let’s dissect this a bit. It helps to think in decision trees. The first decision is whether we picked a fair or unfair coin. Given that we picked a fair coin, what is the probability of getting 4/5 heads?

P(fair) = 10/20 = .50
P(4/5 heads | fair) = 5C4*.50^5 = .15

P(4/5 heads and fair) = .15*.50 = 0.075

We just worked out the numerator of Bayes Theorem. We figured out what the probability of picking a fair coin and flipping 4/5 heads is. Now we need to divide this by the total possibility of flipping 4/5 heads. To do this we just need to find out the probability of flipping 4/5 heads given that we picked an unfair coin. We can then add both probabilities together to get the total probability.

P(unfair) = 10/20 = .50
P(4/5 heads | unfair) = 5C4*.90^4*.10 = .32

P(4/5 heads and unfair) = .32*.50 = 0.16
P(4/5 heads and fair) = .15*.50 = 0.075

Total P(4/5 heads) = 0.075 + 0.32 = 0.23

Finally, we can solve the original question.

P(fair | 4/5 heads) = 0.075 / 0.23 = 32%

There is a 32% chance that we picked a fair coin given that we flipped 4/5 heads.

Conclusion

We opened with a Howard Mark’s quote. Let’s close with another:

Knowing the probabilities doesn’t mean you know what’s going to happen. Unlikely things happen – and likely things fail to happen – all the time.

We need to always remember that more things can happen than will. There was a 92% chance of our basketball player making at least 8 FTs. We might see this as a sure thing, bet our life savings on it, and then go bust when our player only makes 1 FT.

Understanding the likely outcomes is not enough. We need to understand what we can lose if we are wrong. Planning for these tail events is what keeps us in the game.

References:
https://en.wikipedia.org/wiki/Combinatorics
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-041sc-probabilistic-systems-analysis-and-applied-probability-fall-2013/index.htm
https://www.khanacademy.org/math/probability/probability-and-combinatorics-topic

Advertisements

Author: David Shahrestani

"I have the strength of a bear, that has the strength of TWO bears."

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s