100 Years of Markov Chains

On January 23, 1913, the Russian mathematician Andrei Andreyevich Markov addressed the Imperial Academy of Sciences in St. Petersburg, reading a paper titled “An example of statistical investigation of the text Eugene Onegin concerning the connection of samples in chains.” The idea he introduced that day is the mathematical and computational device we now know as a Markov chain.

On January 23, 2013, the Institute for Applied Computational Science of the Harvard School of Engineering and Applied Sciences will celebrate the centenary of this event. If you are in the Boston area and would like to attend, consider this your invitation. See the announcement for details of when and where. There will be three talks:

First Links in the Markov Chain: Poetry and Probability.
Brian Hayes, American Scientist magazine

From Markov to Pearl: Conditional Independence as a Driving Principle
for Probabilistic Modeling.
Ryan P. Adams, SEAS Computer Science

Applications of Markov Chains in Science.
Pavlos Protopapas, Harvard-Smithsonian Center for Astrophysics and SEAS

Markov’s 1913 paper was not his first publication on “samples in chains”; he had written on the same theme as early as 1906. So why celebrate now? Well, for one thing, it’s too late to do it in 2006. But there is another reason: It was the 1913 paper that was widely noticed, both in Russia and abroad, and that inspired further work in the decades to come. The earlier discussions were abstract and technical, giving no hint of what the new probabilistic method might be good for; in 1913 Markov demonstrated his technique with a novel and intriguing application—analyzing the lexical structure of Alexander Pushkin’s poem Eugene Onegin. Direct extensions of that technique now help to identify genes in DNA and generate gobbledygook text for spammers.

Sticklers for calendrical accuracy might raise another question about the timing of this event. On January 23 it will not yet be 100 years since Markov spoke in St. Petersburg. In 1913 Russia had not yet adopted the Gregorian calendar; when the nation did so in 1918, it skipped ahead by 13 days. If you are troubled by this calendrical lacuna, you may want to organize your own symposium on February 5.

Update: Coverage of Markov Day in the Harvard Gazette.

Update 2013-02-24: Recordings of the talk are now available. Audio: MP3. Video: FLV, MP4. The slides are also on the web: HTML. Finally, my latest American Scientist column covers much of the same material: HTML, PDF.