Markov Chains 1

Andrei Andreevich Markov was a Russian mathematician who discovered a technique for recording the dependencies between items in series. This technique has been named Markov Chains in honour of its inventor.

Markov Chains have a long and successful history in computer music research, and for good reason. Markov Chains provide an effective mechanism for creating and using stochastic matrices in musically satisfying ways.

Markov Chains work by analysing the chance of any given pitch (to put the example in a musical context) going directly to any other pitch. We can calculate this by checking a particular pitch every time it occurs in a composition and weighting the notes that follow it into a stochastic matrix. If we do this for every pitch value we build a stochastic matrix which resembles the composition that it is based on. Let's take a look at an example.

{64,62,60,62,64,64,64,62,62,62,64,67,67,64,62,60,62,64,64,64,64,62,62,64,62,60} This pitch array is the start of a very well known nursery rhyme and provides us with a perfect vehicle for investigating Markov Chains. If we identify each individual pitch in this array we get one row of a table like so:

If we now mark out all the notes that could proceed these few notes we can make a proper two dimensional matrix like so:

Now all we need to do is fill matrix in. How do we do this. Well for the first stage let's just count up all the times that a pitch in the left column is followed by any pitch in the top column. The left column of "bold" numbers is known as the 'state' or 'seed', and the top row of "bold" numbers is known as the 'transition' or 'output'. It is the 'seed' that is the difference between a normal stochastic matrix and a Markov matrix.

To turn this table into a working Markov matrix we need to weight the totals so that there sum is equal to 1.0 (give the totals a percentage). Once we have completed that step the matrix should look like the following.

The final detail in our discussion of basic Markov matrices brings us back to the 'seed'. Stochastic matrices can only provide us with output. A Markov matrix provides the far more useful ability to find an output based on an input. The input is known as a seed. In the example above we can deduce that provided a seed of 67 there is 50% likelihood that the output will be 64 and a 50% likelihood that the output will be 67. Following this one step further we can use the output of this choice as the seed of the next choice.

Let's work through a paper example. We will choose to use a seed of 60 for this example. We will use the prefix's s=seed r=random number o=output //for comments. Remember from the tutorial on stochastic matrices that the choice of output is based on the random number being smaller than the sum of weighings going left to right across the row.

s60 r0.4 o62 //Note that there is no choice but to choose o62 from s60

s62 r0.9 o64 //See that o62 is now s62

s64 r0.6 o64

s64 r0.2 o62

s62 r0.1 o60

s60 r0.8 o62

s62 r0.5 o62

s62 r0.8 o64

s64 r0.99 o67

...

Getting the picture :-) Remember that this process can go on for ever!

This very simple application builds on the application presented in the preceding stochastic matrix tutorial. It is reasonably commented and should not be to hard to follow. Notice that the code uses the same data table as the one used in this example. Try changing some of the weighings and see how the results change. Be aware that all other not parameters are defaults. Only the pitch will change.

Click here to view/download the source.

  1: import jm.music.data.*;
  2: import jm.util.Write;
 
  4: public final class BasicMarkov{
  5:         public static void main(String[] args){
  6:                 //A map for our musical pitches
  7:                 int[] map = {60,62,64,67};
  8:                 //A multidimensional array representing our markov matrix        
  9:                 double[][] markovMatrix = {{0.0,1.0,0.0,0.0},
 10:                                           {0.3,0.3,0.4,0.0},
 11:                                           {0.0,0.45454545,0.45454545,0.09090909},
 12:                                           {0.0,0.0,0.5,0.5}};
 13:                 //The seed for generating output
 14:                 int seed = 2; //checking that our map says 64 is at index 2
 15:                 //The output as an index value 
 16:                 int output = 0;  //there are no outputs yet
 17:                 //Score, part and phrase to contain the output
 18:                 Score scr = new Score();
 19:                 Part part = new Part();
 20:                 Phrase phrase = new Phrase();
 
 22:                 //Add the seed note to the phrase first
 23:                 Note n = new Note();
 24:                 n.setPitch(map[seed]);
 25:                 phrase.addNote(n);
 26: 
 27:                 //Generate notes and add them to a phrase
 28:                 for(int i=0;i<30;i++){
 29:                         //Retrieve a random number between 0.0 and 1.0
 30:                         double choice = Math.random();
 31:                         //The current sum of weightings left to right
 32:                         double currentSum = 0.0;
 33:                         //Check matrix left to right
 34:                         for(;output<markovMatrix.length;output++){
 35:                                 currentSum += markovMatrix[seed][output];
 36:                                 if(choice <= currentSum){
 37:                                         break; //break when we've chosen right number
 38:                                 }
 39:                         }
 40:                         Note note = new Note();
 41:                         note.setPitch(map[output]);
 42:                         phrase.addNote(note);
 43:                         //Change the seed to equal the output
 44:                         seed = output;
 45:                         //Reset the output for the next pass 
 46:                         output = 0;
 47:                 }
 48:                 part.addPhrase(phrase);
 49:                 scr.addPart(part);
 50:                 Write.midi(scr,"basic_markov.mid");
 51:         }
 52: }

Stochastic Matrix

Markov Matrix (Part 2)