Game Theory (Part 10)

Last time we solved some probability puzzles involving coin flips. This time we’ll look at puzzles involving cards.

Permutations

Example 1. How many ways are there to order 3 cards: a jack (J), a queen (Q), and a king (K)?

By order them I mean put one on top, then one in the middle, then one on the bottom. There are three choices for the first card: it can be A, Q, or K. That leaves two choices for what the second card can be, and just one for the third. So, there are

3 \times 2 \times 1 = 6

ways to order the cards.

Example 2. How many ways are there to order all 52 cards in an ordinary deck?

By the same reasoning, the answer is

52 \times 51 \times 50 \times \cdots \times 2 \times 1

This is a huge number. We call it 52 factorial, or 52! for short. I guess the exclamation mark emphasizes how huge this number is. In fact

52! \approx 8.06 \times 10^{67}

This is smaller than the number of atoms in the observable universe, which is about 10^{80}. But it’s much bigger than the number of galaxies in the observable universe, which is about 10^{11}, or even the number of stars in the observable universe, which is roughly 10^{22}. It’s impressive that we can hold such a big number in our hand… in the form of possible ways to order a deck of cards!

A well-shuffled deck

Definition 1. We say a deck is well-shuffled if each of the possible ways of ordering the cards in the deck has the same probability.

Example 3. If a deck of cards is well-shuffled, what’s the probability that it’s in this order?

Since all orders have the same probability, and there are 52! of them, the probability that they’re in any particular order is

\displaystyle{ \frac{1}{52!} }

So, the answer is

\displaystyle{ \frac{1}{52!} \approx 1.24 \times 10^{-68} }

A hand from a well-shuffled deck

Suppose you take the top k cards from a well-shuffled deck of n cards. You’ll get a subset of cards—though card players call this a hand of cards instead of a subset. And, there are n choose k possible hands you could get! Remember from last time:

Definition 2. The binomial coefficient

\displaystyle{ \binom{n}{k} = \frac{n(n-1)(n-2) \cdots (n-k+1)}{k(k-1)(k-2) \cdots 1}}

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

I guess card-players call a set a ‘deck’, and a subset a ‘hand’. But now we can write a cool new formula for n choose k. Just multiply the top and bottom of that big fraction by

\displaystyle{  (n-k)(n-k-1) \cdots 1}

We get

\begin{array}{ccl} \displaystyle{ \binom{n}{k}} &=& \displaystyle{  \frac{n(n-1)(n-2) \cdots 1}{(k(k-1)(k-2) \cdots 1)((n-k)(n-k-1) \cdots 1)} } \\ &=& \displaystyle{ \frac{n!}{k! (n-k)!} } \end{array}

I won’t do it here, but here’s something you can prove using stuff I’ve told you. Suppose you have a well-shuffled deck of n cards and you draw a hand of k cards. Then each of these hands is equally probable!

Using this we can solve lots of puzzles.

Example 4. If you draw a hand of 5 cards from a well-shuffled standard deck, what’s the probability that you get the 10, jack, queen, king and ace of spades?

Since I’m claiming that all hands are equally probable, we just need to count the number of hands, and take the reciprocal of that.

There are

\displaystyle{ \binom{52}{5} = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2 \times 1} }

5-card hands drawn from a 52-card deck. So, the probability of getting any particular hand is

\displaystyle{  \frac{1}{\binom{52}{5}} = \frac{5 \times 4 \times 3 \times 2 \times 1}{52 \times 51 \times 50 \times 49 \times 48} }

We can simplify this a bit since 50 is 5 × 10 and 48 is twice 4 × 3 × 2 × 1. So, the probability is

\displaystyle{  \frac{1}{52 \times 51 \times 10 \times 49 \times 2} = \frac{1}{2598960} \approx 3.85 \cdot 10^{-7}}

A royal flush

The hand we just saw:

{10♠, J♠, Q♠, K♠, A♠}

is an example of a ‘royal flush’… the best kind of hand in poker!

Definition 3. A straight is a hand of five cards that can be arranged in a consecutive sequence, for example:

{7♥, 8♣, 9♠, 10♠, J♦}

