Beyond the Transition Matrix: A Language-Independent, String-Based Input Notation for Incomplete, Multiple-Order, Static Markov Transition Values Christopher Ariza Abstract: While Markov chain generators have been employed throughout the history of computer music as a tool for the creation of musical parameter values, input notations for Markov transition values are often cumbersome and opaque. Rejecting the transition matrix as an input notation, this paper offers a new language-independent, string-based input notation for incomplete, multiple-order, static Markov transition values. Transition values are given greater generality by accommodating multiple orders simultaneously, as well as the specification of transitions with the use of limited single-operator regular expressions. A complete Python implementation of this model is introduced, and high-level utilities and object interfaces are demonstrated in athenaCL. 1. Introduction Throughout the history of computer music Markov chain generators have been employed as a tool for the creation of musical parameter values. There are two common approaches to configuring these Markov processors. In the first case, a data sequence is analyzed, and then the resulting transition data is stored in a transition matrix and used to generate new values. In the second case, transition values are directly specified without derivation from analysis. In both cases, an intuitive and transparent notation of transition values, beyond the common tabular matrix, is advantageous. In the second case, a practical notation for Markov transition values offers a powerful and efficient input notation for a wide range of Markov applications. Rejecting the transition matrix as an input notation, this paper offers a language-independent, string-based input notation for incomplete, multiple-order, static Markov transition values. Transition values are given greater generality by accommodating multiple orders simultaneously, as well as the specification of transitions with the use of limited single-operator regular expressions. A complete Python implementation of this model is introduced, and high-level utilities and object interfaces are demonstrated in athenaCL (Ariza 2005). These specialized object interfaces offer flexible rhythm and parameter value generation. Additionally, the use of dynamic Markov order values is shown to offer a flexible and previously unexplored resource. As Charles Ames states, “by no means can Markov chains be said to occupy the cutting edge of progress in automated composition…” (1989, p. 186). A Markov-based generator, further, has well-known limitations: it is “incapable of generating self-embedded structures” (Cohen 1962, p. 155) and, in general, “… is not complete enough by itself to consistently produce high quality music” (Moorer 1972, p. 111). Nonetheless, Markov chains offer a practical tool: they can be used to generate any type of value or value collection, they are discrete, they offer greater control than uniform randomness, and, at higher orders, they produce sequentially related structures. This practicality, however, is often encumbered by the parametric complexity of the traditional transition 1 [email protected]. A challenge of computer-aided algorithmic composition (CAAC) system design is the reduction of parametric complexity. This challenge can be met in part by the development of intuitive, flexible, and language-independent string notations. Such notations permit the user to supply complex specifications within a single argument, rather than supplying numerous arguments to a function or text-entry form. 2. The Markov Chain and the Markov Transition String A Markov chain, as used here, is a technique for generating a one-dimensional series of values or symbols based on probabilities, where probabilities for each possible outcome are selected based on zero or more past symbol formations. The number of past symbols a Markov chain uses to specify a new symbol is the “order” of the Markov chain. In the case of orders greater than zero, it is useful to label these past values as a “source,” and the probabilities as directing to possible “destinations” (Ames 1989, p. 175). Source formations are referred to as “transitions.” The history of Markov models is well documented in the mathematical and scientific literature (Norris 1998, Bermaud 1999). Their origins are traced to their namesake, Russian mathematician A. A. Markov (1856-1922). While some recent research has explored the Hidden Markov Model (HMM) and the Markov Chain Monte Carlo, this article focuses only on the conventional Markov “chain”: a discrete-time stochastic process. Only Markov chains with finite state spaces (or a finite collection of possible symbols) are considered. While Markov chains are frequently displayed with various state diagrams or as directed graphs, are often presented in the context of random walks, and are frequently defined as regular (type 3) finite state grammars (Roads 1984, p. 14), this discussion will only consider elementary models. A Markov chain will be defined with a new string notation. This notation encodes key and value pairs with brace-delimited values. For example, a key “x,” assigned a value of 0.3, is notated as x{0.3}. Multiple key and value pairs can be defined in sequence without the use of spaces or commas: x{0.3}y{0.7}. A Markov chain produces output based on examination of zero or more past symbols. A zeroth order Markov chain thus examines zero previous values; a third order Markov chain examines three previous values. A “transition” defines a possible past symbol formation. Thus, a second order Markov chain with two symbols (x, y) must define four transitions, or the possible past symbol formations x:x, x:y, y:x, y:y (where “:” separates past symbols, and symbols read from left to right as most remote to most recent). For each transition, probabilities may be assigned for the generation of a new symbol. These probabilities may be specified as weights or as unit-interval proportions. In the notation presented here, weights are defined by providing a destination symbol, an “=” sign, and a numeric value; multiple weights, separated by the “|” symbol, may be specified. Continuing the example above, the y:x transition may define an equal probability of producing either symbol “x” or “y” with the following notation: x:y{x=1|y=1}. Alternatively,