Virtual Hyenas, Markov Chains, and Random Knights

Welcome to this week’s Math Munch!

It’s amazing how a small step can lead to a chain reaction of adventure.

Arend Hintze

Arend Hintze

Recently a reader named Nico left a comment on the Math Munch post where I shared the game Loops of Zen. He asked why the game has that name. Curious, I looked up Dr. Arend Hintze, whose name appears on the game’s title page. This led me to Arend’s page at the Adami Lab at Michigan State University. Arend studies how complex systems—especially biological systems—evolve over time.

Here is a video of one of Arend’s simulations. The black and white square is a zebra. The yellow ones are lions, the red ones are hyenas, and guess who’s hungry?

Arend’s description of the simulation is here. The cooperative behavior in the video—two hyenas working together to scare away a lion—wasn’t programmed into the simulation. It emerged out of many iterations of systems called Markov Brains—developed by Arend—that are based upon mathematical structures called Markov chains. More on those in a bit.

You can read more about how Arend thinks about his multidisciplinary work on biological systems here. Also, it turns out that Arend has made many more games besides Loops of Zen. Here’s Blobs of Zen, and Ink of Zen is coming out this month! Another that caught my eye is Curve, which reminds me of some of my favorite puzzle games. Curve is still in development; here’s hoping we’ll be able to play it soon.

Arend has agreed to do an interview with Math Munch, so share your questions about his work, his games, and his life below!

Eric Czekner

Eric Czekner

Arend’s simulations rely on Markov chains to model animal behavior. So what’s a Markov chain? It’s closely related to the idea of a random walk. Check out this video by digital artist, musician, and Pure Data enthusiast Eric Czekner. In the video, Eric gives an overview of what Markov chains are all about and shows how he uses them to create pieces of music.

On this page, Eric describes how he got started using Markov chains to make music, along with several of his compositions. It’s fascinating how he captures the feel of a song by creating a mathematical system that “generates new patterns based on existing probabilities.”

Now there’s a big idea: exploring something randomly can capture structures that might be hard to perceive otherwise. Here’s one last variation on the Markov chain theme that involves a pure math question. This blog post ponders the question: what happens when a knight takes a random walk—or random trot?—on a chessboard? It includes some colorful images of chessboards along the way.

How likely it is that a knight lands on each square after five moves, starting from b1.

How likely it is that a knight lands on each square after five moves, starting from b1.

The probabili

How likely it is that a knight lands on each square after 200 moves, starting from b1.

The blogger—Leonid Kovalev—shows in his analysis what happens in the long run: the number of times a knight will visit a square will be proportional to the number of moves that lead to that square. For instance, since only two knight moves can reach a corner square while eight knight moves can reach a central square, it’s four times as likely that a knight will finish on a central square after a long, long journey than on a corner square. This idea works because moving a knight around a chessboard is a “reversible Markov chain”—any path that a knight can trace can also be untraced. The author also wrote a follow-up post about random queens.

It’s amazing the things you can find by chaining together ideas or by taking a random walk. Thanks for the inspiration for this post, Nico. Keep those comments and questions coming, everyone—we love hearing from you.

Bon appetit!

11 responses »

  1. Wit the Markov Chain, once the chain gets to stopping point ( like the 2 or 9 in the video ) does it restart at the beginning place? If it doesn’t then what does it do?

    • In that specific example, the chain would terminate because it has no possible outcome when it lands on 2, 9 or 10. Let’s say you were using a Markov Chain to write a melody. If you used that chain your melody would stop if it landed on either 2, 9 or 10. I personally like using looping chains for music composition and then deciding myself where I should end the passage. A non-looping chain could be just as good though, especially if you’re looking for a way to have the passage finish naturally. The downside of course, is that the chain could stop quite quickly leaving you with very little music. Hope that helped!

    • I’m glad you found it, too! Often we ping the folks we write about, but I dropped that ball in your case. Glad you’re enjoying the site. Please share it with others who might enjoy it, and thanks for making great things with math!

  2. Pingback: Math Teachers at Play #70 | Let's Play Math!

  3. The markov chain video was very interesting! I especially liked how the music was made with the chain. It actually sounded a lot better than I was expecting it to- it didn’t just sound like a bunch of random notes, but a somewhat organized musical piece. I wonder if some sort of more structured song could be formed using the chains. Maybe one chain could be used for a “verse” section, and another for a “chorus” etc.. Even cooler would be if somebody figured out how to make counter-melodies and harmonies that could overlap and give the music a fuller sound. I wonder, is that possible? Or would it be too difficult to choose chains that generated notes that sounded good together? It’s a very cool topic.

    • Glad you enjoyed it! I have also been quite surprised with the results of using these chains in music. I have never thought about approaching it exactly the way you suggest – one chain for the verse, chorus, etc. Maybe I’ll give that a shot.

      I actually composed an entire album using Markov Chains in direct and indirect modes. Check it out over at: whatericdoes.bandcamp.com. Track 6 specifically uses melodies and counter-melodies like you mentioned. I also have an entire write up on creating the album over at my website: whatericdoes.com in the “About The Artist” section under Graduate Thesis drop down.

  4. I did not understand the video at first. I thought that the video was very interesting because of how the shapes moved in a kind of pattern.

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