Musical Cantor

Cantor’s ternary set, or more briefly, the Cantor set, is a well-known construction that illustrates some interesting topological properties of the real numbers. To describe it briefly, we define an iterative process as follows: Let C_0 be the interval from 0 to 1. Then C_1 is obtained by removing the middle third from C_0 , leaving the two intervals from 0 to \frac{1}{3} and \frac{2}{3} to  1 . The set C_2 is obtained by removing the two middle thirds from C_1 . So C_2 will then contain four intervals, each of length \frac{1}{9}. In general, the set C_n will contain 2^{n} intervals, each of length (\frac{1}{3})^{n} . The Cantor set, denoted C , is then defined as

C=\displaystyle\bigcap_{n=0}^{\infty} C_n.

The Cantor set satisfies many curious properties. For instance, in a certain sense, it has length zero. This is more or less because at stage n , it has a total length of (\frac{2}{3})^{n} , which approaches 0 as n approaches infinity. However, from the perspective of cardinality, it can be shown that the Cantor set is uncountable. This is actually fairly simple to see, using the following argument. In order to be an element of the Cantor set, you must be a member of every set C_n . Going from C_0 to C_1 , you have to be either ‘left’ or ‘right’ of the middle third. Let’s say hypothetically that you are ‘left.’ Then going from C_1 to C_2 , again, you must be either ‘left’ or ‘right’ of the middle third. It’s clear that this process repeats indefinitely. If we represent ‘left’ and ‘right’ by 0 and 1 , then we see that elements of the Cantor set can be put into one-to-one correspondence with infinite binary sequences. Thus, by Cantor’s diagonal argument, the Cantor set must be uncountable. So although it has measure zero, it is an uncountable set!

One can also try to “hear” the Cantor set in the following way. Start with a particular frequency, let’s say, middle C. Define C_0 as sustaining that frequency for some duration, let’s say, one second. Then choose an interval of modulation, for instance, a tone. Then C_1 would be the triplet D-C-D, since we have modulated the outer thirds by a tone. We can proceed similarly to the general form of C_n , and in principle, we could even define the full Cantor set C , although it would be difficult to program. The following audio tracks illustrate a few of these ideas.

Here’s Cantor for n = 0, 1, 2, 3, 4:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Cantor with n = 6:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Inverted Cantor:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Cantor with the modulation factor as a perfect fourth:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

A mash-up of many of these ideas:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

I hope this post allows you to hear the Cantor set better!

(Note: Once again, I’ve coded all the musical examples in Gamma. You can check out the code through my programming page.)

Rhythm and Frequency

If you happen to have a subscription to JSTOR, Karlheinz Stockhausen’s 1962 article “The Concept of Unity in Electronic Music” is a classic explanation of some of the concepts I’m about to describe. It turns out that some musical parameters, such as rhythm and frequency, are in fact manifestations of one underlying mathematical principle.

Consider a simple rhythm, for instance, a pulse that divides a second into three equal beats. We can view the speed of this rhythm as 3 Hz. If we speed this pulse up until it is several hundred Hz, we will no longer process it as a rhythm but instead as a pitch with a frequency, as the following audio example demonstrates:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

More interestingly, suppose we take a polyrhythm. That is, we take a single pulse, let’s say, 1 Hz, and divide it evenly into two different parts. One of the simplest possibilities is a 3:2 pattern, which would initially start out as a 3 Hz : 2 Hz ratio. Again, if we speed this polyrhythm up until it is several hundred Hz, our brains begin to perceive the rhythm as frequency. In particular, we will hear a perfect fifth, since the ratio of the frequencies is 3:2. Try to determine in the middle of the following audio example where you stop perceiving the sounds as a rhythm and start perceiving them as frequency:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Here’s a similar example, but with a 4:3 ratio, so that the frequencies play a perfect fourth:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

And the irresistible 6:5:4 ratio, which produces a major triad:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

It may seem counterintuitive, but these examples demonstrate that rhythm and frequency are in a certain sense the same concept. It’s merely our perception of them that varies.

(Note: I’ve coded all the musical examples in Gamma.)

Finite ant crawling

Here’s another example of recursive probability in action on a different problem.

Suppose you are an ant crawling along the edges of an equilateral triangle ABC . You start at point A . Every minute, you choose uniformly at random one of the other two vertices and move to it. What is the probability that you return to where you started (point A ) after exactly twelve minutes?

Well, okay, at first the question seems hard to grasp, so let’s try to approach it by first tackling simpler questions. What is the probability that you return to where you started after exactly one minute? Zero, since you can only make one move. Well that didn’t work! How about after two minutes? Now we’re getting somewhere, since you can do this via two different paths: one through point B and one through point C. There are four total paths you could take, so the probability in this case must be \frac{1}{2} . Just out of curiosity/completeness, we could also ask ourselves what the probability of arriving at point B or point C is after two moves. By symmetry, these probabilities must be the same, and their sum, together with the probability of arriving at point A after two moves, must be 1. Hence, they must each have probability \frac{1}{4} .

