# Markov Chains

Let's take a tune and dissect it. We'll start with a table to keep our answers in. On the left column will be the note we're currently looking at. On the top will be the next note. In every cell will be a zero (for now). We begin at the first note and start tallying. If the first note is a C, we'll look at row C of our table. If the second note is a D, we'll look at row C, column D. In that box (or cell), we'll add one to whatever number is in it already (at this point it's zero). Then, since the second note is D, we'll look at row D and the column of whatever the third note is (in the figure below, the third note was a G) and add one to that cell as well, and so on through the rest of the tune.

When all of the tallying is over with, we'll have the tally of how often every note follows every other note within this tune. We can easily figure out the percentage of the time that any note follows any other note. Let's do that and place the results in the correct cells. Now we have the percentage of the time that every note follows every other note within this tune. This is called a Markov chain. With this Markov chain, we can construct our own tune.

We can start with any note. Let's take C. We'll generate a random note to follow this C. Only it won't be quite random. If row C, column D has the entry .25, then 25% of the time, a D will be "randomly" chosen (remember: the row is the current note, and the column is the next note. The entry is the percentage of the time that the note for that column follows the note for that row in the original tune). If row C, column E has a zero, then an E will never be "randomly" generated. This is called weighting the results.

When we are done with this process, we will have another tune with a similar set of intervals to those of the original tune. If we get very lucky (or unlucky, if You want new results), we could get the exact tune we started with.

Of course, we don't actually have to start with a tune. We can just fill numbers into an empty table. As long as all of the entries in a row add up to 1 (in other words, we will get a note, any note, 100% of the time), we're okay.

We have an applet that will let You enter a tune and see what a Markov chain does with it. You must enter it in the following format: low C will be denoted C0. The C above that will be C1, and so on up to C4 (high C), which is the highest note allowed. Middle B would b B2. You must enter all notes with no space in between. Enter Q when You're finished. Thus, C0D0E0F0G0A1B1C1Q would play a scale from low C to the C below middle C. All of the letters must be in upper case.

As usual, we have a sample ready for non-Java users in the format listed above (only with spaces between the notes and extra lines to break it up some and make it easier to read). This sample was created using the Markov chain for Row, Row, Row Your Boat. It is, perhaps, not very good because there is a lot of repetition in the song (especially on the word merrily - three identical notes!).