For my Extended Project Qualification, I decided to look into using Markov Chains to generate music, with surprisingly okay results. For this I use the music21 Python library to import, analyse and export musicXML. This was finished in November 2015.

### Markov Chains

A Markov Chain is essentially a probability distribution that introduces state. To give an example, let's consider a naive music generator that plays a random note with some given probability. It'll play what is essentially a random string of notes, like hitting a keyboard with your fist, hitting some good and some bad notes. The important note to take away from that thought experiment is that there won't be a flowing tune at all - each note is independent of the last. If you try to alleviate this problem by massively weighting our selection to the best notes, you'll end up with something like the head of C Jam Blues - which is a perfectly fine tune, but if I wanted a computer to generate music, I'd quite like it to be able to generate more complex music than just a rehash of C Jam Blues every time.

A good way to make music flow is by considering the previous notes in a phrase, as notes are evidently not composed independently of each other. Otherwise composition would be as easy as rolling some dice and putting dots on a page! To introduce this phrasing, we consider what note we are currently playing when writing the next. Rather than having an absolute list of probabilities (e.g. there's a 0.5 chance of playing a C, 0.1 of a D...) we now have a transition matrix, where each row adds up to 1. When picking our next note, we look at the row of our current note for the probabilities we should use.

```
x C E G
C | 0.1 0.5 0.4
E | 0.2 0.3 0.5
G | 0.3 0.5 0.2
```

So if our first note was C, there is a 0.1 probability that we choose a C to be our next note.

We can expand this to look at multiple previous notes in a higher-order Markov Chain, where we consider the previous few notes as well as the current one. An order N Markov Chain is defined as a Markov Chain considering N inputs total. This gives us a row consisting of multiple previous notes, e.g. in this order 2 transition matrix:

```
x C E G
CC | 0.1 0.5 0.4
CE | 0.2 0.3 0.5
CG | 0.3 0.5 0.2
...| ... ... ...
```

This allows us to improve the phrasing of our music even more. However, this comes with a caveat which will be explained as we begin to look into how we determine these probabilities.

### Training our Markov Chains

To train our Markov Chains, we must observe what real music does and get probabilities similar to above. We do this by taking training melodies, transposing them so that they are all in the same key, and going through each note and recording the frequency of notes directly after it. First, we convert our notes to numbers, where 1 is the note of the key, 2 is the note above that and so on. Then we construct a 12x12 matrix to fill with frequencies, and initialise every value to zero.

Now we go through each training melody. For each note, on the row of the current note, we record what the next note is by increasing the number at that entry by 1. We repeat this for every note in every melody, and then divide each row by the total of it to give probabilities that sum to 1.

We do the same with rhythm, except we look at lengths of note rather than pitches. In my program, rather than considering a note-by-note basis, we instead record full beats of rhythm and change between those. This unfortunately detaches the rhythm from the melody, making less pleasing music.

### Actually Generating Music

This is the easiest bit. Start at a note, then use our Markov Chain to generate each note after it. Do the same for rhythm and map the pitches to notes. Then you're done. Just choose a key, turn your numbers into notes from that key, generate a title (my program does this by applying Markov Chains of order 4 to song titles from The Beatles) and output it as musicXML.

After experimentation, I decided to use an order 2 Markov Chain for the melody generation. The problem with higher-order Markov Chains is that you need to have lots of input data because otherwise you will end up with verbatim repeats of other tunes as many-note sequences are less likely to appear in multiple tunes than shorter ones so the program essentially chooses one of the few options and follows it.

### Extras in the program