Markov chains remind me of Dory

In the movie “Finding Nemo” Marlin the clownfish (Albert Brooks) tries to find his fishnapped son Nemo (Alexander Gould), with the help of Dory (Ellen DeGeneres), a blue tang with short memory lapses. Marlin finds that a dialogue with Dory is an exercise in frustration, example:

Dory: I saw a boat.
Marlin: You did?
Dory: Yeah, it went by not too long ago. Follow me.
[few seconds later]
Dory: Would you quit it? What, the ocean isn’t big enough for you or something like that? You got a problem? Huh? Do ya, do ya, do ya? You wanna piece of me? Yeah, yeah! Ooh, I’m scared now! What?
Marlin: What? You said you saw a boat.
Dory: A boat?
Marlin: YES.
Dory: Hey, I’ve seen a boat. It went by not too long ago. It went… this way. It went this way.
Marlin: Wait a minute, you already told me which way the boat went.
Dory: I did? Oh, no…

Simply put, Markov chains (named after Russian mathematician Andrey Markov, 1856-1922) describe random processes that have no memory of past actions; they are based on present (current) knowledge and analysis of the future. Consider the game of backgammon (aka Turkish SheshBesh, Greek Plakoto and Bulgarian Tapa). In backgammon, two players use a board made of twenty-four narrow, multicoloured triangles (‘points’) and 15 checkers. The object of the game is to move all your checkers from the opponents’ half into your own “home board” (by throwing a pair of dice) and then remove them from the board. Backgammon is a Markov chain because as the game always proceeds from the moment the dice hit the board. There is no ‘history’ and the gamers only concern themselves with moves that follow the throw of the dice. Now think about a card game, such as Poker of Bridge — players would do well to take into account the history of the game (in the form of past rounds). By remembering which cards were played — and by whom, player can extrapolate the importance of the cards they have in their hands, as well as the cards held by the other players and the “bank.”

Markov chains have numerous mathematical applications, but I am more interested in the ways Markov chains are used to generate random text that is based on another text (a process known as “dissociated press”.) In principle, generating dissociated press text works like this:

  1. We take a body of text (a line, paragraph, chapter, an entire book, any length will do.)
  2. We count each word-pair in the text and compute how often these two words appear together and list those occurrences in a table.
  3. Say, for example, we have the combinationgood + evening 13 time
    good + pace 10 time
    good + vibrations 3 time
    good + smoke once
  4. We do this for each and every word in the text. Our frequency table with grow very fast!
  5. We then print a new body of text – only this time we generate the wordsat random, based on the frequency of their occurrence in the text. So, in the example above, the word Good appeared in total 27 times. If, for example, the first word in the original was “good”, followed by “evening” – we throw an imaginary dice that has 27 sides (one for each occurrence of the word ‘good’ — computers can do it easily!) where the word ‘evening’is written 13 times, ‘pace’ 10 times, and so on. Say, the word ‘smoke” came up.
  6. In our table, we take the word ‘smoke’ and check the table for all occurrences of the word (it appeared once with ‘good’, but may have other partners). We then generate the next word (say, ‘screen’.) Our text used to look like this: Good evening roger!It now says Good smoke screen!

Aside from being an entertaining exercise, dissociated press can help us, for example, compare bodies of text (for example – Shakespeare and his contemporary, say, Ben Jonson. Using dissociated press, we can compare the language used by Shakespeare to Jonson’s – based on the occurrence, and frequency of words they used.

You must have heard the claim that ‘a million monkeys typing for a million years will eventually produce the bible’.{The literary opus changes, according to the teller’s taste – some say, Shakespeare’s work, others say, The Iliad, I even heard a version invoking that unique British wizard – Harry Potter.) Using Markov Chains and dissociated press techniques, an unnamed programmer (or group of programmers) came up with the Markov Bible, here is an excerpt from Genesis 1, first, the original, then the dissociated version:

The Holy Bible: King James Version. 2000.

1 In the beginning God created the heaven and the earth.

2 And the earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.

3 And God said, Let there be light: 2 Cor. 4.6 and there was light.

4 And God saw the light, that it was good: and God divided the light from the darkness.

5 And God called the light Day, and the darkness he called Night. And the evening and the morning were the first day.

6 And God said, Let there be a firmament in the midst of the waters, and let it divide the waters from the waters.

7 And God made the firmament, and divided the waters which were under the firmament from the waters which were above the firmament: and it was so.

8 And God called the firmament Heaven. 2 Pet. 3.5 And the evening and the morning were the second day.

9 And God said, Let the waters under the heaven be gathered together unto one place, and let the dry land appear: and it was so.

10 And God called the dry land Earth; and the gathering together of the waters called he Seas: and God saw that it was good.

11 And God said, Let the earth bring forth grass, the herb yielding seed, and the fruit tree yielding fruit after his kind, whose seed is in itself, upon the earth: and it was so

The Markov Bible

Now And the sun rose up his father, and they said, O LORD judge betwixt us concerning that is his brother Abel. And the likeness of the field which his wife; and the God set by her.

And Mahalaleel eight days of thine only bring them unto us? one that Ishmael his wife, and hath also heard thee: bury thy dead; none other but the land whereon thou fearest God, the choice of the two hundred and eat, and with him, Because the flocks by force thy face, and he ungirded his father, and behold the LORD. And she said unto his dead, and sent messengers before him forth jewels of Padanaram, for I pray thee, drink also: and Esau said, Behold, in the LORD hath given no man is life, and we said, I establish my father speak unto Zoar. Then again bare Abram and which returned that is my service which he took a wife took one that are these things, and daughters: And I give all thy brother, and Methusael begat sons and I pray thee, if now done in the same is the ground. And God went out, and the sons of Ellasar; four hundred pieces of Abram’s brother’s name Asher. And I pray thee. And Jared were sons of them unto my son of the LORD said unto him in the name Seth: For Sarah saw the LORD scatter them out of the great wrestlings have told Rachel his brother and two and he said, I am the ghost, and all flesh. And Jacob saw Isaac, which went up from this place, and made the frost by a little one: Oh, let us concerning the Canaanites was a feast, and thirty years, and blessed them, Know ye to keep thee from Abraham. Behold, I have I be far from off from the earth. And they seemed unto Cain, lest thou require the face of Egypt, as the LORD said, I sworn, saith the eyes of Noah, Shem, Ham, the waters upon his sons and I will I said unto my covenant between me this place; for all one to keep me find there be Abram in unto the men of Bela, which he ran again into the younger. And Enoch walked with thee a keeper of millions, and twelve princes shall thirty years, and came to pass, when he commanded Noah.

Links to follow:

Contribute to ToingToing!