Random Walk: A New Method for Aleatoric Musical Composition

Year: 2025 Authors: Ranger Liu

Core claim

Random walks on piece-level and measure-level graphs can generate a structured aleatoric composition and related physical artworks.

Topics

aleatoric composition, random walks, graph-based music, physical process, multi-output artwork

Domains

graph theory, random walks, Markov chains, experimental music, sound art, installation art, book/score visualization

Methods

mathematical definition, graph construction, random walk sequencing, physical yarn-and-paper procedure, digital image stitching

Media

yarn, paper, piano score, black string, digital composite image

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2025 Conference Proceedings

Random Walk: A New Method for Aleatoric Musical Composition

Ranger Liu

Seattle, WA, USA; rangerliu.mailbox@gmail.com

Abstract

This paper presents a new method for composing aleatoric (chance-based) music by performing multiple random walks through mathematical graphs constructed from existing musical scores. I introduce a mathematical definition of this technique and then describe a physical procedure for performing this process with yarn and paper, which I used to create a 19-movement composition for piano as well as multiple additional artistic outputs.

Figure 1: An installation created by physically performing the random walk compositional process.

Introduction

Aleatoric music is a type of music in which some compositional decisions are determined by chance operations [3]. Examples include Mozart’s Musikalisches Würfelspiel (1792), which used dice throws to sequence existing measures of music [4], and John Cage’s Music of Changes (1951), which used the Chinese divinatory text I Ching to sequence elements from prepared charts of sounds, durations, and dynamics [3].

In the 1960s and 70s, Iannis Xenakis pioneered stochastic music, a subfield of aleatoric music, which uses stochastic processes to generate music. In his 1971 work for solo violin, Mikka, Xenakis used a random walk on note pitches to create continuous glissandi, with the violinist sliding continuously between discrete pitches generated by the random walk. Xenakis went on to compose a number of other works using random walks on pitch and duration to generate both linear (single-track) and textural (multi-track) sequences [2].

In this paper, I present a new method for aleatoric composition by performing multiple random walks through mathematical graphs constructed from existing musical scores. I first give a mathematical definition of this composition process, detailing 1) its source material; 2) its devised structure, which organizes the source material; and 3) its sequencing procedure, which selects and orders elements of the source material from within the devised structure. I then describe my physical implementation of this process using yarn and paper to compose a 19-movement work for piano, eponymously titled RANDOM WALK. Finally, I describe the many additional artistic outputs of this physical process, including the art shown in Figures 1, 5, and 6.

Mathematical Definition of Random Walk Composition

Source Material

We begin by selecting existing musical pieces for source material. These pieces can be of any genre, for any instrument, as long as their scores contain discreme measures.

Let $N$ be the number of source pieces in the set $\mathcal{P}=\{P_1,P_2,...,P_N\}$ of all source pieces. For each piece $P_i$, let $x_i$ be the number of measures in the sequence $M_i=m_i^1,m_i^2,...,m_i^{x_i}$ of all ordered measures in that piece. Then, for each piece $P_i$, pick a number $y_i$ with $0<y_i\le x_i$, and select $y_i$ distinct measures from $M_i$. Without loss of generality, we may reassign indices to write this set of chosen measures as

$C_i=\{m_i^1,m_i^2,...,m_i^{y_i}|m_i^j\in M_i\}$ (1)

Our source material then consists of the set $\mathcal{P}$ of $N$ source pieces and the $N$ sets $C_i$ of $y_i$ chosen measures. As an example, let’s consider an implementation using $N=3$ pieces, all of length $x_i>3$ measures, and choose $y_1=y_2=y_3=3$ measures from each piece. Then our source material is defined as $\mathcal{P}=\{P_1,P_2,P_3\}$ and the 3 sets $C_1=\{m_1^1,m_1^2,m_1^3\}$, $C_2=\{m_2^1,m_2^2,m_2^3\}$, and $C_3=\{m_3^1,m_3^2,m_3^3\}$, as in the top of Figure 2.

Devised Structure

Next, we construct $N+1$ graphs to organize our source material. Recall that a simple graph has unweighted, undirected edges with no loops or duplicate edges, and a connected graph includes a path between all possible pairs of vertices. Recall also that the valency of a vertex is the number of edges connected to that vertex, and wo vertices are neighbors if they are connected by an edge. Finally, recall that a graph is regular if all its vertices have the same valency.

