NFL Markov: 2 of n (expectation values of a basic markov chain)

In part 1 I talked about a simple random walk in 1-dimension, where the states all the way to the left and all the way to the right are sinks (or roach motels). The next step from that is to ask what is the expectation value associated with each state? I mentioned that we could think of the state s_{+2} as scoring a touchdown (+6 or +7 or +8 points) and s_{-2} as giving up a safety (-2 points), but to illustrate the problem, it is convenient to assume that landing at location +2 is worth +1 point and at location -2, -1 point.

As a concrete example, let me take p=0.6 and ask what the expectation values are, given that I start in state s_{-1}, s_{0}, or s_{+1}. Iterating the transition matrix to convergence, as I did in part 1, I get,

T^{\infty} =   \left(  \begin{array}{ccccc}   1. & 0.584615 & 0.307692 & 0.123077 & 0 \\   0 & 0 & 0 & 0 & 0 \\   0 & 0 & 0 & 0 & 0 \\   0 & 0 & 0 & 0 & 0 \\   0 & 0.415385 & 0.692308 & 0.876923 & 1. \\  \end{array}  \right)

This says that if I start at state s_0, I end in state s_{-2} with probability 0.308 and s_{+2} with probability 0.692. If these are worth -1 and +1 points, respectively, then the expectation value for points will be e_{0} = 0.692-0.308 = 0.384. In a similar way I can see that the expectation values for states s_{-1} and s_{+1} are e_{-1} = 0.415-0.585 = -0.169 and 0.877-0.123 = 0.754, respectively. I will use p=0.6 as sort of a test case and refer back to these values later. So this gives me the answer using the first method.

The question I want to address now is, other than iterating to convergence, how do we go from the transition matrix (which is relatively easy to code up for football) to the expectation value (which is what we really want to know)?
Logically, the expectation value, e_{0}, when starting from the state s_{0}, should be,

e_0 = e_{-2} p_{-2,0} + e_{-1} p_{-1,0} + e_{0} p_{0,0} + e_{+1} p_{+1,0} + e_{+2} p_{+2,0}

In words, its the expectation value of the subsequent state in the chain (for example, e_{-1}), multiplied by the probability to transition to that state (for example p_{-1, 0}). Inspection shows that this says (using Einstein notation for matrix/vector multiplication),

e_{i} = e_{k} T_{k,i}

or, in vector notation,

\vec{e} = \vec {e} ~\vec{T},

or

\vec{e} ~(\vec{T} - \vec{1}) = 0, where \vec{1} is the identity matrix.

For the particular transition matrix we are discussing, we have,

\left(  \begin{array}{c}  e_{-2} \\  e_{-1} \\  e_{0} \\  e_{+1} \\  e_{+2}  \end{array}  \right) =   \left(  \begin{array}{c}  e_{-2} \\  e_{-1} \\  e_{0} \\  e_{+1} \\  e_{+2}  \end{array}  \right)  \times   \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)

Because e_{m} T_{m,n} = T_{m,n} e_{m} = T'_{n,m} e_{m}, where T' is the transpose of T, I can also write this as,

\vec{e} =   \left(  \begin{array}{ccccc}   1 & 0 & 0 & 0 & 0 \\   1-p & 0 & p & 0 & 0 \\   0 & 1-p & 0 & p & 0 \\   0 & 0 & 1-p & 0 & p \\   0 & 0 & 0 & 0 & 1 \\  \end{array}  \right) \times   \vec{e}

This way, with the matrix multiplying the vector from the left, is the more common way to see a set of equations represented, and some code for numerically solving such an equation expect this convention. The values e_{-2} and e_{+2}, however, aren’t really variables, i.e. quantities that need to take on particular values for the set of equations to hold; they are parameters, such that their values are arbitrary, and, once chosen, impact the expectation values for the non-sink states.

Let me denote by (s, t) states that are sinks, and (n,m) states that are NOT sinks. What I really want to know are the set of values e_{n}, i.e. the expectation values for states that are not sinks. So I can write,

e_{n} = e_{s} T_{s,n} + e_{m} T_{m,n}

Rearranging this equation gives,

e_{m} ~(T_{m,n} - \delta_{m,n}) = - e_{s} T_{s,n}

