NFL Markov: 3 of n (accounting for turnovers)

In parts 1 and 2 I described a problem that could be modeled as a Markov chain and that roughly corresponds to the scoring of touchdowns and safetys. Now I will discuss introducing the concept of a turnover. In the orginal problem, the walker had a probability to move right of p, and left of (1-p). I will now model the case where a “turnover” occurs with probability a. This reverses right and left, so that the walker moves left with probability p and right with probability (1-p). The most straight-forward way to model this augmented problem is to double the size of the number of possible states, by including a flag that tells you whether the walker is moving “right” (as in the original problem), or left (after reversing directions). It is convenient to refer to a state as s^{y}_{x}, where x refers to location and y to direction. As a concrete example, the state 1 position over from the left sink, and moving to the right can be denoted as s^{+}_{-1}, the state one step over from the left sink and moving to the left as s^{-}_{-1}. Additionally, the values of the sinks get transposed, so that e^{+}_{+2} = -e^{-}_{-2} (think a touchdown scored in the + direction is +7, a touchdown in the – direction is -7) and e^{+}_{-2} = -e^{-}_{+2} (a safety given up in the + direction is worth -2, in the – direction +2). Combining the effects of stepping and turning over, results in a transition matrix that looks like this,

\left(  \begin{array}{cccccccccc}  1 & (1-a) (1-p) & 0 & 0 & 0 & 0 & a (1-p) & 0 & 0 & 0 \\  0 & 0 & (1-a) (1-p) & 0 & 0 & 0 & 0 & a (1-p) & 0 & 0 \\  0 & (1-a) p & 0 & (1-a) (1-p) & 0 & 0 & a p & 0 & a (1-p) & 0 \\  0 & 0 & (1-a) p & 0 & 0 & 0 & 0 & a p & 0 & 0 \\  0 & 0 & 0 & (1-a) p & 1 & 0 & 0 & 0 & a p & 0 \\  0 & a p & 0 & 0 & 0 & 1 & (1-a) p & 0 & 0 & 0 \\  0 & 0 & a p & 0 & 0 & 0 & 0 & (1-a) p & 0 & 0 \\  0 & a (1-p) & 0 & a p & 0 & 0 & (1-a) (1-p) & 0 & (1-a) p & 0 \\  0 & 0 & a (1-p) & 0 & 0 & 0 & 0 & (1-a) (1-p) & 0 & 0 \\  0 & 0 & 0 & a (1-p) & 0 & 0 & 0 & 0 & (1-a) (1-p) & 1 \\  \end{array}  \right)

So (as an aside), for example, the walker moves from state s^{+}_{-1} (the 2nd column) to
the state s^{+}_{-2} with probability (1-a)(1-p),
the state s^{+}_{0} with probability (1-a) p,
the state s^{-}_{-2} with probability a p,
the state s^{-}_{-2} with probability a (1-p).
Note that when a=0, “moving to the right” (the top-left 5×5) decouples from “moving to the left” (the bottom-right 5×5). Specifically,

\left(  \begin{array}{cccccccccc}  1 & 1-p & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\  0 & 0 & 1-p & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\  0 & p & 0 & 1-p & 0 & 0 & 0 & 0 & 0 & 0 \\  0 & 0 & p & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\  0 & 0 & 0 & p & 1 & 0 & 0 & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & 0 & 1 & p & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & 0 \\  0 & 0 & 0 & 0 & 0 & 0 & 1-p & 0 & p & 0 \\  0 & 0 & 0 & 0 & 0 & 0 & 0 & 1-p & 0 & 0 \\  0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1-p & 1 \\  \end{array}  \right)

With the formulation described above, everything I talked about in parts 1 and 2 carries over, i.e., the expectation values can be determined by iterating the transition matrix until it converges, or by separating out the sink and non-sink states and explicitly solving the system of equations for the non-sink expectation values. If I take p=1-p=0.5, and a=0, the solution is,

\left(  \begin{array}{c}  e^{+}_{-1} \\  e^{+}_{0} \\  e^{+}_{+1} \\  e^{-}_{-1} \\  e^{-}_{0} \\  e^{-}_{+1} \\  \end{array}  \right) =  \left(  \begin{array}{c}  -0.5 \\  0 \\  0.5 \\  -0.5 \\  0 \\  0.5 \\  \end{array}  \right)

If I take p=0.6, and a=0, the solution is,

\left(  \begin{array}{c}  e^{+}_{-1} \\  e^{+}_{0} \\  e^{+}_{+1} \\  e^{-}_{-1} \\  e^{-}_{0} \\  e^{-}_{+1} \\  \end{array}  \right) =  \left(  \begin{array}{c}  -0.169231 \\  0.384615 \\  0.753846 \\  -0.753846 \\  -0.384615 \\  0.169231 \\  \end{array}  \right)

