# 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 $$\left(\frac{1}{3}\right)^{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 $$\left(\frac{2}{3}\right)^{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:$$

Cantor with $$n = 6:$$

Inverted Cantor:

Cantor with the modulation factor as a perfect fourth:

A mash-up of many of these ideas:

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

(Note: Once again, I’ve coded all the musical examples in Gamma.

# 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:

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:

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

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

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.

# Lessons from a grandmaster

The next game is the only tournament game I’ve ever played against a grandmaster. My opponent was Georgian GM Mikheil Kekelidze. Not surprisingly, he outplayed me in every phase of the game. Obviously, I’ve still got a lot of work to do!

 [Event "Marchand Open"] [Site "Rochester, NY"] [Date "2012.05.30"] [Round "3"] [White "Mikheil Kekelidze"] [Black "Aaron Demby Jones"] [Result "1-0"] [WhiteELO "2563"] [BlackELO "2106"] 1.d4 Nf6 2.c4 e6 3.Nf3 c5 {Not my usual repertoire, but I hadn't been getting good results with the Queen's Indian Defense lately.} 4.d5 exd5 5.cxd5 d6 6.h3 {White plays to increase the value of his space advantage by avoiding trades. (His move prevents a future Bc8-g4.)} 6...g6 7.e4 Bg7 ( 7...Nxe4 $4 8.Qa4+ ) 8.Bd3 O-O 9.O-O Re8 {Pressuring the e-pawn.} 10.Nc3 {White defends. Now Black has to figure out how to develop his remaining minor pieces. It's always a struggle in the Modern Benoni.} 10...a6 {The start of the typical queenside expansion plan.} 11.a4 {The usual reply. White has no hurry in this position and first plays to restrict Black's possibilities before embarking on his own plans.} 11...Nbd7 {A bit clumsy, but there was no clear alternative.} 12.Bf4 {White puts his finger on Black's awkward coordination. The d6-pawn needs defense.} 12...Qc7 {An undesirable move from a future tactical point of view. (See White's 17th move.)} 13.Re1 Nh5 {Dangerous, since if White lands g2-g4 at the right moment, Black will lose a lot of time.} ( 13...Rb8 ) ( 13...b6 ) 14.Bh2 Ne5 ( 14...Bh6 {was an interesting alternative.} ) 15.Be2 {Retaining the bishop pair and threatening Nf3xe5, discovering an attack on the knight on h5.} 15...Nxf3+ 16.Bxf3 Nf6 {Forced. Now Black has traded off a pair of knights but at the cost of time.} 17.e5$1 {Very energetic play. White takes advantage of Black's unfortunate queen placement.} 17...dxe5 18.d6 {The point.} 18...Qb6 19.Bxe5 Be6 $2 ( 19...Bd7 {was necessary to keep the rook eyeing the bishop on e5.} ) 20.a5$1 Qb4 ( 20...Qxb2 $2 21.Nd5 {and White wins. Had Black played 19. ... Bd7, this resource would not be available to White.} ) 21.Ra4 Bb3 {The point of 19. ... Be6. But this is based on faulty calculation.} 22.Rxb4 {Starting a favorable forcing sequence.} 22...Bxd1 23.Rxb7 Bxf3 24.gxf3 Nh5 {I had foreseen this sequence on move 19 and thought that I was winning material here. However...} 25.Re7 {... I overlooked this defense in my calculations. White has won a clean pawn.} 25...Red8 26.Ne4 Bxe5 27.Rxe5 f5 {Trying to eliminate the dangerous d-pawn.} 28.Nxc5 Rxd6 29.Re6 Rxe6$2 {Overly cooperative.} ( 29...Rd2 30.Rxa6 Rxa6 31.Nxa6 Rxb2 {and Black has some chances to draw.} ) 30.Rxe6 Nf4 {Black no longer has any meaningful counterplay. White is clearly winning now.} 31.Rxa6 Rd8 32.Ne6 Rd1+ 33.Kh2 Nd3 {Desperately hoping for some sort of mating net.} 34.Rd6 $1 {A nice tactical solution. White forces trades.} 34...Re1 35.Rd8+ Kf7 36.Ng5+ Kf6 37.Nxh7+ Kg7 38.Rxd3 Kxh7 39.a6 {And I resigned. White's pawn promotes without much resistance.} ( 39.a6 Ra1 ( 39...Re7 40.Ra3 Ra7 41.b4 Kg7 42.b5 Kf7 43.b6 ) 40.Ra3 ) 1-0  # 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.  [Event "Grand Prix"] [Site "Rochester, NY"] [Date "2011.02.10"] [Round "3"] [White "Aaron Demby Jones"] [Black "Anna Levina"] [Result "1-0"] [WhiteElo "2106"] [BlackElo "2111"] [ECO "D31"] [PlyCount "85"] [Variant "Standard"] [Opening "Semi-Slav Defense: Accelerated Move Order"] 1.d4 d5 2.c4 e6 3.Nc3 c6 4.e3 Bd6 5.Nf3 Nd7 6.e4 {Since Black isn't playing her knight out to f6, why not?} 6...dxe4 7.Nxe4 Bb4+ 8.Bd2 Bxd2+ 9.Qxd2 {The trade of these bishops seems to help White, since Black's remaining bishop is worse than White's.} 9...Ndf6 10.Nc3 {Trying to make Black suffer from redundant knights.} 10...Ne7 11.Be2 ( 11.Bd3 {looks more aggressive.} ) 11...O-O 12.O-O Qc7 13.Rad1 Ng6 14.Rfe1 b6 {Black plans to slowly unroll with Bc8-b6, c6-c5, etc.} 15.b3$6 {White drifts here for a few moves.} 15...Bb7 16.Qb2 $6 Nf4 17.c5$1 {White wakes up and plays with a plan. Black's bishop shall not free itself so easily after all.} 17...Nxe2+ $6 {This trade doesn't seem to help Black much. White can easily end up with a favorable knight vs. bishop scenario.} 18.Qxe2 bxc5 19.dxc5 Qa5 20.Qe3 Nd5 21.Nxd5 exd5 22.b4$1 {A rather deep pawn sacrifice.} 22...Qxa2 23.Nd4 Rab8 {If Black passes, say, with} ( 23...h6 {, White wins material via} 24.Ra1 Qc4 25.Rec1 Qxb4 26.Rab1 ) 24.Nf5 {The knight, having feinted to the queenside, now goes for the throat on the kingside.} 24...Qb2 25.Rd4 {Blocking the line and threatening Qe3-e5.} 25...Bc8 26.Nxg7 $6 {A tactical solution, but simpler was} ( 26.Ne7+ Kh8 27.Nxc6 {and Black's position collapses.} ) 26...Kxg7 27.Qg5+ Kh8 28.Qf6+ Kg8 29.Rg4+ Bxg4 30.Qxb2 {After the dust clears, White has a queen against rook and bishop. As usual, the queen manages to prove superior by exploiting the color complex opposite the bishop.} 30...a5 31.Qf6 Rxb4 32.h3 {Getting some luft with tempo.} 32...Be6 33.Re3 Rfb8 34.Qh6 {Trying to keep the king cornered by cutting off f8.} 34...Bf5 {Intending Bf5-g6, plugging up the g-line.} 35.h4 {Trying to cross her plans with h4-h5.} 35...Rb3 36.Rxb3 Rxb3 37.Qg5+ Bg6 38.h5 {The bishop is caught. But all of a sudden, Black is whipping up some counterplay with a passed a-pawn.} 38...a4 39.h6$1 {The 'drive-by' in action! White doesn't need to capture the bishop. The pawn is actually more valuable in this position since it coordinates in deadly fashion with the queen on the dark squares.} 39...f6 40.Qxf6 Rb7 41.Qxc6 Rb1+ 42.Kh2 Ra1 \$2 {Losing on the spot, but otherwise White wins easily by pushing the c-pawn.} 43.Qf6 {Black resigns. Qf6-g7 mate can't be stopped. A thematic finish!} 1-0 

