Having taught your students how to visualize matrix multiplication and why performing this bizarre dance of arithmetic could help make society a better place, the next logical step might be to raise a matrix to a power, say, to help your students forecast their dating prospects. Suppose at the start of orientation 80% of freshman are single, 10% are in a relationship, and 10% are in that ambiguous state that has been variously termed “it’s complicated”, “hookup buddies”, or “friends with benefits.” Each month those percentages change, according to a fixed set of probabilities: a fifth of the freshman who are single form a relationship, a quarter of those in the “it’s complicated” category become single, etc. We can organize those probabilities into a transition matrix, in which each entry gives the probability of a student transitioning from the relationship status described by their row to the relationship status described by their column:
Thus, after one month there is a 30% chance a single student will remain single, a 20% chance they will enter a relationship, and a 50% chance they will enter the “it’s complicated” state. Depending on how you structure the lesson, you might have the students estimate these transition probabilities in small groups—an exercise certain to capture their full attention (accompanied, perhaps, by a fair bit of giggling). Next, have students come up with an initial state vector describing the proportion of students in each state (relationship status) at the start of the year. For the above example: [.80 .10 .10] . What percentage of students will be in a relationship after a month?
Two months?
By the end of the year?
And viola, your students will find them themselves raising matrices to higher powers.
At this point, it’s rather natural for students to start exploring what happens after an even longer period of time (four years, for instance), and thus they may on their own (or with a little prompting from you) discover the concept of a steady-state vector—the vector that the system will always converge to over time no matter what initial state vector you start with. Push them to see if they can come up with an example of a transition matrix for which there is no steady-state vector: 
for instance. If they can explain why that matrix does not produce a steady-state vector, try to get them to formalize their reasons into a conjecture about the necessary and sufficient conditions for a matrix to have one. In addition, you might pause here to have your students consider what properties a matrix needs to be a transition matrix. In this example, I have written the probabilities as row vectors requiring you to multiply your initial state vector on the left, but I’ve seen them written as column vectors as well, and I actually think the latter (while less conventional) is easier to visualize.
Depending on the trajectory of the course, you might use this as an opportunity to preview the concept on an eigenvector or even the Perron–Frobenius theorem. When you do introduce these concepts later on, the dating matrix will provide a memorable and tangible example to circle back to. This would also be a good time to step back and ask your students to articulate the general characteristics of the problem we’ve set up—fixed probabilities, the outcome of each stage determined by the previous one, a finite number of states—and in doing so, define a Markov Chain. This approach feels more satisfying to me than simply handing your students a definition at the get-go, since it allows the definition to arise naturally from the problem posed and hence feel less arbitrary, but that’s a matter of preference. In either case, now would be a good time to reinforce the definition by asking students what other sorts of examples could be modeled well (though not perfectly) with a Markov Chain.
A good concluding exercise might be to ask students how they would improve this model. For instance, is it reasonable to assume that the transition matrix stays the same throughout the year, or are there more break-ups around Thanksgiving, more relationships forming around Valentine’s Day, and more students entering the “it’s complicated” category over spring break? How would they adjust the model and would it still qualify as a Markov chain? What are the trade-offs of making each stage of the chain represent a year rather than a month? You could also discuss what the Markov approach can and cannot tell you. Is it possible to estimate in this model how long a typical college relationship will last or how many break-ups a student can expect to experience over their four years? A major advantage here over other common mathematical problems about relationships is that this one does not presume heterosexual couples or even two genders (though a challenging and fascinating extension might be to consider a bisexual subset of the population for which same-sex and cross-sex relationships have different probabilities). In sum, examples about college dating are a great way to capture your students’ attention, particularly if you give them a chance to bring their own knowledge of the college dating scene to bear on the problem. On a psychological level, students should come away from the class associating the term “Markov chain” not only with a simple example they can easily to explain to their friends, but with a positive association between the new concept and the fun class they had. This is sure to make Markov Chains seem less scary and easier to remember in the future.