First, construct $\Phi (\mathcal{P},E)$ to be a simple, connected, and regular graph, with pieces $P_i\in \mathcal{P}$ as vertices, a set of edges $E$, and each vertex $P_i$ with valency $\rho$. Note that the valency $\rho$ must satisfy that the product $N\rho$ is even, to ensure simple connectivity. Then, let $N_{\Phi }(P_i)$ denote the set of $\rho$ neighbors of a vertex $P_i\in \mathcal{P}$.

Next, for all $1\le i\le N$, construct ${\Omega }_i(C_i,{ϵ}_i)$ to be a simple, connected, and regular graph, with chosen measures $m_i^j\in C_i$ as vertices, a set of edges ${ϵ}_i$, and each vertex $m_i^j$ with valency ${\eta }_i$. Similarly, this valency number ${\eta }_i$ must satisfy that the product $y_i{ϵ}_i$ is even, to ensure simple connectivity. Then, let $N_{{\Omega }_i}(m_i^j)$ denote the set of ${\eta }_i$ neighbors of a vertex $m_i^j\in C_i$.

Our source material is now organized into one piece-level graph $\Phi$ and $N$ measure-level graphs ${\Omega }_i$. For our example, the middle panel of Figure 2 shows the 4 graphs $\Phi$, ${\Omega }_1$, ${\Omega }_2$, and ${\Omega }_3$ constructed with chosen valencies $\rho ={\eta }_1={\eta }_2={\eta }_3=2$.

Sequencing Procedure

Finally, we define our sequencing procedure, which consolidates the results of $N+1$ random walks into a single sequence of measures. Recall that a random walk on a graph can be thought of as “visiting” vertices one by one, with the next visited vertex randomly chosen from the neighbors of the previous vertex [1].

A random walk on a graph is typically denoted as a Markov Chain, given by a sequence of dependent random variables $X_1$, $X_2$, …, $X_t$ with some probability distribution function describing the dependence of each visited vertex $X_T$ on the previous visited vertex $X_{T-1}$ [1].This formulation can be thought of as capturing all possible random walks, as it does not specify any particular vertex for each $X_T$. In this paper, I will instead use an “after completion” perspective to notate one particular random walk on a graph as the fixed sequence of specific visited vertices in one completed walk.

With this in mind, let $\mathcal{R}$ be a $k$-step random walk completed on the piece-level graph $\Phi$, given by the sequence of visited vertices

$\mathcal{R}(\Phi )={\psi }_1,{\psi }_2,...,{\psi }_k$ (2)

where

Random Walk: A New Method for Aleatoric Musical Composition

Without loss of generality, we define ${\psi }_1=P_1$ to be the starting vertex of $\mathcal{R}(\Phi )$, and each subsequent ${\psi }_j$ is chosen randomly from the set $N_{\Phi }({\psi }_{j-1})$ of the previous vertex’s neighbors for all 1 &lt; j \leq k. The value of $k$ may be arbitrarily chosen and typically represents the total number of measures in the composition.

Next, for each measure-level graph ${\Omega }_i$, let ${\mathcal{B}}_i$ be an $q$-step random walk completed on ${\Omega }_i$ given by

Similarly, we define ${\delta }_i^1=m_i^1$ to be the starting vertex of ${\mathcal{B}}_i({\Omega }_i)$ without loss of generality, and for all 1 &lt; j \leq q, each subsequent ${\delta }_i^t$ is chosen randomly from the set $N_{{\Omega }_i}({\delta }_i^{j-1})$ of the previous vertex’s neighbors. Here, the value of $q$ is unimportant, which is discussed later. For now we can simply set $q=k$.

Finally, we consolidate these $N+1$ random walks into a final sequence of measures $S=s_1,s_2,\dots ,s_k$. We define the $j$th sequenced measure as

Here $i$ is defined by ${\psi }_j=P_i$, then $\tau$ is defined as the number of times the vertex $P_i$ has been visited at step ${\psi }_j$ in random walk $\mathcal{R}(\Phi )$, and finally ${\delta }_i^{\tau }=m_i^{\nu }$ is the measure $m_i^{\nu }$ chosen at step $\tau$ of random walk ${\mathcal{B}}_i({\Omega }_i)$.

$\Phi$

$\mathcal{R}(\Phi )={\psi }_1,{\psi }_2,{\psi }_3,{\psi }_4$

${\Omega }_2$

${\Omega }_1$

${\Omega }_3$

