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 <cstdlib> /* 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<TSIZE; i++) {
for (j=0; j<TSIZE; j++) {
table[i][j] = value;
}
}
}
double randfloat(void) {
return (double)rand()/RAND_MAX;
}
int chooseNextNote(int lastnote, long ttable[TSIZE][TSIZE]) {
int targetSum = 0;
int sum = 0;
int nextnote = 0;
int totalevents = 0;
int i;
lastnote = lastnote % TSIZE;
for (i=0; i<TSIZE; i++) {
totalevents += ttable[lastnote][i];
}
targetSum = (int)(randfloat() * totalevents + 0.5);
while ((nextnote < TSIZE) && (sum+ttable[lastnote][nextnote] <= targetSum)) {
sum += ttable[lastnote][nextnote];
nextnote++;
}
return nextnote;
}
|
Further Reading / Links
Exercises
Do exercise 1, and choose one of the following exercises to do.
-
|
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.
|  |
- 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.
- Write a second-order Markov chain object.
- The example table removes the octave information. Write an object
which contains an absolute pitch transition table for MIDI notes.
- Add a "clear" message to the object which will erase the current
contents of the transition table.
- 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.
- Add a random number seed, using srand(time(NULL)); in
the initialization of the object.
|