My chessvideos.tv analysis can be found here.

# Probability and number theory, part II

In this post, we will explore the following question: If we choose two integers uniformly at random, what is the probability that they are relatively prime?

We start with a preliminary result. The Riemann zeta function, $$\zeta(s)$$, is ubiquitous in number theory. Although the most interesting version of it is the complex-valued one, today we only need the real version. It is defined as follows: for any real number $$s$$ greater than $$1,$$

$$\zeta(s) = \displaystyle\sum_{n=1}^{\infty} n^{-s}$$.

The Euler product  for the zeta function is the following alternative expression:

$$\zeta(s) = \displaystyle\prod_{p} \frac{1}{1 – p^{-s}},$$

where the product is taken over every prime $$p$$. To see why this formula is true, we start with the right-hand side and use a geometric series expansion to obtain

$$\displaystyle\prod_{p}\frac{1}{1-p^{-s}}=\displaystyle\prod_{p}(1+p^{-s}+p^{-2s}+\cdots).$$

By the Fundamental Theorem of Arithmetic, every positive integer can be expressed as a unique product of primes, up to order. (We consider $$1$$ to be the product of no primes; i.e., the empty product.) Thus, there is a one-to-one correspondence between the terms in the sum $$\sum_{n=1}^{\infty} n^{-s}$$ and the terms in the expansion of the product $$\prod_{p}(1+p^{-s}+p^{-2s}+\cdots).$$ Hence,

$$\displaystyle\prod_{p}\frac{1}{1-p^{-s}}=\displaystyle\sum_{n=1}^{\infty}n^{-s}=\zeta(s).$$

Now back to our original problem! Suppose we choose $$a, b \in \mathbb{Z}$$ uniformly at random. Fix an arbitrary prime $$p$$. The probability that both $$a$$ and $$b$$ are divisible by $$p$$ is $$\left(\frac{1}{p}\right)\left(\frac{1}{p}\right) = p^{-2}$$. Hence, the probability that they are not both divisible by $$p$$ is $$1 – p^{-2}$$.

The condition that $$a$$ and $$b$$ are relatively prime is equivalent to the condition that, for every prime $$p$$, $$a$$ and $$b$$ are not both divisible by $$p$$. Furthermore, for distinct primes $$p$$ and $$q$$, the events that $$a$$ and $$b$$ are not both divisible by $$p$$ and $$a$$ and $$b$$ are not both divisible by $$q$$ are mutually independent. (In fact, more precisely, the events that $$a$$ and $$b$$ are not both divisible by $$m$$ and $$a$$ and $$b$$ are not both divisible by $$n$$, for relatively prime integers $$m$$ and $$n$$, are mutually independent.)

Thus, the probability that $$a$$ and $$b$$ are relatively prime is equal to

$$\displaystyle\prod_{p}(1-p^{-2}),$$

where the product is taken over every prime $$p$$. But

$$\displaystyle\prod_{p}(1-p^{-2}) = \displaystyle\prod_{p}(\frac{1}{1-p^{-2}})^{-1}=(\displaystyle\prod_{p}\frac{1}{1-p^{-2}})^{-1} = \frac{1}{\zeta(2)}.$$

Hence the answer is $$\frac{1}{\zeta(2)}\approx 0.608. \, \spadesuit$$

The closed-form expression for $$\zeta(2)$$ is actually well-known (it equals $$\frac{\pi^{2}}{6})$$, but that’s another story for another day. The result also generalizes to more than two integers, a nice exercise for the reader.