Figure 2: An example composition: (top) source material; (middle) the piece-level graph $\Phi$ and the measure-level graphs ${\Omega }_1$, ${\Omega }_2$, and ${\Omega }_3$, with random walks $\mathcal{R}$, $B_1$, $B_2$, and $B_3$ traced in red and written out explicitly; (bottom) the final sequence of measures $\mathcal{S}$.

209

The middle panel of Figure 2 shows the random walks $\mathcal{R}(\Phi )$, $B_1({\Omega }_1)$, $B_2({\Omega }_2)$, and $B_3({\Omega }_3)$ for our example, with walk lengths set to $k=q=4$. Each walk is marked in red on their corresponding graph, starting from the starred vertex, and their visited vertices are explicitly written to the right of each graph. The bottom of Figure 2 also shows the final sequence $\mathcal{S}$ formed by consolidating these random walks using equation 4, as explained below.

For $j=1$, we have ${\psi }_1=P_1$, so $i=1$. Now $P_1$ has been visited once, so $\tau =1$. Then $s_1=d_1^1=m_1^1$.

For $j=2$, we have ${\psi }_2=P_2$, so $i=2$. Now $P_2$ has been visited once, so $\tau =1$. Then $s_2=d_2^1=m_2^1$.

For $j=3$, we have ${\psi }_3=P_1$, so $i=1$. Now $P_1$ has been visited twice, so $\tau =2$. Then $s_3=d_1^2=m_1^3$.

For $j=4$, we have ${\psi }_4=P_3$, so $i=3$. Now $P_3$ has been visited once, so $\tau =3$. Then $s_4=d_3^1=m_3^1$.

Thus the final composition in this example is the sequence of measures $\mathcal{S}=m_1^1$, $m_2^1$, $m_1^3$, $m_3^1$.

Stepwise Sequencing

This sequencing procedure can also be explained as a two-step loop, where the random walks are created concurrent to—rather than before—the final sequence $\mathcal{S}$. For each measure $s_j$, the piece-level random walk $\mathcal{R}(\Phi )$ is first stepped one vertex forward to select a piece ${\psi }_j=P_i$. Then, this piece’s measure-level random walk ${\mathcal{B}}_i({\Omega }_i)$ is stepped one vertex forward to find the measure $s_j={\delta }_i^{\tau }=m_i^v$. These two steps repeat to find all measures $s_j$. In this formulation, we only need to keep track of each random walk’s current vertex, and we stop looping these two steps once the final sequence reaches our desired length $k$.

This stepwise formulation also clarifies why the value of $q$, the length of each measure-level random walk, is unimportant: as long as $q$ is “big enough,” it is unlikely that any piece $P_i$ will be revisited more than $q$ times during random walk $\mathcal{R}(\Phi )$. In any case, $q$ can be increased to extend the measure-level walks if necessary by simply visiting more vertices.

Stopping Criteria & Flexibility

Note that in the stepwise formulation, the number of steps $k$ in the piece-level random walk $\mathcal{R}(\Phi )$ acts as a “stopping criteria” that tells us to stop random-walking once the composition has reached length $k$. We could also set different stopping criteria: for instance, stop when every piece $P_i$ has been visited at least once in random walk $\mathcal{R}(\Phi )$; or, stop when every measure $m_i^j$ has been sequenced at least once in the final composition $\mathcal{S}$. These potential changes illustrate the intended flexibility of this compositional method. Here I’ve written a strict definition of random walk composition, but any of these rules may be modified at will, as demonstrated in the following section.

Physical Implementation of Random Walk Composition

This section describes my physical implementation of the previous mathematical definition to compose a 19-movement work for piano, eponymously titled RANDOM WALK.

Source Material

I chose $N=19$ existing pieces from the Western-classical piano repertoire, selecting pieces that I played as a child. A full list of these pieces can be found at [5]. I then chose between 6 and 13 measures from each piece.

Devised Structure

To construct the piece-level graph $\Phi (\mathcal{P},E)$ shown in Figure 3a, I randomly arranged the titles of each piece $P_i\in \mathcal{P}$ on a sheet of paper using brad fasteners and glue. I then created the edges $E$ by running a white string between brads until I reached my chosen valency number $\rho =4$ for all vertices. Using one continuous length of string ensured that the graph was connected. I also avoided creating duplicate edges or self-loops, and the white string did not indicate direction or weight, ensuring that the graph was simple.

Random Walk: A New Method for Aleatoric Musical Composition

(a)