Believe it or not, we’re already in a position to solve the original problem! The key is to think recursively. With this in mind, let p_{k} denote the probability of returning back to where you started after 2k minutes. We already know that p_1 = \frac{1}{2}. For k greater than 1 , we want to relate p_k to p_{k-1} . In other words, once you’ve made 2k - 2 steps, what is the probability that after taking two more steps, you are back to where you started?

This depends on where you are after 2k - 2 steps. So we can just break it down into all the cases! You’re at point A with probability p_{k-1} , and from here, the probability of taking two more steps and getting back to point A is simply \frac{1}{2} as we computed before. You’re at either of points B or C with a sum total of probability 1 - p_{k-1} , and from each of those cases, the probability of taking two more steps and getting back to point A is \frac{1}{4} , also as calculated before. So we are finally in a position to write down our recursive equation:

p_k = \frac{1}{2}p_{k-1} + \frac{1}{4}(1 - p_{k-1})

Simplifying,

p_k = \frac{1}{4}(p_{k-1} + 1).

Thus, turning the crank a few times, starting with p_1 = \frac{1}{2} , we get p_2 = \frac{3}{8}, p_3 = \frac{11}{32}, p_4 = \frac{43}{128}, p_5 = \frac{171}{512}, and finally, p_6 = \frac{683}{2048}. (Note that our final answer is very close to \frac{1}{3} , which makes intuitive sense.)

There are actually many other ways to approach the same problem (one could, for instance, create a transition matrix), but this one is very simple and clean. In fact, it’s not too hard from here to come up with an explicit formula for p_k and prove that it is correct via induction. (A good exercise!)

Infinite coin flipping

Suppose Alice and Bob decide to play the following simple game: they alternate turns flipping a coin, and whoever gets heads first immediately wins. (Alice gets the privilege of going first.) What are Alice’s chances of winning this game?

To make it more general, let’s suppose the coin is heads with probability x , where 0 \le x \le 1 . There are two approaches to solving this problem. Let’s look at the ‘brute force’ way first. Alice only gets to flip the coin on the first, third, fifth, seventh, … turns. Thus, her chances of winning the game must be equal to the infinite sum of her chances of winning on each of those respective turns. On the first turn, her chance of winning is x . In order to win on turn three, all previous flips must have been tails. Thus, her chances of winning in this case are (1-x)^{2} x . Similarly, on turn five, her chances of winning are (1-x)^{4} x , and this suggests that on turn 2n + 1 , her chances of winning are (1-x)^{2n} x . Thus, her chances of winning the game in total are

\displaystyle \sum_{n=0}^{\infty} (1-x)^{2n} x.

This is a geometric series with first term x and ratio (1-x)^{2} , so it is equal to \frac{x}{1 - (1-x)^{2}} = \frac{x}{2x - x^{2}} = \frac{1}{2 - x}. So for instance, if the coin is fair, x = \frac{1}{2} and Alice’s chances of winning are \frac{1}{2 - \frac{1}{2}} = \frac{2}{3}.

While this approach certainly was successful, let’s look at a slicker alternative. Starting over, let’s denote the probability that Alice wins the game by P . Then of course the probability that Bob wins the game is 1 - P . Instead of putting ourselves in Alice’s shoes, let’s pretend for a minute that we are Bob. Suppose Alice goes first and throws tails. Now, as Bob, we are pretty happy! It’s almost as though we get to go first now …

Well wait a minute, it is exactly as though we get to go first now! This observation actually tells us something: the original probability of Bob winning the game must be equal to the probability of Alice winning the game while first throwing tails. In equations, this means that (1 - P) = P(1 - x) . Now we can simply solve for P :

1 = P(1-x) + P

1 = P(2 - x)

So P = \frac{1}{2-x} , just as before. (Notice that our answer makes intuitive sense: as x \searrow 0 , Alice’s probability of winning approaches \frac{1}{2} from above, and as x \nearrow 1 , Alice’s probability of winning approaches 1 from below.)

This approach to probability is essentially recursive, and we’ll see more of it in the next post.

Computer Music 3

For my final sound synthesis project, I wrote a more substantial electronic piece, using several different instruments (subtractive synthesis, plucked string, frequency modulation, and vibrato). It’s called “Dilate.” You can listen to it here:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

And read more about it here, if you like:

“Dilate” notes

Computer Music 2

Here is another piece I wrote in Gamma, this time with a frequency modulation instrument. It’s called “Boom/Bust.”

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Computer Music

I’ve recently been writing brief electronic pieces for a sound synthesis course. The software I have used is called Gamma, a C++ library developed by the people in the Media Arts and Technology program at UCSB. Here’s one of my pieces, called “Breeze,” written for a simple vibrato instrument.

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Bishop stifling

I played the following game with the White pieces against WFM Anna Levina. The middlegame shows the thematic idea of playing with a good knight against a bad bishop. The finale shows off a beautiful twist on the same idea.

My chessvideos.tv analysis can be found here.