PDA

View Full Version : Can anyone recommend a good...

tpir90036
11-23-2003, 05:56 AM
book on probability/combanitorics? i have a com. sci. degree and minored in math so it doesn't have to be a "for dummies" book or anything /images/graemlins/wink.gif something undergrad level on inclusion-exclusion, etc. would be cool though. thanks in advance...

-tpir

BruceZ
11-23-2003, 09:56 AM
As far as texts, I just answered a similar question in this post (http://forumserver.twoplustwo.com/showthreaded.php?Cat=&amp;Number=416704&amp;page=0&amp;view=ex panded&amp;sb=5&amp;o=14&amp;fpart=). Additionally, a classic book just on probability theory (no statistics) is the text by William Feller, Introduction to Probability Theory and its Applications. Despite its title, it presents many advanced topics, and the explanations are somewhat terse, so it is best for math majors.

Neither text discusses inclusion-exclusion, nor do I know of one that does. A multi-part series by Brian Alspach in Poker Digest called I'm In...No I'm Out (http://www.math.sfu.ca/~alspach/pokerdigest.html) dealt with this topic. I haven't read this one, but it is probably good. I have written many posts on this forum with explanations and examples of this principle. If you search for these posts, they will tell you everything you need to know about this principle to solve practical problems. I have repeated a few of the simplest examples below.

Explanation of the Inclusion-Exclusion Principle

Inclusion-exclusion is based on a very simple idea. Suppose a poker room has 3 waiting lists for 3 different games, and players are allowed to be on more than one list at a time, but of course on each list only once. We want to know how many total players are waiting to play. We could simply add the number of players on each list, but this has the obvious problem that it would count the players that are on 2 lists twice, and it would count the players on all 3 lists 3 times, so this number would be too high if any players are on more than one list. That is, we would have a number equal to:

(single listed) + 2*(double listed) + 3*(triple listed)

If we knew how many were on two or three lists, we could subtract that off to get the answer we want. So suppose we next count all the players that are waiting on two lists by counting the number that are on both list 1 and 2, both lists 2 and 3, and both lists 1 and 3. This would count all the players on exactly 2 of these lists once, which is good, but it would count the players on all 3 lists 3 times. Now if we subtract this number from our previous count, we would get:

<font class="small">Code:</font><hr /><pre>
(single listed) + 2*(double listed) + 3*(triple listed)
-(double listed) - 3*(triple listed)
------------------------------------------------------------------
single listed + double listed
</pre><hr />

Now if we count the players that are on all 3 lists, we could add this on to get the total number of players waiting.

Why bother with this method of counting? Because in many probability problems, this is the only practical way to count the number of things we need to count, and it actually makes our lives much easier. That is, it is often very difficult to count the members of a union of sets without over counting the members that lie in the intersection of sets. The inclusion-exclusion principle allows us to replace something that is hard to compute with something that is easy to compute, by over counting on purpose, and then it fixes the over counting for us, almost like magic.

This method works for counting the members of any number of sets, not just 3. Note that to obtain an exact answer, we need to compute as many terms as there are different sets of members we are counting, in this case 3. The odd numbered terms (starting from 1,3,5..) are always added, and the even numbered terms are always subtracted (reverse that for comp-sci. people who start counting with 0, myself included /images/graemlins/laugh.gif). The idea is that when we add a term, we include some members too many times, so then we subtract a term, but then we exclude some members too many times, etc. That is why it is called "inclusion-exclusion". Successive terms always get smaller, so in most practical problems, we can stop computing terms when we see that the terms have become smaller than our desired degree of approximation, instead of computing all of the terms which is often difficult.

Mathematically, this is what we are doing:

P(A u B u C u ...) = P(A) + P(B) + P(C) + ... - P(AB) - P(AC ) - P(BC) - ... + P(ABC) + ...

where A,B,C... are sets, and (A u B) means the union of A and B, so P(A u B) is the probability of A OR B. (AB) is the intersection of A and B, so P(AB) is the probability of the intersection of A AND B. So first we add the probabilities of each set, and this is the first term. Then we subtract the probabilities of each pair-wise intersection of sets, and this is the second term. Then we add the probabilities of each 3-way intersection, and this is the third term, etc.

This is all some textbooks may mention (or less) about the probability of a union, usually without even referring to inclusion-exclusion by name. To fully appreciate its usefulness and power requires some examples.

Example 1

This is the simplest non-trivial poker example. If you hold KK before the flop, what is the probability that at least one of your 9 opponents holds AA?

Note that at most 2 opponents can have AA. The probability that any particular player holds AA is 6/C(50,2). So the first term in inclusion-exclusion is simply 9*6/C(50,2). This is the sum of the 9 probabilities of each player having AA. This alone is very close to the exact answer, but it double counts the times that 2 players hold AA. The number of ways that 2 players can hold AA is C(9,2)*1/C(50,4). So the final answer is:

P(KK vs. AA) = 9*6/C(50,2) - C(9,2)/C(50,4)
or about 4.39%

Example 2

Heres a neat "trick". If you hold AA, what is the probability that one of your 9 opponents holds AA?

The probability that a particular opponent holds AA with you is 1/C(50,2). The first term in inclusion-exclusion is 9/C(50,2). Were done, that's the final answer. There are no more terms to compute because it is not possible for more than 1 opponent to have AA with you. That is, the events of different players having AA are mutually exclusive, and youll recall that the probability of mutually exclusive events can always be summed to get the probability of one of the events occurring. Mutually exclusive events are a trivial special case of the inclusion-exclusion principle where there are no intersections, so all terms except the first are zero.

Example 3

Let's do one more example. This one is a little more substantial. If the flop has exactly 2 diamonds, and you don't have a diamond, what is the probability that at least one of your 4 remaining opponents has a 4-flush assuming they hold random cards? Note: It is equally easy to do this problem assuming a realistic distribution of starting hands.

In this case it is possible for up to 4 players to have 4-flushes, so we will have 4 terms in the exact answer. The probability that a particular player has 2 diamonds is C(11,2)/C(47,2). The first term in inclusion-exclusion is thus 4*C(11,2)/C(47,2). For the second term, we want all the ways that 2 players can have diamonds, without regard to over counting. That is, we want to add all the ways that 2 particular players can have diamonds for every pair of players. This is C(4,2)*C(11,4). Note that this counts the times that more than 2 players have diamonds more than once, but this is exactly what we want for the inclusion-exclusion principle. The second term is thus C(4,2)*C(11,4)/C(47,4). Proceeding the same way for the remaining terms give this exact solution:

C(4,1)*C(11,2) / C(47,2) -
C(4,2)*C(11,4) / C(47,4) +
C(4,3)*C(11,6) / C(47,6) -
C(4,4)*C(11,8) / C(47,8)
or about 19.3%

BruceZ
11-23-2003, 06:19 PM
The number of ways that 2 players can hold AA is C(9,2)*1/C(50,4).

Actually, this is the probability of 2 particular players having the 4 aces, which is the 1/C(50,4) part, multiplied by the number of ways to choose the 2 players.

This the key to understanding inclusion-exclusion. Each term is a probability of N particular players having something, multiplied by the number of ways to choose the N players. For the first term, N is 1, so we just multiply the probability of 1 player having it, which is 6/C(50,2), by the number of ways to pick the 1 player, which 9. This is the P(A) + P(B) + P(C)... adding nine of them in this case. For the second term, we take the probability of 2 particular players having aces, 1/C(50,4), and multiply by the number of ways to pick the two players, which is C(9,2).

tpir90036
11-23-2003, 07:11 PM
wow! thanks for the awesome response! i amazoned around last night but all of the combanitorics boks i found were 900 page graduate level tomes that would probably be over my head. i am generally interested in this branch of math outside of the poker realm but it has been a while since i had to do a proof of anything and i am very, very rusty.

i will definitely check out the books you listed.

thanks again,
-tpir

DPCondit
11-23-2003, 07:29 PM
I know you said it didn't have to be a "Dummies" book, but in case you are interested, Statistics for Dummies was just recently released, and all that is recommended before using it is knowledge of algebra. I haven't picked it up yet, though.

Don

BruceZ
11-23-2003, 07:32 PM
I am reposting this with a much clearer explanation for the second term in examples 1 and 3. If you read the original post, you can see the typo and further clarification that I posted below it. The examples were intended to show how all of the terms are computed in essentially the same way. Unfortunately, much of this hinged on a couple of key sentences which failed to convey what was intended. Hopefully this post will rectify that. Ignore the previous post, and use this version for reference.

---

As far as texts, I just answered a similar question in this post (http://forumserver.twoplustwo.com/showthreaded.php?Cat=&amp;Number=416704&amp;page=0&amp;view=ex panded&amp;sb=5&amp;o=14&amp;fpart=). Additionally, a classic book just on probability theory (no statistics) is the text by William Feller, Introduction to Probability Theory and it's Applications. Despite its title, it presents many advanced topics, and the explanations are somewhat terse, so it is best for math majors.

Neither text discusses inclusion-exclusion, nor do I know of one that does. A multi-part series by Brian Alspach in Poker Digest called I'm In...No I'm Out (http://www.math.sfu.ca/~alspach/pokerdigest.html) dealt with this topic. I haven't read this one, but it is probably good. I have written many posts on this forum with explanations and examples of this principle. If you search for these posts, they will tell you everything you need to know about this principle to solve practical problems. I have repeated a few of the simplest examples below.

Explanation of the Inclusion-Exclusion Principle

Inclusion-exclusion is based on a very simple idea. Suppose a poker room has 3 waiting lists for 3 different games, and players are allowed to be on more than one list at a time, but of course on each list only once. We want to know how many total players are waiting to play. We could simply add the number of players on each list, but this has the obvious problem that it would count the players that are on 2 lists twice, and it would count the players on all 3 lists 3 times, so this number would be too high if any players are on more than one list. That is, we would have a number equal to:

(single listed) + 2*(double listed) + 3*(triple listed)

If we knew how many were on two or three lists, we could subtract that off to get the answer we want. So suppose we next count all the players that are waiting on two lists by counting the number that are on both list 1 and 2, both lists 2 and 3, and both lists 1 and 3. This would count all the players on exactly 2 of these lists once, which is good, but it would count the players on all 3 lists 3 times. Now if we subtract this number from our previous count, we would get:

<font class="small">Code:</font><hr /><pre>
(single listed) + 2*(double listed) + 3*(triple listed)
-(double listed) - 3*(triple listed)
--------------------------------------------------------------------
single listed + double listed
</pre><hr />

Now if we count the players that are on all 3 lists, we could add this on to get the total number of players waiting.

Why bother with this method of counting? Because in many probability problems, this is the only practical way to count the number of things we need to count, and it actually makes our lives much easier. That is, it is often very difficult to count the members of a union of sets without over counting the members that lie in the intersection of sets. The inclusion-exclusion principle allows us to compute much simpler terms which over count on purpose, and then it fixes the over counting for us.

This method works for counting the members of any number of sets, not just 3. Note that to obtain an exact answer, we need to compute as many terms as there are different sets of members we are counting, in this case 3. The odd numbered terms (starting from 1,3,5..) are always added, and the even numbered terms are always subtracted (reverse that for comp-sci. people who start counting with 0, myself included /images/graemlins/laugh.gif). The idea is that when we add a term, we include some members too many times, so then we subtract a term, but then we exclude some members too many times, etc. That is why it is called "inclusion-exclusion". Successive terms always get smaller, so in most practical problems, we can stop computing terms when we see that the terms have become smaller than our desired degree of approximation, instead of computing all of the terms which is often difficult.

Mathematically, this is what we are doing:

P(A u B u C u ...) = P(A) + P(B) + P(C) + ... - P(AB) - P(AC ) - P(BC) - ... + P(ABC) + ...

where A,B,C... are sets, and (A u B) means the union of A and B, so P(A u B) is the probability of A OR B. (AB) is the intersection of A and B, so P(AB) is the probability of A AND B. So first we add the probabilities of each set, and this is the first term. Then we subtract the probabilities of each pair-wise intersection of sets, and this is the second term. Then we add the probabilities of each 3-way intersection, and this is the third term, etc.

This is all some textbooks may mention (or less) about the probability of a union, usually without even referring to inclusion-exclusion by name. To fully appreciate its usefulness and power requires some examples.

Example 1

This is the simplest non-trivial poker example. If you hold KK before the flop, what is the probability that at least one of your 9 opponents holds AA?

Note that at most 2 opponents can have AA. The probability that any particular player holds AA is 6/C(50,2). So the first term in inclusion-exclusion is simply 9*6/C(50,2). That is the sum of the 9 probabilities of each player having AA. This alone is very close to the exact answer, but it double counts the times that 2 players hold AA. For the second term, we take the probability of 2 particular players having aces, 1/C(50,4), and multiply by the number of ways to pick the two players, which is C(9,2). So the final answer is:

P(KK vs. AA) = 9*6/C(50,2) - C(9,2)/C(50,4)
or about 4.39%

Example 2

Heres a neat "trick". If you hold AA, what is the probability that one of your 9 opponents holds AA?

The probability that a particular opponent holds AA with you is 1/C(50,2). The first term in inclusion-exclusion is 9/C(50,2). Were done, that's the final answer. There are no more terms to compute because it is not possible for more than 1 opponent to have AA with you. That is, the events of different players having AA are mutually exclusive, and youll recall that the probability of mutually exclusive events can always be summed to get the probability of one of the events occurring. Mutually exclusive events are a trivial special case of the inclusion-exclusion principle where there are no intersections, so all terms except the first are zero.

Example 3

Let's do one more example. This one is a little more substantial. If the flop has exactly 2 diamonds, and you don't have a diamond, what is the probability that at least one of your 4 remaining opponents has a 4-flush assuming they hold random cards? Note: It is equally easy to do this problem assuming a realistic distribution of starting hands.

In this case it is possible for up to 4 players to have 4-flushes, so we will have 4 terms in the exact answer. The probability that a particular player has 2 diamonds is C(11,2)/C(47,2). The first term in inclusion-exclusion is thus 4*C(11,2)/C(47,2). For the second term, we take the probability that 2 particular players have diamonds, which is C(11,4)/C(47,4), and we multiply this by the number of ways to choose the 2 players which is C(4,2). Note that this counts the times that more than 2 players have diamonds more than once, but this is exactly what we want for the inclusion-exclusion principle. The second term is thus C(4,2)*C(11,4)/C(47,4). Proceeding the same way for the remaining terms give this exact solution:

C(4,1)*C(11,2) / C(47,2) -
C(4,2)*C(11,4) / C(47,4) +
C(4,3)*C(11,6) / C(47,6) -
C(4,4)*C(11,8) / C(47,8)
or about 19.3% /images/graemlins/diamond.gif

tpir90036
11-23-2003, 08:05 PM
i actually just saw that on amazon today. if they did "probablility and combinatorics for dummies" i would be all over that /images/graemlins/wink.gif i am sure it's good though as most of the "for dummies" books are top notch IMHO.

DPCondit
11-24-2003, 12:58 AM
Of course I'm sure it has good coverage of probability and combinatorics. I don't imagine they are going to write a Dummies book just about probability and combinatorics, but any decent statistics book will be all over that anyways.

Don

DPCondit
11-29-2003, 11:13 PM
I hope I didn't lead anyone astray by suggesting it would probably have good coverage of probability and combinatorics, because IT DOESN'T.

I was browsing through Barnes and Noble today, and I skimmed through the Probability section in the book. To be brief, the coverage is of probability is terrible, and the coverage of combinatorics is NON-EXISTENT. Please don't waste your money on this superficial bit of fluff. You will learn much more in the average well thought out Bruce Z post, than you will learn from this entire book.

Don