Since it comes up a lot, perhaps this should be a sticky, so I went ahead and attempted to write something worrrthy of stickiness. To that end, I went beyond addressing OP's question and wrote an intro to inclusion-exclusion. The specific response to OP is mostly at the beginning of Part 2, but is also partly covered in Part 1.
Part 1: Background
Suppose you flip a coin twice and want the probability of at least one tails. You know it isn't simply 50% + 50%. The big clue is that you know it can't be 100% (nor 150% with 3 flips), but what's the underlying reason probabilities don't add (or multiply) like that? Well, sometimes they do, for instance if you want the A
, you have a 1/52 chance with one card and a 2/52 chance with 2 cards. What's the difference between those two scenarios? Overlapping possibilities.
There is no overlap in the ace example. Getting the ace with your 1st card or your 2nd card are mutually exclusive possibilities because the A
can only be one of your cards (if any). Each 1/52 is the probability of the A
being an exact card, so there is no overlap between the two 1/52 terms. Therefore, when you add them, nothing is counted more than once.
By contrast, when you flip a coin twice, Tails can occur on one or both flips. There is a 50% chance for the 1st flip and a 50% chance for the 2nd flip. Notice, though, that each of those 50%'s allows the other flip to also be tails. There's a 50% chance of Tx and a 50% of xT, where x can be a T or H.
If you add the TX and XT cases, you're adding (TH & TT) + (HT & TT), so you're double-counting the TT case. That's why the chance of at least one T is not P(Tx) + P(xT), but lower. If you remove the excess TT, you get the right answer: P(T) = P(Tx) + P(xT) - P(TT) = 100% - 25%, which is the Principle of Inclusion-Exclusion at work. That can also be illustrated with a Venn diagram, but I prefer to picture the strings of symbols, especially when we extend the concept to N sets.
Let's extend it to 3 flips. We know it's not 150%, but by how much is that too high?
Each Txx possibility counts a TTx possibility, so when any two Txx possibilities are combined, one of the 3 TT possibilities gets double-counted. Here is my mental model of what's happening:
Txx + xTx double-counts TTx
xTx + xxT double-counts xTT
Txx + xxT double-counts TxT
By adding Txx + xTx + xxT, we have double-counted each of the 3 TT possibilities. We've also triple-counted the TTT case. Therefore, it follows that:
P(T with 3 flips) = 150% - P(exactly 2 tails) - 2*P(TTT) = 150% - 3/8 - 2(1/8) = 7/8
If you wanted the chance of
exactly one tails, you'd simply adjust the above as follows:
P(exactly one T w/ 3 flips) = 150% - 2*P(exactly 2 tails) - 3*P(TTT) = 3/8
However, for problems where it's worth using this approach to begin with (unlike this coin problem), the exactly-2 case would be just as difficult to calculate as the original thing we're trying to calculate. So rather than subtracting the TTH cases, we'd subtract the TTx cases, which is easier in such problems. In doing so, we'd also be subtracting TTT cases, in fact over-subtracting them. Here's what that would look like.
There are 3 TTx arrangements. Since the x is ignored, or equivalently, has a 100% chance, each TTx arrangement has a 25% chance. So from 150% we subtract 75%. Our original 150% triple-counted the TTT. But for each TTx case we subtracted, we also subtracted the TTT case, so overall it got added 3 times and then subtracted 3 times for a net result of 0. It needs to be added back in.
P(T with 3 flips) = 3(1/2) - 3(1/4) + 1/8 = 7/8
Mind you, the problem can also be solved using only addition, but only if there's no overlap among what you're adding: P(T with 3 flips) = P(exactly one T) + P(exactly 2) + P(TTT)
Part 2: Card Examples
Quote:
What % of the time will KK flop at least 1 K & AA will not flop an ace?
A common mistake is to make the numerator C(2,1)*C(45,2). That numerator counts the Kxx cases, but since another K is part of the 45, the x's are allowed to be another K, which means the KKx cases are counted twice.
You can visualize it the same way I illustrated it with the 3 coinflips when listing the Txx vs TTx cases. There's also a numerical explanation.
If instead of the Kxx cases, you wanted to count the KKx cases, you'd correctly say C(2,2)*44. Notice how the two kings are both picked at the same time, hence the C(2,2) term instead of C(2,1).
Let's make it explicit by rewriting the bad numerator:
C(2,1) * [C(44,2) + C(1,1)*44]
What you've done is counted the KKx cases C(2,1)*C(1,1) times instead of C(2,2).
A warning sign was that you picked from the same set (of two kings) twice separately. As a rule of thumb, any time you find yourself picking from the same set more than once (which I'll call "double-dipping"), especially when you don't intend for the order of selections to matter, you have to watch out for overcounting.
To get the correct answer, you can either subtract the excess KKx combos or, from the start, split the problem into non-overlapping cases. If we let "o" represent non-kings, you can add the K-o-o cases and the KKo cases: C(2,1)*C(44,2) + C(2,2)*44
Quote:
5 hold'em players go to the flop and it's all diamonds. What's the chance that at least 2 of them flopped a flush?
49 cards remain, 10 of which are diamonds.
Unlike the other examples, inclusion-exclusion is a time-saving approach to this problem, and probably the most efficient one. It makes this otherwise tedious problem quick and easy (potentially).
Start with the FFxxx cases. There are C(5,2) ways to pick 2 players who to get the flushes. The other 3 players are allowed to have anything, so we can greatly simplify the calculation by ignoring them, which looks like:
C(5,2)*C(10,4) / C(49,4)
If we didn't ignore the unchosen players, we'd have a larger numerator and a proportionally larger denominator:
C(10,4)*C(45,6) * 3*(5*3) / [C(49,10) * 9*7*5*3]
Ignoring is clearly better! But notice how the 45 includes the rest of the diamonds, so C(45,6) means they can be picked again. Just like in the previous example, this double-dipping results in the cases of >4 diamonds to be overcounted. With the shorter method, the same thing is happening, except it's visible in the form of the denominator being too small rather than the numerator being too large. What the two expressions have in common is that they're counting FFxxx cases where the x's are all-inclusive. The inclusiveness of the x's results in overlap, and so things get overcounted. This time, however, we're overcounting on purpose (with the plan of correcting later), since the x's make the calculations easier.
Anyway, we started with P(FFxxx). That triple-counts P(FFFxx), so we have to subtract that twice:
- 2*C(5,3)*C(10,6) / C(49,6)
As a rule of thumb, +'s and -'s always alternate, so our next step will be to add something. Next up is P(FFFFx). It was counted C(4,2) times, then subtracted 2*C(4,3) times for a net count of -2. To make the count +1, we'll add it back 3 times:
+ 3*C(5,4)*C(10,8) / C(49,8)
Finally, the case of all 5 players having a flush. Without any math, I already know it needs to be subtracted 4 times, because these error/correction coefficients follow patterns.
- 4 / C(49,10)
In entirety, after simplification: C(5,2)*C(10,4)*[1/C(49,4) - 2/C(49,6)] + 3*5*C(10,2)/C(49,8) - 4/C(49,10)