Definition 4. A straight flush is a straight whose cards are all of the same suit, for example:

{7♣, 8♣, 9♣, 10♣, J♣}

Definition 5. A royal flush is a straight flush where the cards go from 10 to ace, for example:

{10♠, J♠, Q♠, K♠, A♠}

Example 5. If you draw a 5-card hand from a standard deck, what is the probability that it is a royal flush?

We have seen that each 5-card hand has probability

\displaystyle{ \frac{1}{\binom{52}{5}} = \frac{1}{2598960} }

There are just 4 royal flushes, one for each suit. So, the probability of getting a royal flush is

\displaystyle{ \frac{4}{\binom{52}{5}} = \frac{1}{649740} \approx 0.000154\%}

Puzzles

Suppose you have a well-shuffled standard deck of 52 cards, and you draw a hand of 5 cards.

Puzzle 1. What is the probability that the hand is a straight flush?

Puzzle 2. What is the probability that the hand is a straight flush but not a royal flush?

Puzzle 3. What is the probability that the hand is a straight?

Puzzle 4. What is the probability that the hand is a straight but not a straight flush?

7 Responses to Game Theory (Part 10)

  1. Arrow says:

    The hard part seems to be the shuffling – if we start from an ordered deck and do some standard shuffling how close will the deck be to a well-shuffled state?

    • John Baez says:

      There’s been a lot of research on this, with Persi Diaconis playing a leading role. Here’s a good quick overview with references:

      Shuffling playing cards – research, Wikipedia.

      A rough rule of thumb is ‘7 riffle shuffles are enough’. But the details are complex and fascinating.

      • Graham Jones says:

        8 riffle shuffles may not shuffle at all.
        http://en.wikipedia.org/wiki/Out_shuffle

        • John Baez says:

          Cool! These are ‘perfect’ shuffles, where you interleave the cards in a perfectly alternating way. And yet again, Diaconis seems to be behind this result:

          • Persi Diaconis, Ronald Graham and William M. Kantor, The mathematics of perfect shuffles, Advances in Applied Mathematics 4 (1983), 175–196.

          There are two kinds of perfect shuffles: out shuffles, where the top card stays on top, and in shuffles, where it doesn’t. Here’s a wacky result from this paper: you have a deck of 24 cards, the group of permutations generated by in and out shuffles is the semidirect product of (\mathbb{Z}/2)^{11} and the Mathieu group M_{12}.

          This Mathieu group is an amazing group with 12 × 11 × 10 × 9 × 8 = 95,040 elements. It acts in a sharply quintuply transitive way on a 12-element set, meaning that you can take any 5-tuple of distinct elements of that set and find a unique element of the group that maps it to any other 5-tuple of distinct elements! Apart from symmetric and alternating groups, there are only a few groups that are k-tuply transitive for k > 3, so this group is very special. This group is also ‘simple’, meaning that it doesn’t have any nontrivial normal subgroups. There’s also a cool description of this group in terms of 12 balls rolling on a ball of the same size!

          Ronald Graham is the guy that Graham’s number is named after. Diaconis and Graham won a writing prize at the Joint Mathematics Meetings in San Diego this January. Upon accepting the prize they played a card trick. I later asked Graham about the somewhat mysterious story behind Graham’s number, and he clarified it.

        • Graham Jones says:

          Ok, I give up, you win the Cool Maths of Shuffling Game.

        • John Baez says:

          Sorry, I’m a showoff… but I only learned this Cool Maths of Shuffling by checking out your reference and finding that paper by Diaconis on perfect shuffles. And I got so excited by this new appearance of the Mathieu group M_{12} that I posted this! So thanks.

    • davidtweed says:

      Note that an important point is that in most real games you’re not starting from just some ordered deck of cards, but because of patterns of play in the previous game (hands of whist, games of poker, etc, depending on the game) “high value” cards will be clustered together. This tends to mean that if there are also imperfections in the rifling they’re less likely to be separated and then the tend to get redistributed fairly evenly by a “rotating round the table” deal. So real shuffles+dealings tend to be more “balanced” than genuinely random selections, which have more very good and very bad hands.

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

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