(b) Figure 3: Constructed graphs: a) the piece-level graph $\Phi$ with piece names as vertices and strings as edges, and b) the measure-level graph ${\Omega }_1$ for piece $P_1$ , with measures as vertices and strings as edges.

The 19 measure-level graphs ${\Omega }_i$ were similarly constructed, with ${\Omega }_1$ shown in Figure 3b. For each graph ${\Omega }_i(C_i,{ϵ}_i)$ , I used glue and brad fasteners to arrange each chosen measure $m_i^j\in C_i$ on a sheet of paper, and then created edges ${ϵ}_i$ with one continuous white string until I reached the valency number ${\eta }_i$ for all vertices. I chose valencies of either ${\eta }_i=3$ or ${\eta }_i=4$ for each measure-level graph.

Modifications to Sequencing Procedure

I first modified my stopping criteria. Instead of choosing an overall number of measures $k$ , I decided to compose 19 movements with 19 measures each, requiring that the first measure of each movement should come from the same piece as the last measure of the previous movement. To capture this modification mathematically, recall that the completed piece-level random walk $\mathcal{R}$ is given by

with ${\psi }_1=P_1$ . We set $k=361$ and require that ${\psi }_j={\psi }_{j-1}$ for all $j$ in 1 &lt; j &lt; k where $(j\mathrm{mod}19)=1$ . The remaining ${\psi }_u$ are then chosen randomly from the set $N_{\Phi }({\psi }_{u-1})$ of the previous vertex’s neighbors, as usual.

I also added physical randomization to shuffle groups of notes within each measure. I printed out each chosen measure $m_i^j$ , cut it in half horizontally to separate right-hand and left-hand notes, and cut each half into note-groups based on my musical intuition, as in Figure 4a. I then placed each chopped-up measure into a labeled paper envelope. For each measure in the sequence $S$ , I shook out the measure’s chopped-up pieces to get a physically randomized version of the measure to use in the final composition, as shown in Figure 4b.

The mathematical representation of this “chop-up randomization” process is left as an exercise to the reader (hint: use partitions). For brevity, I will simply add an additional step to the sequencing procedure: after consolidating the final sequence $S=s_1,s_2,\dots ,s_k$ of sequenced measures, create a transformed sequence $S^{\ast }=s_1^{\ast },s_2^{\ast },\dots ,s_k^{\ast }$ by applying chop-up randomization to every sequenced measure $s_j$ .

Implementation of Sequencing Procedure

Instead of performing 20 separate random walks and then consolidating their results, I performed a physical version of the aforementioned step-wise process in which the piece-level random walk $\mathcal{R}(\Phi )$ is stepped forward to choose a source piece ${\psi }_j=P_i$ , and then that piece’s measure-level random-walk $B_i({\Omega }_i)$ is stepped forward to choose the next measure $s_j={\delta }_i^{\tau }=m_i^{\nu }$ in the composed sequence $S$ . A timelapse video of this process can be found at [5], which may be useful in visualizing the description below.

Liu

(a)

(b) Figure 4: Chop-up randomization: a) the measure $s_1$ split first in half (red) to separate right- and left-hand notes, and then into groups (blue) based on my musical intuition; b) the transformed measure $s_1^{\ast }$ with blocks arranged after being physically shaken out.

I first affixed each measure-level graph ${\Omega }_i$ to a wall and chose a starting vertex ${\delta }_i^1=m_i^1$ for each measure-level random walk $B_i({\Omega }_i)$ . I marked these starting measures with a length of black string. I then chose a vertex ${\psi }_1=P_1$ to start my piece-level random walk $\mathcal{R}(\Phi )$ . I picked a color of yarn to represent the first movement and tied a length of this yarn to the vertex $P_1$ on the piece-level graph $\Phi$ . I then tied a separate, second length of yarn to the starting vertex ${\delta }_1^1=m_1^1$ of the random walk $B_1({\Omega }_1)$ . Finally, I shook out the envelope for measure $m_1^1$ to physically randomize its notes. I took a picture of this randomized arrangement, shown in Figure 4b, thus creating the first measure $s_1^{\ast }$ in the transformed sequence $S^{\ast }$ .

For the remaining measures of the first movement, I repeated four steps:

