Applying LRMC Rankings to College Football, Part One

The following was originally published on the CFBD Blog and has been reproduced here with edits for clarity.

As Bill covered earlier this season , calculating strength-of-schedule adjusted metrics like SRS are a little tricky given how few non-conference games teams play this year. While I think his technique for conference-based SRS is a great attempt at a really difficult problem, I think there is some value in discussing alternative approaches to evaluating team strength this year that do not struggle with the same singularity issues as SRS. I hope to cover one of them in this post and a following post: Logistic-Regression/Markov Chain ratings, or as they are more commonly known, LRMC .

This post covers the mathematical concepts behind LRMC. If you are unfamiliar with Markov chains this should be a useful read for you! You may feel inclined to skip this post and proceed right to part two with the code (which you can do here), but I highly recommend making sure you have a good understanding of the math first!

An Overview of LRMC#

LRMC is a rating systems devised by Georgia Tech professors Dr. Joel Sokol and Dr. Paul Kvam (largely maintained by Dr. Sokol) designed to predict the results of college basketball games¹². As the name implies, the system uses two different modeling techniques to generate ratings, logistic regression and a Markov chain.

To best explain how LRMC works, we can use an example. Imagine a 3 team league consisting of Team A, Team B, and Team C who each play 4 games, a home-and-home series, against the other teams in the league. Here are the results of those games for a given season.

Let’s give you the task of figuring out who the best team was. Not terribly easy, given that every team finished exactly 2-2!

You decide to start your rankings alphabetically, as a prior, and iterate through them to come up with the best answer: so Team A is ranked 1st, Team B 2nd, and Team C 3rd. However, is it fair to rank Team A over Team B? After all, Team B beat Team A by a slightly larger margin on Team B’s home court than Team A beat Team B by on Team A’s home court. What about Team C over Team B? After all, Team C recorded the largest margin of victory over Team B. But then couldn’t we also give some credence to Team A, who beat Team C at home while playing them close on the road? Quickly, we’re entering a bit of a loop in terms of evaluating teams. Which is good! This loop is how we’ll arrive at an answer. But first, it would be good to know how much weight we should place on certain margins of victories for different teams. This is where the logistic regression part of LRMC comes in.

Using Logistic Regression to Pick Teams#

Taking advantage of college basketball’s home-and-home scheduling system for conference games, Sokol and Kvam compiled the margins of victories in those games for the winning teams and ran a logistic regression³ on those margins of victories to determine those team’s odds of winning the road game of that session (in other words, the logistic function $$ f(x_{a,b}) \approx s_x $$ where x_a,b is the point differential for Team A that occurred when they hosted Team B and s_x are the odds Team A will beat Team B on the road). From there, Kvam and Sokol found the value of x for which s_x = 50%, then used that value to determine the home field advantage and adjust their equation for s_x to find r_x, the odds of Team A winning on a neutral court (or, the true talent win probability for Team A).⁴

I’ll do the hard work for you; here are values of r_x for each of the games (the odds the home team is better than the away team based on the point differential of each game)⁵⁶:

With these probabilities established, we can now do some looping, using the second part of LRMC: the Markov chain.

An Introduction to Markov Chains#

Markov chains are an exceedingly useful modeling technique designed to simulate random events that have a sort of stickiness to them, as a value moves from one state to another.

As an introduction, here is a sample Markov chain problem: Imagine that you love to eat two different foods, and have one of either tacos or pizza every day. However, if you ate pizza the day before, there’s a 70% chance you feel like switching it up the next day and have tacos, and a 30% chance you feel like having another slice the next day. If you ate tacos the day before, there’s a 50% chance you’ll have more tacos today, and a 50% chance you’ll have pizza. Here’s a far reaching question: given that you ate tacos yesterday, what will you want to eat 5 days from now?

To answer this question, we can use something called a transition matrix. Think of a transition matrix like a magic box – we put numbers in the right side and it spits an output from the top. This matrix is represented as P.

$$ P = \begin{bmatrix} 0.5 & 0.5\\\
0.7 & 0.3 \end{bmatrix} $$

If you’re confused about what P stands for, just think about it this way: the matrix is just restating the probabilities we discussed in the opening paragraph of this section.

Our input is essentially a binary representation of the row names of P, with a 1 indicating what we ate and a 0 representing what we did not eat. We’ll represent this matrix as:

$$ x^{(0)} = \begin{bmatrix} 1 & 0 \end{bmatrix} $$

To obtain the odds of what we eat tomorrow, we just need to multiply our matrix by P.

$$ x^{(0)} \cdot P = x^{(1)} $$

$$ \begin{bmatrix} 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0.5 & 0.5\\\
0.7 & 0.3 \end{bmatrix} = x^{(1)} $$

$$ \begin{bmatrix} 1 \cdot 0.5 + 0 \cdot 0.7 & 1 \cdot 0.5 + 0 \cdot 0.3\end{bmatrix} = x^{(1)} $$

$$ \begin{bmatrix} 0.5 & 0.5 \end{bmatrix} = x^{(1)} $$

Little surprise here: as we previously said, when we ate tacos yesterday, there is a 50% chance we eat tacos today, and a 50% chance we eat pizza today.

What if we want to know what we eat tomorrow? Then the output of x⁽⁰⁾ times P becomes x⁽¹⁾ and we repeat the process over again.

$$ x^{(1)} \cdot P = x^{(2)} $$