or in vector notation,

\vec{e}^{n} ~(\vec{T}^{n} - \vec{1}) = - \vec{e}^{s} ~\vec{T}^{s}

Taking the transpose of both sides I get,

(\vec{T}^{n} - \vec{1})' ~\vec{e}^{n}  = - \vec{T'}^{s} ~\vec{e}^{s}

Note that the superscripts here denote sink or non-sink and do not denote exponentiation. Also, let S denote the number of sinks and N the number of non-sinks; then the dimensions of e^{n}, e^{s}, T'^{n}, and T'^{s} are
N \times 1, S \times 1, N \times N, and N \times S, respectively.

For the particular problem we’ve been discussing, this can be expanded as,

\left(  \begin{array}{ccc}   0 & p & 0 \\   1-p & 0 & p \\   0 & 1-p & 0 \\  \end{array}  \right) \times  \left(  \begin{array}{c}   e_{-1} \\   e_{0} \\   e_{+1} \\  \end{array}  \right) =   - \left(  \begin{array}{cc}   1-p & 0 \\   0 & 0 \\   0 & p \\  \end{array}  \right) \times   \left(  \begin{array}{c}   e_{-2} \\   e_{+2} \\  \end{array}  \right)

or

\left(  \begin{array}{ccc}   0 & p & 0 \\   1-p & 0 & p \\   0 & 1-p & 0 \\  \end{array}  \right) \times  \left(  \begin{array}{c}   e_{-1} \\   e_{0} \\   e_{+1} \\  \end{array}  \right) =   -\left(  \begin{array}{c}   e_{-2} (1-p) \\   0 \\   e_{+1} p \\  \end{array}  \right)

Note that once I choose values for e_{-2} and e_{+2}, the the right hand side is just a constant vector.

\left(  \begin{array}{ccc}   0 & p & 0 \\   1-p & 0 & p \\   0 & 1-p & 0 \\  \end{array}  \right) \times  \left(  \begin{array}{c}   e_{-1} \\   e_{0} \\   e_{+1} \\  \end{array}  \right) =   \left(  \begin{array}{c}   (1-p) \\   0 \\   -p \\  \end{array}  \right)

The formal solution is,

((\vec{T}^{n}-\vec{1})')^{-1} \cdot (- \vec{T}^{s} \cdot \vec{e}^{s})

=  \left(  \begin{array}{c}   \frac{-{e_{-2}} p^3+{e_{+2}} p^3+2 {e_{-2}} p^2-2 {e_{-2}} p+{e_{-2}}}{2 p^2-2 p+1} \\   \frac{{e_{-2}} (p-1)^2+{e_{+2}} p^2}{2 p^2-2 p+1} \\   \frac{{e_{+2}} p \left(p^2-p+1\right)-{e_{-2}} (p-1)^3}{2 p^2-2 p+1} \\  \end{array}  \right)

so if I set e_{-2} = -1 and e_{+2} = +1, then I get,

\left(  \begin{array}{c}   \frac{2 p^3-2 p^2+2 p-1}{2 p^2-2 p+1} \\   \frac{p^2-(p-1)^2}{2 p^2-2 p+1} \\   \frac{(p-1)^3+p \left(p^2-p+1\right)}{2 p^2-2 p+1} \\  \end{array}  \right)

and then if I further set p = 0.6, then I get,

\left(  \begin{array}{c}   -0.169231 \\   0.384615 \\   0.753846 \\  \end{array}  \right)

which is exactly what I got from iterating the transition matrix until it converges and then reading off the columns. One last thing to note, is that the equation,

\vec{e} \cdot \vec{T} = \vec{e}

from above implies that (if I multiply by T from the right on both sides),

\vec{e} \cdot \vec{T}^2 = \vec{e} \cdot \vec{T},

but,

\vec{e} \cdot \vec{T} = \vec{e}, so

\vec{e} \cdot \vec{T}^{2} = \vec{e},

and it follows that,

\vec{e} \cdot \vec{T}^{\infty} = \vec{e},

which is exactly what we got by iterating the transition matrix to convergence.

Advertisements

One thought on “NFL Markov: 2 of n (expectation values of a basic markov chain)

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