I'm In ... No, I'm Out: Part VI

Brian Alspach

Poker Digest Vol. 2, No. 19, September 10 - 23, 1999

In this last article in the series dealing with inclusion-exclusion, we are going to examine a different setting for applying it. We presented the principle of inclusion-exclusion in terms of counting numbers of objects having certain properties. If we look at the formula in Part I of this series and divide every term by A, the total number of objects, we get terms of the form A(i)/A. These numbers are nothing more than probabilities. That is, there is a corresponding inclusion-exclusion formula for probabilities. This can be advantageous because the computations involved for determining the probabilities may be less complex than doing the counting directly. Let P(i) denote the sum of the probabilities of a set of i properties holding summed over the collection of all subsets of i properties, that is, P(i)=A(i)/A. Then the probability P that none of the properties hold is given by

\begin{displaymath}P = 1 - P(1) + P(2) - P(3) + \cdots + (-1)^kP(k),\end{displaymath}

where k is the total number of properties.

We now illustrate by looking at two examples involving calculations done in earlier articles. Suppose we have a player in Omaha high-low holding A-2-H-H, where H denotes a 9-10-J-Q or K, the board has three low cards of distinct ranks, but no ace or deuce, and we want to compute the probability no one else has an A-2. We first compute the probability player j has an A-2. Player j can hold A-A-A-2, A-A-2-2, A-A-2-x, A-2-2-2, A-2-2-x, or A-2-x-y. There are three choices for A-A-A-2, nine choices for A-A-2-2, $9\cdot 37$ choices for A-A-2-x and so on. Altogether there are 6,675 choices for these hands. There are C(43,4) = 123,410 ways of dealing four cards to player j. Thus, the probability player j receives an A-2 is 6675/123410. Since there are nine other players, we must multiply the preceding probability by nine to obtain P(i). Doing so yields P(1) = .48679.

We next compute P(2). We count the number of ways players i and jboth receive an A-2 in their hands. There are 15,980,004 ways for this to happen as there are only nine patterns for the two hands. We multiply this by C(9,2) = 36 because that is the total number of ways of choosing two players from nine. We then divide by C(43,4)C(39,4) which is the number of ways players i and j can be dealt four cards apiece. This gives P(2) = .05667.

Finally, we do the same for three particular players being dealt A,2. This is particularly easy because there is only one pattern for the three players to receive an A-2 apiece. There are 7,532,300,160 deals. This is then multiplied by C(9,3) and divided by C(43,4)C(39,4)C(35,4)which produces .001190. Note that this agrees, as it should, with the figure .0012 obtained in Low Board Blues: Reprise and Coda. We then use the inclusion-exclusion formula to obtain

P = 1 - P(1) + P(2) - P(3) = .568690

which agrees with the figure given in the article cited in the preceding sentence. However, you will note the result has been obtained with considerably less computation. Also, we note that William Chen, who just completed his Ph.D. in mathematics at UC Berkeley (congratulations William!), did a similar calculation using inclusion-exclusion to obtain the probabilities for other people being dealt A,2 given no cards have appeared in the board. He posted his calculations on RGP and they corroborated the figures given in the article cited above.

Let's now consider flushes in hold'em. Suppose we have a player who has two hearts in her hand with three hearts in the board. She wants to know the probability no one else has a flush. Again we assume there are nine other players. Since there are eight hearts unaccounted for, there can be at most four other players also holding two hearts in their hands. The probability player i has two hearts is 28/990 because there are C(8,2) = 28 ways for player i to have two hearts and C(45,2) = 990possible hands for player i. Multiplying by nine and simplifying gives P(1) = 14/55.

For players i and j, there are C(8,2)C(6,2) = 420 ways both can receive hearts and C(45,2)C(43,2) = 893,970 they can receive two hands. We have to multiply by C(9,2) = 36 obtaining P(2) = 15120/893970 = 8/473.

In a similar manner we obtain P(3) = 28/96965 and P(4) = 14/23950355. Inclusion-exclusion then tells us the probability no one else has a flush is

P = 1 - P(1) + P(2) - P(3) + P(4) = .76208

which agrees (of course!) with the figure of .762 published in Flushing Meadows: Part V.

Bib Ladder then asked me (as many readers probably are asking as well), ``Why did you do these problems earlier using direct counting methods which required considerably more computation than what you did above?'' This is a good question and this is what I told Bib.

The basic counting techniques we started with are fundamental and must be included in any counting toolkit. We then saw how they could be used to handle a wide variety of counting problems. They are more or less fail-safe in that more sophisticated tools do not always work and sometimes lead people astray whereas the basic techniques usually can be made to work although sometimes at the cost of more labor. Now inclusion-exclusion is a powerful counting technique but it is applicable only for certain problems. Even at that one still uses basic counting techniques when applying inclusion-exclusion so you have to be able to use them. The point is that you now have a choice of more than one method for certain counting problems. In the future we shall be free to bring inclusion-exclusion into the fray if it is useful.

Home | Publications | Preprints | MITACS | Poker Digest | Poker Computations | Feedback
website by the Centre for Systems Science
last updated 27 August 2001