These make sense based on the results from parts 1 and 2. If I take p=0.5 and vary the value of a, then the result is as shown in Fig. \ref{fignm_05}. In other words, it makes no difference if I reverse direction or not. This makes sense because either way I am moving left or right with equal probability, and moreover, I have defined the points for landing at location +2 (a “touchdown”) to be equal to the points for landing in location -2 (a “safety”).

If I set p=0.6 and vary a, the results are as shown in Fig. \ref{fignm_06}. And, if I set p=0.9 and vary a, the results are as in Fig. \ref{fignm_09}.

As a test case to investigate in more detail, let me choose p=0.6, a=0.1. In that case the solution is,

\left(  \begin{array}{c}  e^{+}_{-1} \\  e^{+}_{0} \\  e^{+}_{+1} \\  e^{-}_{-1} \\  e^{-}_{0} \\  e^{-}_{+1} \\  \end{array}  \right) =  \left(  \begin{array}{c}  -0.316552 \\  0.206897 \\  0.642069 \\  -0.642069 \\  -0.206897 \\  0.316552 \\  \end{array}  \right)

An important point to note is that the solution has a lot of symmetry. In other words, if you flip the direction you’re moving and also flip the starting point, then the expectation value is equal in magnitude and opposite in sign. So, for example, starting from s_{-1} and moving right is the negative of starting from s_{+1} and moving left. I can write this more concisely as, e^{-}_{i} = -e^{+}_{2m-i}, where m stands for “middle”. In this case m=0, and

\begin{array}{c}  e^{-}_{-1} = - e^{+}_{+1} \\  e^{-}_{0} = - e^{+}_{0} \\  e^{-}_{+1} = - e^{+}_{-1} \\  \end{array}

Moreover, the transition probabilities are symmetric if we flip directions and flip position around the middle, that is, T^{-,-}_{i,j} = T^{+,+}_{2 m-i,2 m - j }. The main point of this section is that we can use the symmetry of the expectation values and transition probabilities to avoid the doubling of the state space. To repeat the general equation for expectation value in terms of transition probabilities (Einstein notation),

e^{+}_{j} = e^{+}_{i} T^{+}_{i,j}  = e^{+}_{i} T^{+,+}_{i,j} + e^{-}_{i} T^{-,+}_{i,j}

So far this is just an identity, where I have split up T into the parts where no turnover occurs (the T^{+}_{i} terms) and the parts where a turnover did occur (the T^{-}_{i} terms). With the assumption that a “turnover” occurs with probability a, and the relations described above, I can write,

e^{+}_{j} = (1-a) e^{+}_{i} T^{+,+}_{i,j} - a e^{+}_{2 m-i} T^{+,+}_{2 m -1, 2 m - j}

So if I generate a matrix, U, with elements U_{i,j} = (1-a) T_{i,j} - a T_{i, 2m - j}, then I can write the vector equation \vec{e} = \vec{e} \vec{U}. Everything discussed in part 2 regarding solving this then carries over. As a concrete example, here is what the 5 \times 5 matrix U looks like for this problem,

\left(  \begin{array}{ccccc}  1-a & (1-a) (1-p) & 0 & -a (1-p) & -a \\  0 & 0 & (1-a) (1-p)-a (1-p) & 0 & 0 \\  0 & (1-a) p-a (1-p) & 0 & (1-a) (1-p)-a p & 0 \\  0 & 0 & (1-a) p-a p & 0 & 0 \\  -a & -a p & 0 & (1-a) p & 1-a \\  \end{array}  \right)

Finally, since this equation is identical to the one in part 2, with U replacing T, the transition matrix without considering turnovers, it follows that a 2nd way to determine the expectation values is to iterate U until it converges, and read off the columns. In the football application, where the transition matrix has (depending on the parameterization) about 8000 elements, iterating may be a better choice, computationally. Another important thing to note here is that I’ve looked at a restricted case where a turnover allows occured at the same location from which the walker started. So the relation in this case is
e^{-}_{i} T^{-,+}_{i,j} = e^{+}_{i} T^{+,+}_{i,2 m -j},
more generally it is,
e^{-}_{i} T^{-,+}_{i,j} = e^{+}_{i} T^{+,+}_{i,j'}, where j' is the state that the turnover brounght you to.
As a concrete example, consider having 1st and 10 from the 20. Say there is a probability \eta to throw an interception, with the ball ending up 20 yards down field, at the 40. Then the part of the transition matrix encoding that will be
- e_{1-10-60} T^{-,+}_{1-10-60,1-10-20}.

markovChains_05

markovChains_06

markovChains_09

Advertisements

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 )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s