On rereading this just now, I just had to laugh. Two reasons I suppose. First of all, the article is really about Markov chains (my original title was just that), and I spend just 3 paragraphs right at the end talking about speech recognition. I think my editor was a smidge too enthusiastic about the speech recognition part. Secondly I note that I talk about random walks in a couple of places – even Gambler’s Ruin – a topic I skirted just recently here. It certainly sounds like I knew back then what I couldn’t work out a few days ago; so maybe there’s something to all this forgetting stuff as you grow older.

Where was I? Oh, yes, Markov chains. In essence, they’re a description of a finite state machine with the transitions between states governed by some probability model. What can we determine from such a model? Well, there’s the possibility of calculating the probabilities for a steady state after a large number of transitions for a start. Using the Viterbi algorithm, you can try to determine the transition probabilities for a “hidden” model from a series of state changes. The standard (read: old) method for pricing equity options uses a Markov chain model known as the Black-Scholes algorithm (and, boy, does that take me back to the time I worked for the swaps trading desk at Deutsche Bank).

This article first appeared in issue 301, December 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a few months. When I buy the current issue, I'll publish the article from the issue a year ago. Since I've now got September's issue (and have had it for a couple of weeks), here's September 2008's article.

Pure fun this time: generating random text. The article shows that generating pure random text where every character has an equal probability of appearing next doesn't work particularly well. Enter Markov chains, where the probabilities of what comes next are skewed to what has just appeared. First we look at characters, so the next character depends on what the previous character was (order-1 Markov chain), all the way up to an order-10 Markov chain (the next character depends on the previous 10 characters). I particularly like the example text generated from War of the Worlds for this latter case:

BOOK ONE THE EVE OF THE WAR

No one would have left an abiding sense of smell, but it had a pair of very large dark eyes of a Martian from the Martians making their blue shirts, dark trousers, and singers.

I just love the idea of the Martians making their blue shirts and dark trousers.

Anyway, I also experimented with Markov chains that use previous words instead of characters, but in reality an order-10 Markov chain based on characters would work very well.

This article first appeared in issue 272, September 2008.

You can download the PDF here.