[Haskell-cafe] How would you hack it?

[John Melesky]

On Jun 4, 2008, at 3:50 PM, Andrew Coppin wrote:
> However, if you can find me a source that explains what a "Markov  
> chain" actually *is*, I'd be quite interested.

In a non-rigorous nutshell:

You have the word "star". You want to pick another word to follow it.  
It turns out that, based on analyzing a corpus ("corpus", here means  
"bunch of text you extract information from"), the following word  
pairs occur:

star wars (20% of the time)
star cluster (5% of the time)
star dust (10% of the time)
star system (25% of the time)
star -end-of-sentence- (5% of the time)
.
.
.

So you use those occurrence statistics to pick a feasible next word  
(let's choose "system", since it's the highest probability here -- in  
practice you'd probably choose one randomly based on a weighted  
likelihood). Then you look for all the word pairs which start with  
"system", and choose the next word in the same fashion. Repeat for as  
long as you want.

Those word-pair statistics, when you have them for all the words in  
your vocabulary, comprise the first-level Markov data for your corpus.

When you extend it to word triplets, it's second-level Markov data  
(and it will generate more reasonable fake text). You can build higher  
and higher Markov levels if you'd like.

And, ultimately, though the example is about text, you can use this  
method to generate "realistic" sequences of any sequential data.

Hope that helps.

-johnnnnnnn