1. step forward in the piece-level random walk $\mathcal{R}(\Phi )$ by stringing the first length of yarn to a new piece-level vertex ${\psi }_j=P_i$ , choosing $P_i$ randomly from the set $N_{\Phi }({\psi }_{j-1})$ of the neighbors of ${\psi }_{j-1}$ ;
2. step forward in the measure-level random walk $B_i({\Omega }_i)$ by stringing the black string to a new measure-level vertex ${\delta }_i^{\tau }=m_i^{\nu }$ , choosing $m_i^{\nu }$ randomly from the set $N_{{\Omega }_i}({\delta }_i^{\tau -1})$ of the neighbors of ${\delta }_i^{\tau -1}$ ;
3. also string the second length of yarn to that measure-level vertex $m_i^{\nu }$ , thus marking $s_j={\delta }_i^{\tau }=m_i^{\nu }$ to keep track of the consolidated sequence of measures $S$ ; and finally
4. shake out the envelope for the measure $m_i^{\nu }$ and take a picture of this transformed measure $s_j^{\ast }$ .

At the end of each movement, I tied off both lengths of yarn to their last vertices, $P_e$ and $m_e^d$ . To start each new movement, I performed slightly modified versions of steps 1 and 3, with steps 2 and 4 the same:

1a. Pick a new color of yarn for this movement and tie a first length of new-colored yarn to the same piece-level vertex $P_e$ from the end of the previous movement; 3a. tie a second length of new-colored yarn to the selected measure-level vertex $m_i^{\nu }$ .

I then repeated the original steps 1-4 to create the remaining measures of each movement.

Artistic Outputs

This physical implementation of random walk composition creates several artistic byproducts alongside the final musical composition. First, we have the wall installation shown in Figure 1, where the consolidated sequence of measures $S$ is represented in the paths of colored yarn, and the measure-level random walks $B_i({\Omega }_i)$ are represented in the paths of black string on each measure-level graph ${\Omega }_i$ .

Random Walk: A New Method for Aleatoric Musical Composition

Second, we have the piece-level graph $\Phi$ with its random walk $\mathcal{R}(\Phi )$ visualized in layers of colored yarn, one for each movement. The yarn I used was too thick to keep all 19 layers on at once, so I organized the movements into 4 cycles of 4 movements each, plus 1 cycle of 3 movements at the end, and removed all the yarn before the start of a new cycle. The piece-level graph is shown in Figure 5, after Cycle I.

Figure 5: The piece-level graph $\Phi$ after Cycle I, with 4 layers of yarn showing the random walk $\mathcal{R}(\Phi )$ .

Third, we have the pictures of each transformed measure $s_i^{\ast }$ . I digitally stitched all 361 of these images into one composite image, shown in Figure 6, with each movement represented as one row.

Fourth, we have the physical performance of undertaking this procedure, which I videotaped in its entirety of about 15 hours. An edited timelapse of the composition process can be found at [5].

Finally, we have the composition itself, consisting of 361 transformed measures $s_i^{\ast }$ . The fully transcribed human-readable score and a partial recording of the piece as performed by myself can be found at [5].

Conclusion

In this paper, I presented a mathematical definition and physical implementation of a new method for aleatoric composition using random walks through graphs constructed from existing musical scores. This method creates multiple artistic outputs alongside the musical composition, and it presents many exciting avenues for more potential modifications and extensions. For instance, instead of physically randomizing the notes within each measure, note-level graphs may be constructed for each measure, on which a third level of random walks may be performed. Graphs may also be constructed and walked to sequence dynamics, time signatures, note durations, or any other elements of a musical composition. Finally, the stepwise formulation of the sequencing procedure may easily be converted into a computational program, which would enable exploration of high volumes of large-scale compositions using the random walk technique.

Acknowledgments

Many thanks to Iris Rosenblum-Sellers and Pip Petersen for help with notation, terminology, and clarity.

Liu

Figure 6: All 361 transformed measures $s_i^{\ast }$ laid out in a grid, with each movement represented as one row.

References

[1] S. Arora and B. Barak. Computational Complexity: A Modern Approach, Draft ed. 2007. https://theory.cs.princeton.edu/complexity/. [2] J. Harley. Random Walk. https://www.iannis-xenakis.org/en/random-walk/. [3] E. Jones. 11.3: Aleatoric Music. https://human.libretexts.org/Bookshelves/Music/Music_Appreciation/Music_Appreciation I (Jones) /11%3A_20th_Century-_Aleatoric_Electronic_and_Minimalist_Music/11.03%3A_Aleatoric_Music. [4] E. C. Keppelmann. “Mozart’s Dice Game.” Joint Mathematics Meetings, January 8 2025. [5] R. Y. Liu. RANDOM WALK. https://ryurongliu.com/random-walk.