A Markov chain is a chain of variables such that future variable are based on present variables, no matter how those present variables came into being. So if two different paths of variables lead to the same state, then presumably, the two paths would merge into a single path after that particular state had been reached.

To give a bigram related example:

(x, x) -> (y, y)

(y, y) -> (z, z)

(z, z) -> (y, y)

As you can see, each destination point depends only on the immediately preceding point, irrespective of any points before that (although that is not required; each point could be dependent on n preceding points, called an ngram; or it could be based not on the preceding point but the one before that, or basically any complicated formula that makes sense).

So:

Path 1: (x, x) -> (y, y) -> (z, z) -> (y, y) ...

Path 2: (z, z) -> (y, y) -> (z, z) -> (y, y) ...

Different starting points, same destination. If you don't know what the starting point is, there's no way to determine it from subsequent points.

A popular use for this is in the "Markov Chain Algorithm", as an ngram (usually bigram) text generator. A list of ngrams is generated from a corpus, with information about what words are known to follow each ngram. So then, given a starting point (the first ngram), the generator chooses appropriate succeeding words.

Some very simple implementations choose randomly from the list of known following words without considering probability, so for example, if "as little" was followed 99 times by "as" and only 1 time by "a", then, in the output text, there is equal chance of "as little" being followed by "a" or "as." Better implementations do consider probability, so that "as little" would almost always be followed by "as".

Markov Chain Algorithm (last edited 2008-05-18 16:47:15 by CantrellRehj)