Markov Models

Competency Goals

Markov Models

Last was mm06

Introduction

Many systems consist of a population of entities that transition between states over time. At any given time, for example, some people are in school, some have jobs, and some are unemployed. Over time, people get hired, fired, graduate, look for work, go back to school etc. The rates at which these different processes occur determine the number of people in each state. Whenever the next state depends only on where you are now, we can model the situation as a "Markov" process.

Here we will learn to recognize things that can be modeled as Markov processes, how to set up and "solve" a Markov model and what the limits of this approach are.

Entities and Populations

In stock and flow models we talked about the aggregate state of system: how much water is in reservoir, how many dollars in the bank, how many workers deployed on a task. With Markov models we are moving toward considering the behavior of the entities that compose the stocks, though still in the aggregate. We will, for example, look at a population of people and ask how many of them are, at a given time, healthy but susceptible, sick, or immune to a disease. We call these conditions "states."

markov-entities.png

States

A "state" is a condition that can be true of false of each item in a system population. In a Markov model the entities are generally of one kind only (in contrast, for example, with a stock and flow model in which we could have workers, products, raw materials, etc.).

markov-states.png

Stop and Think:

1. Consider the student body of a four year college in which students transition to the next class at the end of each year.

2. Or how about the "system" of all Facebook users and their relationship statuses?

3. Or how about a community drug treatment program whose clients transition between different categories of drug use/non-use?

NOTE: States must be mutually exclusive and exhaustive.

Transitions

In the systems we are interested in, at least some entities in some states have a chance to transition to other states over time. Healthy people can become sick, sick people can recover and become immune or they can die. First years become sophomores or drop out or, perhaps, repeat the year. A "transition" is just the change from one state to another.

markov.gif

Visualization

Building on imagery we have used before, we can picture each state as a circle. Entities are in one state at a time. As time unfolds they can move between states.

markov-visualization.png

Arrows show which transitions are allowed. In this example, all transitions are possible, including "self-transitions" which amount to staying in the same state. Each time the clock ticks, someone who is happy can become sad, so-so, or stay happy. Similarly for the other two states.

Stop and Think:

1. Draw a similar diagram for college student system as described above. Assume we have four states for the years plus an "alum" state and a "drop out" state.

2. In the model you just drew, what state(s) would you expect to be "fuller" and "emptier" over time and why?

3. What about a model of a population subject to a flu outbreak where individuals can be uninfected, currently infected, or immune after having been infected.

The last detail we need to add to the diagram is to label the transition probabilities. Each arrow is labeled by the probability of a transition FROM the origin state TO the destination state.

NOTE that the numbers on all the arrows LEAVING each state have to sum to 1.0.

An Example: Rehabilitation Center

The Happy Valley Rehabilitation Center was set up to deal with drug problems in a community where everyone has a drug problem. Community members are in one of three situations: they are currently in treatment (I), they have been rehabilitated (R) or they have escaped from the facility or not yet been identified (that is, they are free but still have a problem).

In any period, there is a 10 percent probability that an inmate will be judged rehabilitated, in which case s/he will be released at the beginning of the following period. There is also a 5 percent chance that an inmate will escape during each period. Rehabilitated addicts have a 20 percent chance of relapsing in each period and returning to treatment; escapees have a 10 percent chance of being recaptured each period. Both recidivists and recaptured escapees are returned to the facility.

Introducing the transition matrix

A matrix is a table of numbers arranged in rows and columns. For example:

0.85 0.1 0.05
0.2 0.8 0.0
0.1 0.0 0.9

We would refer to this as a 3 by 3 matrix. If we add a row

0.85 0.1 0.05
0.2 0.8 0.0
0.1 0.0 0.9
0.1 0.8 0.1

we would call it a 4 by 3 matrix. The nomenclature is "number of rows by number of columns."