$$ \begin{bmatrix} 0.5 & 0.5 \end{bmatrix} \cdot \begin{bmatrix} 0.5 & 0.5\\\
0.7 & 0.3 \end{bmatrix} = x^{(2)} $$

$$ \begin{bmatrix} 0.5 \cdot 0.5 + 0.5 \cdot 0.7 & 0.5 \cdot 0.5 + 0.5 \cdot 0.3\end{bmatrix} = x^{(2)} $$

$$ \begin{bmatrix} 0.6 & 0.4 \end{bmatrix} = x^{(2)} $$

So given that we ate tacos yesterday, there is a 60% chance we eat tacos tomorrow, and a 40% chance we eat pizza tomorrow.

This is a Markov chain in action! We have taken an initial state vector (x⁽⁰⁾), multiplied it by our transition matrix (P), then taken the outcome of that (x⁽¹⁾) and multiplied it again by P to find x⁽²⁾ – the so-called “chaining”. For the algebraically inclined, you will find that given an initial state x⁽⁰⁾ and a constant transition matrix P, to find x^(k), you can skip some steps and just use this formula⁷:

$$ x^{(0)} \cdot P^{k} = x^{(k)} $$

So on the 5th day, given that you ate tacos yesterday, your odds of eating tacos versus pizza are $$x^{(5)} = \begin{bmatrix} 0.583 & 0.417 \end{bmatrix}$$ or a 58% chance of eating tacos versus a 42% chance of eating pizza.

You’ll notice that as the value of k increases, the probability of us landing in a given state approaches some finite value. For example:

For k = 1, there is a 50% chance we will eat tacos.

For k = 2, there is a 60% chance we will eat tacos.

For k = 3, there is a 58% chance we will eat tacos.

For k = 4, there is a 58.4% chance we will eat tacos.

Note that we approach this same state even if we had eaten pizza yesterday:

$$ \text{if } x^{(0)} = \begin{bmatrix} 1 & 0 \end{bmatrix} \text{ then } x^{(5)} = \begin{bmatrix} 0.583 & 0.417 \end{bmatrix} $$

$$ \text{if } x^{(0)} = \begin{bmatrix} 0 & 1 \end{bmatrix} \text{ then } x^{(5)} = \begin{bmatrix} 0.584 & 0.416 \end{bmatrix} $$

In other words, this system approaches a “steady state”, where in the long run, our odds of eating pizzas versus tacos on a given day are two constant values. Not every Markov chain approaches a steady state⁸, but ours does – how do we find out what it is?

We have two ways of finding that steady state. We can simply calculate what our final state vector will look like at some time in the far-off future, like x⁽⁰⁾ • P¹⁰⁰⁰. However, we can solve for an exact answer by calculating the eigenvector of our transition matrix P⁹. In either approach, you will arrive at a steady state of [0.583, 0.417]¹⁰.

Putting it all together#

Let’s return to our teams and their records. Previously, we calculated r_x for each game, the odds that the home team would beat the away team on a neutral court given the point differential in that game. We can take these probabilities and convert them into a transition matrix to generate our rankings.

Borrowing from the analogy first deployed by Callaghan, Mucha, and Porter in proposing the application of this method to sports¹¹, imagine a room full of monkeys who randomly choose a game and determine whether or not the home team or the road team is better using r_x. A transition matrix will not just reflect the odds of which team is better, but the odds of choosing a particular game as well. To generate our transition matrix, we sum up r_x for games involving a particular team (let’s say, Team X) by team. In the row of Team X, we place each team’s sum of r_x in each team’s corresponding column (including Team X). Then, we divide all of the values in the row by the number of games Team X played.

Let’s say [1,0,0] represents an initial state vector, a monkey with a random prior belief that Team A is better than Team B or Team C. To evaluate their prior, they watch a random game that Team A played. There is a 50% chance that they pick a game where Team A faced Team B, and a 50% chance that they pick a game where Team A faced Team C. If they pick a game where Team A faced Team B, there is a 52% chance they walk away from that game thinking that Team B is better than Team A; if they pick a game where Team A faced Team C, there is a 48% chance that they walk away thinking Team C is better than Team A. Thus, there is a 50% * 48% + 50% * 52% = 50% chance they stay with Team A in our initial state, a 50% * 52% = 26% chance they think Team B is better, and a 50% * 48% = 24% chance they think Team C is better.

Or, more succinctly:

$$ \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0.50 & 0.26 & 0.24\\\
0.24 & 0.48 & 0.28\\\
0.26 & 0.22 & 0.52 \end{bmatrix} = \begin{bmatrix} 0.5 & 0.26 & 0.24 \end{bmatrix} $$

So which team is best? Our transition matrix approaches an output vector of [0.33, 0.32, 0.35], indicating that Team C is likely the best team in our league, followed by Team A with Team B just a hair behind.

Conclusion#

By pairing simple modeling tools such as logistic regression and Markov chains together, LRMC becomes a powerful predictive algorithm: Kvam and Sokol found that LRMC consistently outperformed considerably more complicated algorithms in picking college basketball games¹. LRMC values are also fairly easily regressed to estimate values such as expected point spreads and win probabilities, so while one might not get a nice and tidy “This team would beat an average team by X points” value like SRS, LRMC yields useful values regardless. But ultimately, the beauty of LRMC results from its simplicity: with just four basic inputs (home team, away team, point differential, and court location), it performs well enough to be included as an important input for college basketball aggregate rankings such as 538’s NCAA March Madness projections¹².

Having established our understanding of the math behind LRMC, we can now implement an algorithmic ranking of LRMC in college football. You can find part two of this article here.