Matrix Multiplication in Excel — Markov Chains

This post is part of the “Matrix Multiplication in Excel” series. It’s composed of a math introduction, a silly interlude and an interactive tutorial (you are here). By the end of the series, you’ll learn how to perform Markov Chain calculations, which are used in some damage calculations.

Now that we know some of the basics, I’m going to introduce a toy problem where one would use matrix multiplication, step through how to calculate it in Excel and then give an example used forensic economics.

Click here to download Matrix Multiplication.xlsx.

Scenario 1: Ping Pong Problem

Suppose two ping pong players (labelled left and right) are tied near the end of a game. In order to win, one of them has to have a two point lead. Suppose that, on any given volley, the left player has a 55% chance of winning.

The game can be thought of as having five states:

  1. (2,0) – The left player wins.
  2. (1,0) – The left player is winning by one.
  3. (0,0) – The game is tied.
  4. (0,1) – The right player is winning by one.
  5. (0,2) – The right player wins.

Graphically, the transitions between these states can be seen as follows.

ppFig1

The left player increases his score with the probability p(LW), in this case 55%. How do we calculate the probability that the left player wins?

This problem can be formalized as a Markov Chain, a mathematical system in discrete-time which transitions through various states.

To simulate a Markov Chain, start by creating a matrix P1 of size 1 x s where s is equal to the number of states. Element p1_{1,j} gives the probability the system starts in state j. Next create a transition matrix T of size s x s. Element t_{i,j} gives the probability the system moves from state i to state j.

In this example, we’ve stated the game starts at tied in state (0,0). The starting probability vector and transition matrix are displayed below.

ppFig1-1

Now we get to the value of matrix multiplication. As discussed previously, multiplying a 1 x s matrix by an s x s matrix produces a 1 x s matrix. If you step through the math of matrix multiplication, you’ll see that multiplying P1 by matrix T produces the probability the system will be in a given state in at the start of the next serve. This process can be iterated indefinitely to generate probability distributions at any given interval of time. The first ten steps are shown below.

ppFig1-2

Starting with a tie game, after two serves there’s a 30.25\% chance the left player will win, a 20.25\% chance the right player will win and a 49.50\% chance the game will still be tied. With enough iterations, we can see that there’s approximately a 59.90\% chance the left player will win.

Scenario 2: Racquetball Problem

In the Excel book, I also included a second scenario for a racquetball-like scoring system where you only score points if you’ve served. The slightly more complex state diagram and iterations are displayed below.

ppFig2

ppFig2-1

By changing the inputs, one could use this model to answer questions like “what is the value of serving first?” or “how often does the ‘better’ player win?”

Creating Matrix Multiplication Problems in Excel

Matrix multiplication in Excel is slightly different from standard formulas because the returned result is an array of numbers. Usually, excel formulas return a single result.

Instead of using a standard formula, you will have to use an array formula. To create a normal formula, simply type it into the cell and type “enter.” To create an array formula, instead press “control-shift-enter.” This will add curly braces around the formula to let you know it’s an array formula, as seen in the following screenshot. In some circles, these are called CSE formulas because of the key stroke which creates them.

ppFig3

To see how to create matrix multiplication CSE formula, follow these steps:

  1. Clear the iterated matrix multiplication in scenario 1.
    • Use Ctrl-G to select “‘S1. Matrices’!B14:F62.” Press delete to clear the contents.
  2. Select range B14:F14. Leave B14 as the “active cell.”
  3. Enter the following formula into B14:
    • =MMULT(B4:F4,B7:F11)
    • Press “Control-Shift-Enter” to have this formula applied across the entire selected range.
    • I’ve named the ranges “S1.MA” and “S1.MB”, respectively. Feel free to use these “dynamic range names” in your formula instead.
  4. Repeat the process for the remaining iterations, except replace “S1.MA” with the previous iteration.
    • Make sure you use proper absolute/relative references so the process continues downwards.
    • For row 15: =MMULT($B14:$F14,$B$7:$F$11)
    • For rows 16 and on, you can Copy and Paste-Special Formulas.

If you receive an error while trying to implement matrix multiplication in Excel, you’ve likely specified an incorrect number of dimensions. As we discussed in a previous post: When you multiply an m x p matrix by a p x n matrix, you produce an m x n matrix. The number of columns in the first matrix has to match the number of rows in the second matrix. The resulting matrix will have the number of rows from the first matrix and the number of columns from the second matrix.

Markov Chains in Economic Damage Cases

Markov Chains are commonly used to measure lost earning capacity. In any given year, a subject can be in one of several states (i.e. employed, unemployed, dead). Hopefully the analog to the ping pong problem is clear. Statistical information can give us “transition probabilities” which state the probability of a worker moving from one state to another based on the the current state. A currently employed worker is more likely to be employed the next year than a currently unemployed worker. A dead worker will stay dead in the same way a finished game of ping pong will stay finished.

In every year, we are left with a probability of the subject being in the “employed” state, necessary information for valuing his or her potential income stream.

The ping pong example is memoryless. The game of ping pong doesn’t care if this is the first or thousandth time the right player has been one away from winning. In some more sophisticated Markov Chain calculations, the transition probabilities depend on not only the current state but the state of prior years. For instance, a subject who has been employed for the past two years is more likely to be employed next year than a subject who was gainfully employed for only one year.

Conclusion

We’ve covered a lot of ground in this series. We learned the basics of linear algebra and Markov Chains. We learned how to implement these concepts in Excel and even considered the thermodynamic consequences of living in the Matrix.

If you were intimidated by any of these concepts before, hopefully I’ve unpacked them enough to take the magic out. Like most apparently complex things, matrix multiplication is merely a few simple things done many times over.