Wednesday, February 6, 2008

Wednesday Math, Vol. 14: Markov chains

Let's say you are having a party and 30 people are traipsing around your house. A pattern emerges that traffic is milling about in the following way. Every 10 minutes, 20% of the people who were in the kitchen go to the living room, while 10% of the people in the living room head to the kitchen. (Yes, I know, there should be some people leaving to go to the bathroom, and people should be coming and going from the party itself, but let's stick with this simple model for now.)

Looking at the numbers, you might think the kitchen is developing a slow leak and will eventually be empty, but that's not the way it works. Here are the equations, where L is the number of people in the living room and K is the number of people in the kitchen.

20% K + 90% L = L
80% K + 10% L = K

Both equations, once simplified, tell us that 20% K = 10% L, which can be re-written to say that twice the number of people in the kitchen is equal to the number of people in the living room, or written as an equation 2K = L. Since we already stipulated that there are 30 people at the party, this system will reach an equilibrium state when there are 20 people in the living room and 10 in the kitchen, and every 10 minutes, two people in the living room (10% of 20) will head to the kitchen and two people in the kitchen (20% of 10) will leave and go to the living room.

This is a very orderly and predictable party you have thrown. You must have invited a lot of Germans.

The math done here is known as a Markov chain. It is used for problems like this dealing with the flow of stuff, whether people in a party or a shopping mall or molecules flowing in an engine. You can have more than two rooms, but the rule is that 100% of the stuff in every room has to be accounted for, where it will be when the next time interval occurs. Sometimes the equilibrium state is nice and simple like this, and sometimes there will be more than one equilibrium state, and the system will bounce back and forth between two or more situations. The field of math being used is linear algebra and the equilibrium states are called eigenvectors, which is a mishmash of German and English. The mathematicians who first worked on perfecting linear algebra were both German and English, and someone either didn't know to translate "eigen" into "characteristic" when going from German to English, or maybe they just wanted to save time typing. Either way, eigenvector and eigenvalue are legitimate words now. Even my spell checking software likes them.

Fun stuff. (If you're me, though I'm pretty sure you're not.)

Yay, Flags of Many Lands™! Yay, St. Kitts and Nevis!

Maybe Padre Mickey will be kind enough to tell us the story of St. Kitts one day in his lives of the saints series, and who exactly was this non-saint Nevis that Kitts always was hanging out with.

Suspicious if you ask me.

Now playing: The Beatles - Chains
via FoxyTunes


dguzman said...

Oy vey, every other word out of The Kat's mouth is "Hidden Markov models" so this actually made some sense to me. Thanks for the 'splainin!

Distributorcap said...

i had a whole class on eigenvectors - i completely forgot about them --- also matrix math, game theory, advanced regression and multivariate analysis...

you are making me relive grad school

Matty Boy said...

Grad school was fun! For me at least.

Wormwood's Doxy said...

Sorry Matty boy, but you are ALL wrong on this. At my parties, EVERYONE is in the kitchen! They refuse to go in the living room at all.

Don't know what that does to your equation...


FranIAm said...

Doxy we have to stop meeting like this... Padre's, Grandmere's, Maddie's and now Matty's!

I came to see if Padre had something to say about St Kitts. I better stop by the dance party.

how are the new digs?

Andy said...

It is very difficult to study Markov chain topic. Not many good reference textbooks to study Markov chain.

I use Markov Chains and Stochastic Stability to study. This is good reference textbook.

Do you have any other good Markov Chains related textbooks recommend?



Matty Boy said...

Hi, Andy. The most recent class I had on Markov chains was taught from the notes of the professor, so I can't give a good reference. Sorry.