In the case of a Markov model, we will use a matrix like this (it's still a 3x3 matrix, we have simply added row and column headers to indicate the function of the rows and columns:

To I To R To E
From I 0.85 0.1 0.05
From R 0.2 0.8 0.0
From E 0.1 0.0 0.9

which we would read like this:

  • In each time period, there is an 85% likelihood that a person IN treatment will remain IN treatment
  • In each time period, there is a 10% likelihood that a person IN treatment will become REHABILITATED.
  • In each time period, there is a 5% likelihood that a person IN treatment will become ESCAPE.
  • In each time period, there is a 20% likelihood that a REHABILITATED person will end up back IN treatment.
  • In each time period, there is a 20% likelihood that a REHABILITATED person will remain so.
  • In each time period, there is a 10% likelihood that an ESCAPEE will be caught and put back IN treatment.
  • In each time period, there is a 90% likelihood that an ESCAPEE will remain free.
  • Those who are REHABILITATED never turn into ESCAPEES and vice versa.

Don't continue until you feel confident you understand the layout of the transition matrix.

Assume for now that the system begins with 1000 individuals in treatment.

Let's make sure we remember what the rows, columns, and elements of this matrix represent via color coding the text:

markov-drugs-transition-matrix-represents.jpg

To calculate the populations of each of the states at the next time period, we multiply current state populations by all the relevant transition rates. This gets a little messy, but we can handle it if we proceed systematically:

markov-drugs-equations.jpg

We call the three numbers describing the populations of the states at the start P1 - the condition of the system at time 1. What we want to do is calculate P2, the system at time 2. We do this by multiplying P1 by the transition matrix.

Each of these equations is an example of the SUMPRODUCT function that we saw when we set up constraint equations in linear programming.

Together these equations represent an operation we call "matrix multiplication." What we are doing here is multiplying the three-tuple that represents the current populations of the three states times three sets of transition rates, one for each destination state. This amounts to multiplying each column of the transition matrix times the three-tuple of current population numbers.

markov-drugs-mmult-1.jpg

The yellow triple times the red column gives the first element of the result (in orange). The yellow times the blue gives the green. The yellow times the violet (3rd) column gives the olive green element of the result.

markov-drugs-mmult-2.jpg

Practice Sketch the transition matrix for this state diagram

markov-foreclosure.gif

References

Stokey & Zeckhauser, ch. 7, "Markov Models," pp. 98-107.
Stokey & Zeckhauser, ch. 7, "Markov Models," pp.104-114.

http://www.stat.cmu.edu/~fienberg/Stat36-835/SingerSpilerman-AJS-1976.pdf

Burton Singer; Seymour Spilerman. 1976. "The Representation of Social Processes by Markov Models," The American Journal of Sociology, Vol. 82, No. 1. (Jul., 1976), pp. 1-54.
Kemeny, John G. and J. Laurie Snell. 1962. Mathematical Models in the Social Sciences. Boston: Ginn and Company. (Questia)

KEMENY, JOHN G. & J. LAURIE SNELL Finite Markov Chains.
Princeton NJ: D. Van Nostrand Company, 1963.
Wikipedia. Markov Chains

Lab

Included page "ppol225:markov-lab-2012" does not exist (create it now)

Problems

Q151. A cinema has a marquee with lots and lots of light bulbs. In any given week 1% of the light bulbs burn out. Unfortunately, between being busy and being sloppy, replacement is a little bit sporadic. Of all the bulbs that are burnt out, about 95% get replaced each week. Draw the state diagram for this system.


Q152. Translate this description into a state diagram. A population consists of people who play it safe, and daredevils. From year to year, most (97%) safe-players stay that way, but 2% turn into daredevils. About 1% of the safe-players die each year. By contrast, 10% of daredevils die each year and another 10%, seeing that, switch to playing it safe. All the other daredevils stick with the program.

Label each of the states in as transient or absorbing.


Q153. A criminologist and an activist decide to collaborate on a project designed to reduce prison population. In the spirit of starting simple, they identify 4 states in which people can find themselves: never imprisoned; incarcerated; on parole; post-parole. The period of time in their analysis will be one year. Suppose 70% of the population has never been incarcerated. Each year 2% of these people are imprisoned. Of those currently incarcerated, 20% are released each year onto parole. Average parole is 5 years so that a person on parole has a 20% chance of finishing parole. Those on parole have a 10% chance of finding themselves back in prison in any given year. Individuals who are post parole have a 4% chance of returning to prison in any given year. Draw a state diagram and matrix representing this information.


Q154. Suppose a given housing market has a 10% turnover rate each year. How many houses will typically be in the first, second, third, etc. year of their mortgage at any given time? Assume 10 year mortgages to keep things simple. Draw the diagram that would be the first step in solving this problem.


Q155. Suppose 25% of the mortgages written in the first years of this century were subprime (meaning the borrowers were not very credit-worthy) and all were 5 year adjustable such that after the fifth year the monthly payments would go way up. In the market in question there is approximately 5% turnover housing each year. The housing stock in the market consists of one million units. Research has shown that 33 1/3% of subprime adjustable mortgages go into default under current conditions when they go past their five year mark (and these conditions are expected to continue for some time) when they adjust.


Q156. A state corrections system has established a new drug treatment facility for first offenders. The center has a capacity of 1000.

Inmates may leave the facility in either of two ways. In any period, there is a 10 percent probability that an inmate will be judged rehabilitated, in which case s/he will be released at the beginning of the following period.. There is also a 5 percent chance that an inmate will escape during each period. Rehabilitated addicts have a 20 percent chance of relapsing in each period; escapees have a 10 percent chance of being recaptured each period. Both recidivists and recaptured escapees are returned to the facility and have priority over new offenders.

Questions

If it operates at full capacity, how many of the original inmates will be resident at the facility 10 periods later?
How many new offenders can be admitted during each of the next 2 periods?
What happens if we modify the model to allow for a small possibility of death or a change in the probability of relapse?


Q157. Sketch the transition matrix that corresponds to the following diagram

p0157-markov-01.jpg

Q158. Suppose the following statements are true about the local housing market.

  1. On a month to month basis, 90% of mortgage payments are on time, 10% are late or missed.
  2. Of all the late/missed payments, 25% are back on track the following month. 65% are late again. 10% go into default.
  3. Of all mortgages in default in a given month, 20% have a work-out and return to good standing. 70% remain in default and 10% move into foreclosure.
  4. Of all houses in foreclosure each month, the banks manage to get 20% back on the market and resold.

Draw the transition diagram and write out the transition matrix.


Q159. Implement the model from problem 158 using this Excel spreadsheet.


Q187. The diagram below represents a candidate's shifting weekly position on abortion. Treating this as a Markov model (where each transition is independent of previous sequence of states), show us what the transition matrix would look like. What do we call the state that would represent a candidate's final position on an issue? Using this diagram, what prediction can you make about what this candidate's position would be if he were to be elected?

markov-candidate-position.png

Q328. Have a look at this recent release from Bureau of Labor Statistics (BLS). The data separates those without a job into unemployed but "in the labor force" and "marginally attached to the labor force" and a subset of these called "discouraged" - the former would like to work but have not looked in the last four weeks and so are not counted as unemployed. The latter are not actively looking for work having given up on the idea that its possible to find. These groups are not included in the denominator when the unemployment rate is calculated. The simple version of the unemployment rate is, then,

(1)
\begin{align} UR = \frac {Unemployed} {Employed + Unemployed} \end{align}

Some recent op-eds have counseled caution about optimism that the overall unemployment rate has been going down because it might reflect growth in the number of people no longer looking for work. We'll think about that with a Markov model. We'll simplify the states a worker can be in:

  • employed (E)
  • short term unemployed - 14 weeks or less (US)
  • long term unemployed - over 14 weeks (LS)
  • Marginally attached to the labor force - no longer looking for a job (MALF)

Let's construct a simplified Markov model of unemployment based on transition rates shown here:

markov_transition_table.png

If the unemployment rate is calculated as the ratio of those who are short term unemployed (US) plus those who are long term unemployed (UL) to the total labor force (E + US + UL), how would things evolve over the next twelve months if the starting numbers are these:

markov_starting_point.png

What will the unemployment rate be? Even if it is agreed that getting unemployment to near 6% is a policy goal, are there reasons the results might not be a cause for celebration?

Create a chart showing changes over the next 12 months. Suggestion: plot total employment (E) on secondary axis since it's such a large number. In the alternative, put it on a separate chart.

Excel worksheet here