# Digital Music Programming II: Markov Chains

This lab presents a Max external object which manages a first order Markov chain of MIDI pitch-class transitions.

Markov chains describe how to get from one event to another. If you have three events A, B, and C which can come in any order, a Markov chain describes the probability of what the next note will be. The following table demonstrates a first-order Markov chain. There are three possible states be at. Either the current note is A, B, or C. For each possible current state, there are three possible next letters. Each row in the table indicates the relative probability of going to the next letter. For example, if you are currently on letter A, there is a 20% chance of repeating letter A, a 50% chance of going to B, and a 30% chance of going to C. Note that the sum of changes for each row is 100% (20 + 50 + 30 = 100).

first-order Markov chain.
 Current next note next note next note Note A B C A 20% 50% 30% B 35% 25% 40% C 70% 14% 16%

Here is a sequence of letters generated with the table above. the sequence C B which is rare, is highlighted in red. The common sequence C A is highlighted in blue. (Generated with the program markovex.cpp).

 ``` A C A C B C A B C A B B C A B C C A C A B A B A C A B A A C A B C A B C A B C A C A C A C A B C C A C A A A B C A A A B A B C C C A B B C A B B A B C C B A C A B C A B C B A B C A B C A B C A C A C A C A B C C A C A B C A C A B A A B B B A C A A B C C C A B C A B A B A A C A C A C A C A B A B C B C C A C A A B A A A B C A C A A C A C A C A C A A C A A A B C B B B B B C A B C A C A C B C A C B C C B C B C C A B A C C A B A B A B A B A A B A B B C A B C A B B C A B C A A B B C A B B B A ```

The table above is for a first-order Markov chain. This means that only the current state affects the choice of the next event. A second-order Markov chain would mean that the current state and the last state affect the choice of the next event. A third-order Markov chain would indicate that the current state and the last two states in the sequence will affect the choice of the next state. Here is an example transition table for a 2nd order Markov chain. For example, if the current event is B and the last one was A, then the probability of the next event being A is 20%, B is 45% and C is 35%. The pattern C B A will never occur, and the pattern B B C will occur rarely.

second-order Markov chain.
 Current next note next note next note Notes A B C A A 15% 55% 30% A B 20% 45% 35% A C 60% 30% 10% B A 35% 25% 40% B B 49% 48% 3% B C 60% 20% 20% C A 5% 75% 20% C B 0% 90% 10% C C 70% 14% 16%

# Source Code

markov1.c
 ``` #include "ext.h" #include /* included for rand() function */ #define TSIZE 12 /* for 12x12 pitch class transition table size */ typedef struct { t_object max_data; long lastnote; long outnote; long ttable[TSIZE][TSIZE]; void* output; } MyObject; void* object_data = NULL; void main (void); void* create_object (void); void InputTriggerNote (MyObject* mo, long value); void InputTrainingNote (MyObject* mo, long value); void InputBang (MyObject* mo); void MessageClear (MyObject* mo); int chooseNextNote (int lastnote, long ttable[TSIZE][TSIZE]); void setAllValuesOfTable (long table[TSIZE][TSIZE], int value); long midilimit (long value); double randfloat (void); void main(void) { setup((t_messlist**)&object_data, (method)create_object, NULL, sizeof(MyObject), NULL, A_NOTHING); addbang((method)InputBang); addint ((method)InputTriggerNote); addinx ((method)InputTrainingNote, 1); addmess((method)MessageClear, "clear", A_NOTHING); } void* create_object(void) { MyObject* mo = (MyObject*)newobject(object_data); mo->lastnote = 60; mo->outnote = 60; setAllValuesOfTable(mo->ttable, 0); mo->output = intout(mo); intin(mo, 1); return mo; } void InputTriggerNote(MyObject* mo, long value) { int octave; value = midilimit(value); octave = value / 12; mo->outnote = 12 * octave + chooseNextNote(mo->outnote, mo->ttable); outlet_int(mo->output, mo->outnote); } void InputTrainingNote(MyObject* mo, long value) { int newstate, laststate; value = midilimit(value); laststate = mo->lastnote % 12; newstate = value % 12; mo->lastnote = value; mo->ttable[laststate][newstate]++; } void InputBang(MyObject* mo) { InputTriggerNote(mo, mo->outnote); } void MessageClear(MyObject* mo) { setAllValuesOfTable(mo->ttable, 0); } long midilimit(long value) { if (value < 0) return 0; if (value > 127) return 127; return value; } void setAllValuesOfTable(long table[TSIZE][TSIZE], int value) { int i, j; for (i=0; i

# Exercises

Do exercise 1, and choose one of the following exercises to do.
1.  Compile the markov1.c Max external object and program it with input from a MIDI keyboard. Then play back notes from the object using a rhythm generated by the MIDI keyboard. Use the patch on the left as a guide to making your own patch.

2. Add code to the object to allow it to save its probability table into a file which can be read back into the object at a later time.

3. Write a second-order Markov chain object.

4. The example table removes the octave information. Write an object which contains an absolute pitch transition table for MIDI notes.

5. Add a "clear" message to the object which will erase the current contents of the transition table.

6. Analyze some melodies and prepare a 1st order Markov chain transition table for use in your Max object from your extracted data. Here is a transition table generated from 1700 monophonic songs (transposed to C tonic) which contain approximately 73,000 notes.

 ``` C C# D E- E F F# G A- A B- B |------------------------------------------------------------------------- C | 3282 1 2661 13 2303 180 8 1510 0 682 106 1537 C# | 2 0 17 0 3 0 0 0 0 0 0 0 D | 3892 17 2694 32 3172 682 5 1000 0 183 8 423 E- | 9 0 35 15 0 27 0 6 0 0 0 0 E | 1639 4 4585 0 3365 2494 30 2978 0 235 8 15 F | 44 0 1176 18 3843 1526 0 1637 2 488 11 117 F# | 1 0 7 0 11 2 19 107 0 12 0 0 G | 2564 0 499 11 2766 3653 86 4854 4 1658 60 225 A- | 0 0 0 0 0 3 0 6 0 2 0 0 A | 227 0 97 0 36 250 9 3016 2 955 29 427 B- | 51 0 7 3 36 6 0 67 3 55 72 6 B | 1369 0 349 0 10 22 2 214 0 781 8 258 ```

Values in this table can be placed directly into the object. Note that the table does not contain probabilities, but rather total transition counts. For example, the transition from G (5th scale degree) to A (6th scale degree) occurs 1,658 times in the set of songs.

7. Add a random number seed, using srand(time(NULL)); in the initialization of the object.
```

```