### NFL Markov: 1 of n (a basic markov chain)

This is the first in a series of posts describing my work on a Markov chain tool to analyze football. The code is available from github,
https://github.com/bdilday/nflMarkov

Before talking about football, I want to talk about a less complicated problem. It is probably worth saying at this point that I am not a mathematician, nor a computer scientist. What I am is an astronomer and astrophysicist, so obviously I know some math and some programming, but at the same time I’m not necessarily an expert on Markov chains. As with most things, what I know is what I’ve picked up in order to work on research problems, so what I have to say may be obvious, or naive. In any case, writing this out is in large part for my own sake, to help myself clarify my thoughts on the problem; as well as to hopefully be useful people who read this without much knowledge of Markov chains coming in.

The first simple problem I want to talk about, which is pretty much the simplest non-trivial Markov chain problem I can think of, is this; imagine a random walk where there are 5 possible states which I will call $s_{-2}, s_{-1}, s_{0}, s_{+1}, s_{+2}$. In each step of the process, the walker can move one step to the right, which happens with probability p, or one step to the left, which happens with probability q=1-p. If the walker lands at position +2 or -2 they stay there. Here is what the transition matrix looks like,

$T_{ij} = \left( \begin{array}{ccccc} 1 & 1-p & 0 & 0 & 0 \\ 0 & 0 & 1-p & 0 & 0 \\ 0 & p & 0 & 1-p & 0 \\ 0 & 0 & p & 0 & 0 \\ 0 & 0 & 0 & p & 1 \\ \end{array} \right)$

To be clear, this is the probability to transition TO the state i, FROM the state j. If I iterate once, i.e., compute $T^2 = T_{ik}T_{kj}$ (this is the Einstein notation for maytrix multiplication), I get,

$T^{2} = \left( \begin{array}{ccccc} 1 & 1-p & (1-p)^2 & 0 & 0 \\ 0 & (1-p) p & 0 & (1-p)^2 & 0 \\ 0 & 0 & 2 (1-p) p & 0 & 0 \\ 0 & p^2 & 0 & (1-p) p & 0 \\ 0 & 0 & p^2 & p & 1 \\ \end{array} \right)$

Two times,

$T^{3} = \left( \begin{array}{ccccc} 1 & p (1-p)^2-p+1 & (1-p)^2 & (1-p)^3 & 0 \\ 0 & 0 & 2 (1-p)^2 p & 0 & 0 \\ 0 & 2 (1-p) p^2 & 0 & 2 (1-p)^2 p & 0 \\ 0 & 0 & 2 (1-p) p^2 & 0 & 0 \\ 0 & p^3 & p^2 & (1-p) p^2+p & 1 \\ \end{array} \right)$

Three times,

$T^{4} = \left( \begin{array}{ccccc} 1 & p (1-p)^2-p+1 & p (1-p)^3+\left(p (1-p)^2-p+1\right) (1-p) & (1-p)^3 & 0 \\ 0 & 2 (1-p)^2 p^2 & 0 & 2 (1-p)^3 p & 0 \\ 0 & 0 & 4 (1-p)^2 p^2 & 0 & 0 \\ 0 & 2 (1-p) p^3 & 0 & 2 (1-p)^2 p^2 & 0 \\ 0 & p^3 & (1-p) p^3+\left((1-p) p^2+p\right) p & (1-p) p^2+p & 1 \\ \end{array} \right)$

You can stare at these and start to see the structure of how you move from state to state as you iterate the Markov chain, but I think the main usefulness is just to illustrate that repeated applications of the transition matrix mix things up in a deterministic and straight-forward (if tedious to enumerate) way. For a simple problem like this you could probably even come up with a closed form solution.

Now let me put in some numbers and keep iterating the transition matrix until it converges. lets try p=1-p=0.5. If I iterate 100 times, and round to zero values less than $1 \times 10^{-6}$, I get,

$T^{100} \approx T^{\infty} = \left( \begin{array}{ccccc} 1. & 0.75 & 0.5 & 0.25 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0.25 & 0.5 & 0.75 & 1. \\ \end{array} \right)$

So what exactly does this mean? It means if I start in the state $s_{-2}$ (all the way to the left), I end in the state $s_{-2}$ with probability 1. If I start in the state $s_{-1}$ I end in the state $s_{-2}$ with probability 0.75 and $s_{+2}$ with probability 0.25. If I start in the state $s_0$, I end in the state $s_{-2}$ with probability 0.5 and $s_{+2}$ with probability 0.5. In other words, reading down each column (j) tells me the probability to end in the state (i) after 100 (which may as well be infinity) transitions.

If I use p=0.501 instead, this is what I get,

$\left( \begin{array}{ccccc} 1. & 0.748498 & 0.498 & 0.248502 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0.251502 & 0.502 & 0.751498 & 1. \\ \end{array} \right)$

If I use p=0.99, I get,

$\left( \begin{array}{ccccc} 1. & 0.010101 & 0.00010202 & 1.02 \times 10^{-6} & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0.989899 & 0.999898 & 0.999999 & 1. \\ \end{array} \right)$

This first post just shows that you can set up a Markov chain that models a random walk and make the states at the end “sinks” (or roach motels; once you enter, you never leave), and after iterating enough times, you will always end up in one of the sinks. In the football application, the sinks are going to be scoring events. So we can imagine that making it all the way to the right is like scoring a touchdown, all the way to the left, like giving up a safety. In the next part I’ll look at the expectation values associated with such a Markov chain.