Real-world Markov chains

Question

I will give a talk to undergrad students about Markov chains. I would like to present several concrete real-world examples. However, I am not good with coming up with them beyond drunk man taking steps on a line, gambler's ruin, perhaps some urn problems.

I would like to have more. I would favour eye-catching, curious, prosaic ones. Specially if there has been a paper about it. For example, I remember reading years back a paper, based on actual data, about the probability that a football player will change teams, or something like that.

Answer 1

The Markov Chains I work with are usually called in the epidemiological and in the chemistry literature "compartmental models". The most famous (from an epidemiological viewpoint) is the SIR model for infectious diseases.

SIR model

The main idea is that individuals can be classified into three groups: Susceptible (people that can get the disease), Infected (people that have the disease and are contagious), and Removed.

The main idea is that almost all individuals start Susceptible (they can catch the disease) with a handful of Infected. Considering discrete time (such as days) some infected individuals will either get better or die (hence becoming Removed) and some Susceptible will become Infected. The interesting part is how interactions between the compartments give rise to different models. Also, there are a lot (and I mean a lot) of infectious disease models that use this idea and add additional compartments (boxes in the picture or states of your chain). For example you can divide the infected into symptomatic and asymptomatic, you can divide the susceptible into vaccinated and unvaccinated, etc. A more complete account on this models can be found in Mathematical Epidemiology by Brauer.

Here is a plot of what the model looks like (the simulation is done in R as explained in this blogpost)

Chronic disease models

Chronic disease models do not usually have interaction between compartments (think diabetes which is usually not contagious).The main idea is that everyone is Healthy, then gets the disease and finally dies. This models are usually done to evaluate policies (what would happen if we give medicine to everyone? or what would happen if we improve everybody's diet?). Again you can add more compartments by differentiating sexes, or age categories, body mass index, etc. You can see the paper State-Transition Modeling: A Report of the ISPOR-SMDM Modeling Good Research Practices Task Force-3

Connections between SIR and physics

The SIR model and most infectious-disease models are related to compartmental models in physics. The associated physics models are called interactive particle systems and are quite an interesting area of research. From a physics standpoint you can read van Kampen or Gardner (which might be closer to an advanced undergraduate). A book on how the connections are made is Quantitative Sociodynamics and a graduate level (classical) book on this systems is Interactive Particle Systems by Liggett.

Answer 2

I'm not sure if you consider the board game Monopoly as a real-world example, but it is often used to explain Markov Chains to laypeople. Ian Stewart has a couple of Mathematical Recreations articles about it in Scientific American.

The first (in the April 1996 issue) has the title "How Fair is Monopoly?" (A copy it can be found here.)

The second (in the October 1996 issue) has the title "Monopoly Revisited" (A copy of it can be found here.)

Answer 3

A bit late to the party, but PageRank is partially built off of this notion (if I'm on page x, what is the probability I go to page y? What does this say about the importance of pages?) There's a paper by Larry Page Link here about it.

There's also quite a bit of work on things like context-based autocompletion (using Markov chains with smoothing) as well as other predictive works.

In the world of Numerical Linear Algebra, you could view eigenvalue computations (especially sparse eigenvalue computation) using power iteration as a Markov-like process.

Answer 4

1. Hydrology: classic area, very easily intuitively to think of water filling, draining areas (but with variation in the input). It is very graphical and physical. This is the classic example!

2. Markov chains in economics. Little less physically intuitive, but huge area in terms of relevance to Mankind. And for smart students and/or world aware ones, won't be that bad (not like some weird physics, chem problem).

3. Climate data (tree rings, etc.). The math is a little trickier and examples a little less pure, but may be of relevance to your students.