## A very clever way to solve the first Monday Math Madness problem

On March 3rd Blinkdagger and I posted the first Monday Math Madness problem. On March 11th, after the first contest ended, I posted a couple of different solutions to the problem. Pat Ballew, even though he wasn't picked as the random winner, impressed me with a very clever solution to the problem that generalizes very nicely. He uses an approach called Markov state matrices, which I had never heard of. It seems to me that this approach is pretty similar to the one I posted from Richard Berlin. Pat and I exchanged several emails where he explained the method and here is my attempt to explain what Pat explained to me.

This was the problem:

A popular blog has just three categories: brilliant, insightful, and clever. Every blog post belongs to exactly one of the three categories and the category for each post is selected at random. What is the probability of reading at least one post from each category if a reader reads exactly five posts?

Pat's approach starts by creating a matrix that encodes the probabilities of going from one "state" to another as a new blog post is read. State just refers to whether 0, 1, 2, or 3 categories have been encountered after reading some number of blog posts. After one blog post has been read we are in state 1 (1 category has been read). After two posts have been read we may be in state 1 (if both blog posts are in the same category), or state 2 (if the two categories are different), but not in state 3 (you could not have encountered three categories after having read only two blog posts.)

If we look at probabilities as one moves from state to state we get the following, where p(x,y) is the probability of going from state x to state y by reading one more blog post.

p(1,1) = 1/3. If we are in state 1 (have read one category), the next blog post can be in any of the three categories and there is a 1/3 chance that the next post will be the same category as the one we've encountered in all previous posts and that we'll remain in state 1.

p(1,2) = 2/3. There's a 2/3 chance that the next post will be in one of the two categories other than the one we've encountered in all previous posts (state 1).

p(1,3) = 0. There's no way to go from state 1 to state 3 by reading one more post. We have to get to state 2 first.

Note that p(1,1) + p(1,2) + p(1,3) = 1. In other words, the probability of going from state 1 to any state (1, 2, or 3) after reading one more blog post is 100%.

p(2,1) = 0. Once we've seen two categories we can't go back to having seen only one.

p(2,2) = 2/3. If we've seen two categories, there's two ways we can see one of those two again (and stay in state 2) and only one way we can get the third category (and go to state 3.)

p(2,3) = 1/3. Once we've seen two categories, 1/3 of the time we'll see the category we've not seen before.

Again, note that p(2,1) + p(2,2) + p(2,3) = 1.

p(3,1) = 0. Once we've seen all three categories, we can't get to a state where we've seen only one.

p(3,2) = 0. Once we've seen all three categories, we can't get to a state where we've seen only two.

p(3,3) = 1. Once we've seen all three categories, regardless of what category we see next we will have seen all three.

Note that p(3,1) + p(3,2) + p(3,3) = 1.

Now, here's where things get interesting. Take all the probabilities that we have computed and encode them into a matrix like this:

1/3 2/3 0

0 2/3 1/3

0 0 1

Notice that we've created the matrix using these probabilities:

p(1,1) p(1,2) p(1,3)

p(2,1) p(2,2) p(2,3)

p(3,1) p(3,2) p(3,3)

Now the real interesting part, which I don't get intuitively but probably would if I sat down and drew some probability trees, is that to solve the problem, which in state talk is to find the probability of getting to state 3 (all categories seen) after reading five blog posts, you take the matrix we created, raise it to the 4th power, and look at the entry in row 1, column 3 (the entry that contains the probability of getting to state 3 from state 1.)

Let's call our matrix A. A contains the probabilities of being in different states after reading the second blog post. There is no matrix corresponding to having read just one blog post. You are always in state 1 after the first post.

So, A shows probabilities after 2 posts have been read.

It turns out that A^2 shows probabilities after 3 posts have been read.

A^3 shows probabilities after 4 posts have been read.

A^4 shows probabilities after 5 posts have been read.

While matrix multiplication can be a little tedious, in this problem there are a number of 0's which simplify the arithmetic.

When I do the multiplication I get:

A^2 = [ ( 1/9, 6/9, 2/9 ), ( 0, 4/9, 5/9 ), ( 0, 0, 1) ]

A^3 = [ (1/27, 14/27, 12/27), (0, 8/27, 19/27), (0, 0, 1) ]

A^4 = [ (1/81, 30/81, 50/81), (0, 16/81, 65/81), (0, 0, 1) ]

If it's not clear, I've written each matrix, m, as [ ( m(1,1), m(1,2), m(1,3) ), ( m(2,1), m(2,2), m(2,3) ), (m(3,1), m(3,2), m(3,3) ) ].

So, we've done all the hard work. To get the answer to the contest problem we look at the matrix for A^4. We look at the entry for A^4(1,3) (getting from state 1 to state 3) and we see that that value is 50/81. so, that's our answer.

I hope that you appreciate that with this method we can answer all kinds of problems. For example, if we wanted to know what the probability was of seeing all three categories after having read just three blog posts we look at A^2(1,3) and we see that the probability is 2/9. And, the probability of seeing all three categories after reading four blog posts is A^3(1,3) = 12/27.

This is a very nice technique indeed. Once you set up the initial matrix, it's just a matter of doing the matrix multiplications to get the answer you need. Thanks, Pat, for teaching me this very nice technique.

Clint HamadaMarch 23rd, 2008 - 18:55

Very interesting indeed. While I can follow along, I’m not sure I can explain exactly why it works (yet).

What’s more interesting to me, however, is how your post highlights the difficulties associated with blogging about mathematics. How can I (or more importantly, my students) blog about mathematical topics and easily use the appropriate mathematical notation? Somebody who can help me solve this problem will have my eternal gratitude!

LaReneMarch 26th, 2008 - 13:43

I love people who can get excited about numbers. I marvel at your thinking and it makes me smile to see what you just did. Numbers are not my favorite equation to work with. I meet so many people who are passionate about them. It makes me feel like I’m missing something special in life.

Ξ_HeatherMarch 30th, 2008 - 10:15

This is fantastic! I showed it to my students, and used it to approach a similar problem I was wondering about [breaking down the matrix into eigenvalues and eigenvectors to make it easier to take it to a higher power]. Thanks for sharing this, Pat and Sol!

Debt Free or Bust - SherriMarch 30th, 2008 - 11:31

Absolutely brilliant solution!

This is an ideal example for my advanced math/precalc students. It’s not just a formula, you have to think about what’s going on in the problem, something many of my students don’t believe they need to do. They tend to carry that attitude over to physics and chemistry as well, and then wonder why they aren’t making good grades.