An instructive counting / probability question from Alexander Bogomolny

I saw this question from Alexander Bogomolny today through a tweet from Nassim Taleb:

It reminded me a bit of a fun question I saw from Christopher Long a few years ago:

A great introductory probability and stats problem I saw from Christopher Long

The first solution that came to mind for the dice question involved generating functions. Here’s the code I wrote in Mathematica:

Mathematica Code

The general idea was to look at powers of the polynomial x + x^2 + x^3 + x^4 + x^5 + x^6 and keep track of the coefficients for powers greater than x^{12}. The one tiny bit of difficulty is that you also have to strip off the powers of x greater than x^{12} after each stage (since you only want to count the first roll giving you a sum greater than 12). Here’s that polynomial cubed, for example:

Coefficient Example

The coefficients for x^{13} through x^{18} tell us the number of different ways to get a 13 through an 18 with three rolls.

The results of counting the polynomial coefficients are given below (columns give the number of ways to roll 13 through 18, and the rows are the dice rolls 3 through 13):

Counts at each stage

These counts don’t have the right weights, though, since 21 ways of getting a 13 on the 3rd roll have a much higher chance of happening than the 1 way of getting an 18 on the 13th roll. In fact each row has a weight 6x greater than the row immediately below it. Weighting the rows properly we get the following counts:

Total Counts.jpg

Now we just have to add up the columns and divide by 6^{13} to get the probabilities of ending on 13 through 18 (and do a weighted sum to get the expected final number) -> the probability of ending on a 13 is about 27.9% and the expected value of the final number is roughly 14.69:

Probabilities

This is a nice problem to show how generating functions can help you find exact answers to problems that seem to require simulations. It was fun to think through this one.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s