Weighted Random Numbers

In Pd to generate a random number you use the [random] object. Everytime it receives a "bang"-message, it will generate a random number between 0 and its argument number minus one.

A [random 10] object will generate random numbers between 0 and 9 (= 10 - 1), while [random 2] will switch randomly between 0 and 1. All the numbers will be chosen with the same probability: If you bang a [random 2] often enough, you will get roughly the same amount of zeros and ones out of it.

Now lets say you want to get a 1 more often than a 0, lets say twice as many. So a 1 should get double the "weight" of 0 in your process. There is no builtin object for this in Pd, but the [list]-abs collection contains the object [list-wrandom], that does exactly that: weighted random numbers. (In the RjDj library a clone of it is included as [u_wrandom].)

You control the numbers to choose by sending a list (the probability function) to the rightmost inlet of [list-wrandom]. Each number in that list specifies the weight, that its position should get in the random choice. Note that counting the posititions starts at 0.

For example, if you send a list "1 2" to [list-wrandom], then you will get a zero with a weight of 1, and a one with a weight of 2, i.e. you will get twice as many ones than you get zeros if you bang the object very often.

This can be extended to longer sets and you can also exclude numbers from being selected at all: If you sent a list "0 1 1" to [list-wrandom], you will never get a 0, and about the same amount of ones and twos. What would a list "0 5 2 1" give?

Markov Chains

A Markov chain sets an additional constraint on the choice results: Here the probability function can change depending on the previous result(s) of the random choice. So a Markov random process has a bit of memory built in. How many previous results are taken into account by a certain Markov process also is called the "order" of a Markov chain. We will only deal with Markov chains of the 1st order here, which means, that they will only evaluate the previous result when deciding on the probability function to use, and they will ignore any prior results. Our chains also will use a finite number of possible results or states.

Markov chain with [list-wrandom] objects

To make the [list-wrandom] object into a Markov chain, we need as many of them as we have states to manage. Each [list-wrandom] object will be primed with the probabilities to apply for choosing the next state. A [select] object will receive the current state and select, which of the [list-wrandom] objects should be the next active one. Sending the current state to the [select] will activate the respective [list-wrandom] object.

To easily set the probabilities we use a [route] object and messages, that in front of the list of probability weights also include the index number of the [list-wrandom] object to set. The help-file for [list-wrandom] includes such an example in the "markov"-subpatch. Make sure that each of your weight lists includes as many elements as you have states.

Managing Markov Chains more easily

Basically you can already use this to write many Markov chains, but it becomes tedious after a while to make so many connections. So I wrote a little helper abstraction that will automatically create the needed list-wrandom objects and connect them with [select]s and [route]s and spices everything up with some dynamic patching.

All you need to do is create an instance of the [markov-chain] object provided in this tutorial's archive and send probability lists with state index number prepended to its rightmost inlet. A bang to its first inlet will select a new random state and send its number to the outlet, a float number will set the current state first and generate a new state from that. Use "set" messages to onnly set the state without calculating a next one immediatly.

A Markov chain abstraction called [markov-chain]

[markov-chain] as default provides room for up to 16 states. If you need more, you can create the object with an argument like [markov-chain 20] for 20 chains. The help-file also includes an example how you can load a state transition matrix from a textfile into the markov object. This way you can write the full probabilities matrix in a normal text editor or even exchange them easily on the fly.

Alternative Approach

The Pd documentationn contains an alternative approach to write a Markov chain in 2.control.examples/21.markov.chain.pd

Here [moses] is used to make a weighted random choice. While this is fine for short chains, it becomes tedious quickly if you need longer chains with more states.

Markov chain with [moses] objects as shown in 21.markov.chain.pd

Higher Order Markov Chains

(This update was added on May 25, 2009)

Using the [markov-chain] abstraction it is possible to do higher order Markov chains as well. The tutorial archive includes an example for a second order chain (pictured below), that takes the two previous states into account when selecting a new state. You now need a [markov-chain] for each possible second to last state. The example has three states, so you need three [markov-chain]s. We use [route] to select the [markov-chain] object matching a chain.

The object is not started with a "bang", but also receives the current state as a float number. This is necessary because internally it might still have a different state saved, although one of the other two [markov-chain]s might already have produced another current state. The float message will overwrite the internally stored states with the real one.

2nd order Markov chain in markov-chain-2nd-order.pd