Performance of Real-time Nth Order Stochastic Compositions[1]

by

Douglas Lyon

E-mail: Lyon@cse.bridgeport.edu

Phone: (203)576-4760

Computer Science and Engineering Department, Dana Building

University of Bridgeport

Bridgeport CT 06601

**Abstract**

This article* *presents a technique for the use of stochastic Petri-nets
for real-time realization of Nth order stochastic compositions (a Markov
process). The algorithm makes use of a data structure known as a stochastic
Petri table. This table is compact and suitable for interactive performance on
lap-top type computers. We also show how the inherently concurrent nature of
Petri nets can be used to implement real-time MIDI processing. Since some
readers are unfamiliar with Petri nets, we present a brief and incomplete
introduction to the basic ideas behind the Petri net and compare it with the
finite state machine.

The use of Markov chains for computer assisted composition is not new,
Schwanauer and Levitt's book, * Machine Models of Music*, describe an
experiment performed in 1955 called Illiac Suite. This experiment was performed
by Lejaren Hiller and Leonard Isaacson (Schwanauer and Levitt).

Attempts to realize Markov chain performance in real-time are not new (O'Haver 1978). This was only a first-order processes, however. High-order Markov chain composition has not been published in real-time, as far as we know.

A stochastic Petri-table is a data structure that is shown to enable the computation of high-order real-time Markov processes. We encode a melody using pitch class and ignore tempo and timbre information. Tempo and timbre information are ignored in order to simplify the presentation. The computation of the stochastic Petri-table is an off-line process, however, the table is compact (linear in the number of arcs) and enables real-time Markov chain computation. Our brute-force approach to building the Petri-table, while easy to implement, is slow. A harder to implement, but faster approach, has been suggested but remains untried. After the computation of the stochastic Petri-table, the program writes it to a file to be read during program start-up. Thus, this stochastic Petri-net approach allows us to perform a precomputation phase which permits fast execution.

We are motivated to take the stochastic Petri-net approach because we have found approaches in literature which do not give real-time performance and which use more memory than is practical on portable computers (Moore 1990). A further motivation for the use of Petri-nets is the concurrent nature of interfaces and music performance. It is often the case, for example, that a user will create interrupts during a performance. As shown in the following sections, these interrupts cannot be handled with a finite state machine but can be handled by Petri-nets.

A Turing machine is a computing device which consists of a control unit (which may assume one state at a time), a tape (which can store a symbol) and a read-write head (which moves relative to the tape and can relay information between the control unit and the tape).

A finite state machine is a deterministic device with a fixed number of states. A special case of the Turing machine, the finite state machine is also known as a finite automaton. The finite state machine consists of a Turing machine with a single input tape and a read-only head (Ralston 1983). The output and next-state of a finite state machine are a function of the machine's present state and inputs (Katz 1994).

Finite-state machines are often depicted by state diagrams. A state diagram is a directed graph which shows the input and output of the finite state machine. An example of a finite state machine diagram representation of a gum machine is shown in Figure 1.

Figure 1 A Finite State Machine Diagram for a Gum Machine

The price of gum from this machine is 15 cents. The Petri net can represent any finite state machine but the opposite is not true.

The finite state machine model does not handle interrupts well. From a programmer's view, a subroutine is serviced after the state of the machine is pushed onto a stack. The finite state machine does not provide a stack, nor does it describe how an interrupt should be serviced, or to where it should return.

A further limit of the finite state machine model is that it does not handle multiple asynchronous processes. This is really a result of its inability allow for the synchronization of parallel activities. One way to perform this synchronization is through the use of token passing.

Petri nets, which are covered in the following section, are able to model concurrency and interrupts, two features which are notably lacking in the finite state machine.

In the Petri net, places symbolize conditions and transitions symbolize
computations. In addition, every transition is connected to *input* and
*output* *places*.

Figure 2 Petri-net Primitives

The Petri-net is a bipartite graph because there are two types of nodes, places and transitions. It is a directed graph because all arcs connect from a place to a transition or from a transition to a place.

The Petri-net may be represented graphically using a Petri-net diagram or it may be represented textually using a Petri-net table. The primitives of the Petri-net diagram are shown in Figure 2. The diagram is better suited for human communication, while the table is better suited for machine communication. Figure 3 shows an example of a Petri net for a gum machine represented by both a Petri-net diagram and a Petri-net table.

Figure 3 Petri- Diagram and Table for a Gum Machine

The price of gum is 15 cents and no change is given.

The Petri net represented in Figure 3 is modeled with a finite state machine diagram shown in Figure 1. The finite state machine cannot model interrupts, and these are present in the example of a real-time MIDI delay system, shown in Figure 4. The real-time MIDI delay system is designed to act like a 3 second echo box with no decay and a maximum number of echos for every MIDI event. This has several advantages over traditional approaches to achieving a 3 second delay. There is no noise or decay in the repeated event. In addition, the number of echos is a parameter which is settable by the performer.

Figure 4 A Petri-Net for a Real-Time 3 Second Midi Delay.

From any place in the Petri net (P1..P7), an interrupt in the main event loop may be generated by the user's input of a mouse click.

The interrupt generated by the user, shown in Figure 4 by the
*Mouse_button* token, is typical of user generated events. User input
occurs concurrently with the execution of the main body of the program, and is
asynchronous with respect to the execution of the code.

The Petri-net represented in Figure 4 may be represented as a Petri-table and this is shown in Figure 5.

Figure 5 A Petri-Table for a 3 Second Delay

This table represents the same Petri net which is shown by the Petri diagram of
Figure 4. The * in the last row, second column of the Petri table indicates
that the *mouse_button* token will cause a jump from any place in the
Petri net.

A fragment of Pascal code which implements the Petri-table shown in Figure 5 is given in Figure 6.

begin { of main}

initialize_program;

transition := 1;

repeat

case transition of

1: {scan for an event }

begin

if midi_get(event) then {p1}

transition := 2 {got an event}

else

transition := 1;

end; {case 1}

2: {output note }

begin

echo_event(event);

if event.number_of_times_put < max_echos then

transition := 3

else

transition := 5;

{ok, we echoed enough times, check the queue for old events}

end; {case 2}

3: {update and start again if any new events occur}

begin

if midi_get(event2) then

transition := 4 {a new event occured while we were echoing}

else

transition := 2; {keep echoing, no new inputs}

end; {case 3}

4:

begin

(event); {keep old event for later}

writeln('stashing old event');

copy_event(event2, event);

transition := 2;

end; {case 4}

5:

begin

if q_empty then

transition := 1 {scan for fresh events}

else

transition := 6;

end; {case 5}

6:

begin {queue is not empty so get stashed event and echo it}

remove_q(event);

writeln('removed old event');

transition := 2;

end; {case 6}

end; {case}

until button;

QuitMidi; {discards memory and removes interrupt handlers}

end.

Figure 6. Code For A Three Second Delay

This code was written using Think Pascal(TM) on a Macintosh computer (Symantec
1991). The code was designed to be executed in a sequential fashion and so does
not enable the handling of true interrupts. Instead the events are queued by
the operating system and de queued by the *until button* of the main event
loop of the program. For the case of parallel Pascal, a more direct translation
from the Petri net to the code is possible.

A Markov process (or Markov chain) is a non-deterministic finite state machine. The difference is that there are probabilities assigned to the arcs in the finite state machine diagram. In addition, the sum of all the probabilities leaving any Markov state is equal to one.

A Markov random process is classed as being *continuous-valued* or
*discrete-valued*. For the purpose of selecting pitches from a scale
(finite set), we use the *discrete-valued Markov random process *(i.e.,
Markov Chain). A *Markov chain* is a DVMRP with a countable or finite set
of states (Stark and Woods).

The Markov chain satisfies the conditional probability mass function expression

(1.3-1)

The value of the random variable *X* at time *t* will determine the
conditional probabilities for the future process values. The process values are
called the process state and the conditional probabilities are called the
*transition probabilities* between the states. A Markov process is
*stationary* if the probabilities are static. We assume that the Markov
process is stationary because we perform off-line analysis.

The transition table of probabilities uses

(1.3-2)

The resulting two dimensional table represents the transition probabilities in
a first-order Markov chain, as discussed by Dodge and Jerse in their book
*Computer Music*. Dodge and Jerse, like Moore, describe an N+1 dimensioned
table to represent an Nth order Markov process (Dodge and Jerse). The
brute-force approach to the composition using Markov chains usually centers
upon the creation of a transition table.

This table of arc-transition probabilities is usually sparse and so requires a program to perform access and computation with a large high-dimensioned matrix containing many zero elements. The probabilities assigned to the arcs may be arrived at by one of several methods. We use a technique of statistical analysis of an existing piece of music and have found this method described in the literature (Moore 1990).

The *order* of a Markov process indicates the amount of event memory that
the process has. For example, a 0th order Markov process has no event memory. A
1st order Markov process takes into account a single event and an Nth order
Markov process takes into account the last N events.

In order to perform the analysis of a melody, we convert the notes of a melody
into their corresponding pitch class. For example, in Louis Bonfi's *Black
Orpheus,* the notes are:

E, C, B, A, A, G#, B, E, E, C, B, A, A, G, B, E, E, F, G, A, D, D, D, E, F, G, C, C, C, D, E, F, B, B, C, D, E, E, C, B, A, A, G#, B, E, E, A#, A, G, G, F, E, A, D, D, E, F, G, C, C, D, E, A, G#, E, E, G#, B, A, E, A, A, B, C, D, C, B, A, B, C, D, C, B, A, B, C, D, C, B, A, G.

Converting into a pitch class requires that each note be assigned a number, for example:

[A A# B C C# D D# E F F# G G#] = [1 2 3 4 5 6 7 8 9 10 11 12]

*Black Orpheus* then becomes:

8, 4, 3, 1, 1, 12, 3, 8, 8, 4, 3, 1, 1, 11, 3, 8, 8, 9, 11, 1, 6, 6, 6, 8, 9, 11, 4, 4, 4, 6, 8, 9, 3, 3, 4, 6, 8, 8, 4, 3, 1, 1, 12, 3, 8, 8, 2, 1, 11, 11, 9, 8, 1, 6, 6, 8, 9, 11, 4, 4, 6, 8, 1, 12, 8, 8, 12, 3, 1, 8, 1, 1, 3, 4, 6, 4, 3, 1, 3, 4, 6, 4, 3, 1, 3, 4, 6, 4, 3, 1, 11.

The technique of converting a melody into its corresponding pitch class is not
new (Winsor 1987). These notes are placed into a file, called *notes * and
read into an array of integers called *note_array[i]*.

(1.3-3)

Assume that the occurrence of a note is an independent random event. We have
written a procedure which compiles a table that records the frequency of
occurrence into an array called the *pmf_array[i]*. Here, PMF is an
abbreviation for the *p*robability *m*ass *f*unction. This is a
statistical record of the frequency of occurrence of each note in the melody.
It is treated as a discrete probability distribution function so that

(1.3-4)

must be true.

We use the probability mass function array to bias our choice of a note by
picking a random number, *random_pick* such that

. (1.3-5)

We then compute the cumulative mass function by summing the elements of the
probability mass function array until they exceed *random_pick*. This is
shown in the following pseudo code.

Compute the probability mass function array, pmf_array

random_pick = random(0,1)

sum = 0

i = 1

repeat

sum = sum + pmf_array[i]

i = i + 1

until sum >= random_pick

play_note(i)

Figure 7. Code for computation of the PMF

Using first-order Markov processes requires that the transitions be used to compute a transition table which records the frequency of occurrence. Each element of the transition table represents a probability, we therefore create the transition table by summing the number of transitions for each row and then divide each element in the row by that sum. This "normalizes" the PMF's so that each row will sum to one, i.e.,

(1.3-6)

Figure 8 A Transition Table for a First-Order Markov Process

In general, as the order of the process increases, the sparsity of the matrix increases. Using this technique, a Nth order Markov Process requires an N+1 dimensioned transition table.

The transition table for a first-order Markov process description of *Black
Orpheus* appears in Figure 8. It is possible to transform this transition
table into a Markov diagram but the results are cluttered. The advantage of
using the transition table is that it provides a compact and convenient form
for representing and programming *first-order* stochastic processes. Using
this technique, a Nth order Markov Process requires an N+1 dimensioned
transition table.

Suppose we wish to compute Markov process probability tables from order 0 to 9
and store the results in the computer's memory (for the purpose of interactive
composition we use the numeric keypad numbers 0 to 9). In general, the number
of cells needed in all Nth order stochastic processes from 0..9 involving
*p* pitch classes has

(1.3-7)

elements when all the Nth order processes are stored in N+1-dimensioned matrices. Any attempt to reduce this number, f(12, 9) ~ 6.75x10^10, may be foiled by the introduction of pathologic data created by an advisary. For example, a large number of random numbers (much larger than the number of elements in the matrices) will eventually fill all the elements in the matrices. Never the less, it is practical, for low values of N, to perform the computation as described above. For example, the following code computes the 1st order Markov chain for Black Orpheus appears in Figure 9.

procedure compute_1st_order

begin

subtract the order number to keep the window from exceeding the number

of notes i.e., number_of_notes - order, note, the number_of_notes > order

with notes do

for each (note1 and note2) in (note_array[i] and note_array[i+1]) do

increment the number_of_2nd_order_event[note1,note2]

normalize the probs in the 1st order matrix

end

procedure play_first_order_stochastic_note;

begin

pick = random(0,1)

use the current row to perform a biased choice

play the choice and store the next element

end; {play_first_order_stochastic_note}

Figure 9. Code for Computation of 1st Order Stochastic Composition

Using this approach, we can implement a second order Markov process using the data structure shown in Figure 10.

second_order_markov_array_type = record

probability: array[1..11, 1..11, 1..11] of real;

used: array[1..11, 1..11] of boolean;

current_i, current_j: integer;

end;

Figure 10. Data Structure for a Second Order Markov Array

We would find (using 1.3-7) that a 9th order stochastic process over a 12 tone systems must make use of 6.75x10^10 elements. To make matters worse, using a matrix approach requires that we iterate over zero elements when computing the cumulative mass function. One objective (for the interactive realization of Markov processes on small computers) is to minimize the time it takes to compute a branch between nodes in the Markov chain.

Algorithms are available that implement sparse matrices with space proportional to the number of elements (Press et al.). These sparse-matrix approaches will reduce the amount of space needed, but cannot address the issue of execution time reduction. Since many visited states have zero probability (using the matrix approach) the time that the computer program takes to compute a branch cannot be predicted. We have found that this creates an uneven play back of the Markov chain during a real-time performance. This is a primary motivation for our approach which uses space which is linear in the number of Markovian states.

For the first-order stochastic process, shown above, the Petri-table appear in Figure 11.

The following program implements a second order Markov process using a
petri-net. *Transition probabilities* are defined as the conditional
probabilities between the states.

Name Place Enabling Tokens probability Next Place A p1 Ta 0.21052632 p1 A p1 Tb 0.15789474 p3 A p1 Td 0.10526316 p4 A p1 Te 0.05263158 p5 A p1 Tg 0.31578947 p6 A p1 Tg# 0.15789474 p7 A# p2 Ta 1 p1 B p3 Ta 0.46666667 p2 B p3 Tb 0.06666667 p3 B p3 Tc 0.26666667 p4

Figure 11 A Fragment of a First-Order Petri Net Table.

The zero elements of the Markov table are removed, reducing the time it takes to compute a branch. The number of rows is equal to the number of transitions.

In order to implement the Petri-table, and take full advantage of the fact that the number of elements in the table is linear in the number of transitions in the stochastic process, we need to write a program which can read Petri-tables directly. First we establish a Petri-table file format for a Markov-chain which appears as place, probability, next-place. The file format appears in Figure 12.

1 0.21052632 1 1 0.15789474 3 1 0.10526316 4 1 0.05263158 5 1 0.31578947 6 1 0.15789474 7 2 1.0 1 3 0.46666667 2Figure 12. The File Format for the Stochastic Petri Table.

The columns appear in the order of *place, probability, next-place*.

The data-structure used to store the Petri-net, with the next states and probability is shown in Figure 13.

type

{petri_markov data types}

petri_row_record = record

place: integer;

probability: real;

next_place: integer;

end; {petri_row_record}

row_array_type = array[1..35] of petri_row_record;

petri_type = record

row_array: row_array_type;

number_of_rows: integer;

current_place: integer;

end; {petri_array_type}

var

petri: petri_type;

The following pseudo code plays a row in the petri-table:

procedure play_petri_row (var petri: petri_type);

{play one row in the petri-table implementations of the first order Markov chain}

{these Markov chains of love, wont let me be, yeah!}

var

i: integer;

place_name: integer;

cmf: real;

prob_pick: real; {a number between 0 and 1}

while_loop_not_done: boolean;

begin

cmf = 0; {compute the cumulative probability mass function}

prob_pick = random(0,1)

while_loop_not_done := true;

with petri do

begin

i := current_place;

place_name := row_array[i].place;

with row_array[i] do

begin

while (place_name = place) and (cdf < prob_pick) do

begin

cmf := cmf + probability;

i := i + 1; {move to next row}

end; {while place_name}

make_tone(scale_array[i], tone_time);

current_place := next_place;

end; {with row_array[i]}

end; {with petri}

end; {play_petri_row}

Figure 13. Code to Define Stochastic Petric Table Data Type

Here, CMF stands for the cumulative probability mass function (computed by summing the probabilities of each of the transition arcs). To better understand the above program, recall the Petri-table file shown in Figure 12. To play one row, we first pick a pseudo-random number from 0 to 1, inclusive. We then transition from one row of the Petri table to the next until the cumulative mass function exceeds our probability pick, when this occurs, we take the transition to the next place.

In case the cumulative mass function does not sum to one (due to round-off error), we provide a compound conditional in the while loop, "(place_name = place) and (cmf < prob_pick)", this keeps us within the petri-table row.

The Petri table is a faster method for realizing Markov chains than the Markov table because of the elimination of the zero elements. It would be even faster to store the cumulative mass function, rather than the probability mass function. This saves a floating-point addition as the program iterates over each element in the Petri-table. The transition matrix requires 144 reals for a first-order Markov process. The Petri table needs only 66 integers and 33 reals. Assuming that an integer is 2 bytes long and that a real is 4 bytes, there are 144x4 bytes per real or 576 bytes used for the Markov transition table and 66x2+33x4 = 264 bytes for the Petri table. This saving grows as an exponential function of the order of the Markov process.

Suppose we use the *Black Orpheus* example to compute a 2nd-order Markov
chain. In order to speed execution, and eliminate the sparse matrices, we use a
Petri-net. A partial Petri net implementation of a Markov chain is shown in
Figure 12.

Figure 12 A Partial Stochastic Petri Net

The transition probabilities are shown on each arc. They indicate the probability of the occurrence of a token.

Here, we note that each of places has a transition probability that sums to one. Let R= row number of the Petri-table. N1, N2 and N3 = note 1 note 2 and note 3. Pijk is the probability that note k will occur given the occurrence of notes i and j. A partial Petri-table is shown in Figure 16.

R N1 N2 N3 Pijk

Figure 16. Partial Stochastic Petri Table

*R* is the row number of the table. *N1* and *N2* are two notes
in the history of the Markov chain. *N3* is the next note in the chain and
*Pijk* is the probability that *N3* will occur given the occurrence
of notes *N1 *and *N2.*

In order to play such a table, a program must jump to a row given two notes. A
procedure picks a uniformly distributed random number that varies from 0 to 1
(called *r, * this is created using linear congruential generator with a
long period) (L'Ecuyer 1993). The procedure then sums the probabilities to form
the *c*umulative *m*ass *f*unction (CMF). When the CMF exceeds
*r*, the value for the next state, *k*, is obtained.

In Petri-net parlance, *k* is a token that appears with a given
probability. Note number two becomes the new note number one. *K* becomes
the new note number two. An array (called the *indirection array*) gives
us a pointer to the beginning of the list of places that start with note number
1.

An example indirection array is shown in Figure 17:

Figure 17 The Indirection Array.

The first element indicates the next note's pitch class. The second element points to the row in the Petri table the pitch class may be found. This keeps the procedure from having to perform a search for the next pitch class.

We have implemented 5th order stochastic processes using Petri nets. After that, the 100 note example tends to be deterministic.

In the future, we should eliminate the computation of the cumulative mass function by storing the cumulative mass function rather than the probability mass function. This should save the cost of an addition during the branching computation. In addition, we think that the computation of the stochastic Petri table may be made faster than the present implementation.

This author believes that the Markov chain method of computation may be of use in the area of animation and, in particular, dance. On this topic, as on many others relating to the use of stochastic Petri nets in the arts, much work remains to be done.

The source and Macintosh compiled version of the code for the program described in this article is available from the author for a 10$ fee to cover the cost of shipping and handling. It is also available through ftp to the site cse.bridgeport.edu.

Finally, I wish to acknowledge the debt I have to the late Mike Torello, who died while this paper was being written. Co-performer/Co-Composer and friend, Mike's influence and enthusiasm were infectious. He continues to be missed.

Apple. 1987. *Apple Technical Introduction to the Macintosh Family*. New
York, New York: Addison-Wesley Publishing Company, Inc. , pp. 22, 169, 172.

Baggi, D. 1991. "Computer-Generated Music." *Computer*. 24(7):6-9.

Batish, S.D., and A. Batish. 1989. *Ragopedia Volume 1*. 1316 Mission St.,
Santa Cruz, California 96060: Batish Publications.

Dodge, C., and T. Jerse. 1985. *Computer Music*. New York, New York:
Schimer Books.

Kassler. 1994. "Machine Models of Music." *SIGART Bulletin*. ACM Press,
5(1):51-52.

Katz, R. 1994. *Contemporary Logic Design*.. New York, New York:
Benjamin/Cummings Publishing Company, Inc.

L'Ecuyer, P., F. Blouin, and R. Couture. 1993. "A Search for Good Multiple
Recursive Random Number Generators." *ACM Transactions on Modeling and
Computer Simulation*.. 3(2): 87-98.

Moore, F. R. 1990. *Elements of Computer Music*. Englewood Cliffs, New
Jersey: Prentice Hall.

O'Haver, T. 1978. "More Music for the 6502." *Byte*. Peterborough, New
Hampshire: Byte Publications, Inc., 3(6):140-141

Peterson, J. 1977. "Petri Nets." *ACM Computing Surveys*. 9(3):223-252.

Press, W., S. Teukolsky, W. Vetterling, and B. Flannery. 1992. *Numerical
Recipes in C*. Cambridge, Massachusetts: Cambridge University Press.

Ralston, A. 1983. *Encyclopedia of Computer Science and Engineering*.
Second Edition, , NY, NY: Van Nostrand Reinhold Company.

Randel, D. 1990. *Harvard Concise Dictionary of Music*. The Belknap Press
of Cambridge, Massachusetts: Harvard University Press.

Roads, C., and J. Strawn, Eds. 1985. *Foundations of Computer Music.
*Cambridge, Massachusetts: MIT Press.

Schwanauer, S., and D. Levitt. 1993. *Machine Models of Music*. Cambridge,
Massachusetts: MIT Press.

Symantec Corporation. 1991.*Think Pascal(TM) User Manual*. Cupertino,
California.

The International MIDI Association. 1990. *Midi 1.0 Detailed
Specification*.. 5316 W. 57th St., Los Angles, California 90056,
(213)649-6434: International MIDI Association.

Winsor, P. 1987. *Computer-Assisted Music Composition*.. Princeton, New
Jersey: Petrocelli Books.