Order Out of Chaos

I’ve loved mathematics for most of my life. The last year he home-schooled me, my father taught me - as he relearned - Euclidean geometry from the Schaum’s outline. This was how I learned about proof: how to find a sequence of observations that left no doubt about a conclusion. I found the hunt for these sequences, and the process of refining them into the most concise form possible, deeply satisfying. The idea that there were some truths that were absolutely certain thrilled me. Most of the math I learned subsequently in middle and high school was really just rote arithmetic at its core, but I loved that too, juggling numbers and letters and finding answers. It’s about as similar to proving theorems as solving crossword puzzles is to short story writing, but I enjoy both of those as well.

My next real taste of wrestling with math was at the Evergreen State College, in the year-long Computability and Cognition course taught by Al Leisenring and Sherri Shulman. The philosophy thread was interesting, and learning to program in Prolog was a treat, but the real standout for me was the section on mathematical logic and formal language theory, a sort of extension of the ideas of basic logic in a similar vein to abstract algebra’s extension of the ideas of arithmetic. What I learned there and what I’ve built on it since still inform my thinking about everything related to programming, mathematics, and logic.

During this time I came closest, I think, to thinking I could maybe Be A Real Mathematician. It was often a fantasy of mine, and still is sometimes. Usually I’m quite happy to acknowledge that my life has taken me in other directions, and let math be one of many joys in my life that I can engage with or put down when the mood strikes me, but in my year-and-a-bit at Evergreen I dreamed a bit more deeply for a while, and it was lovely.

It was also during this time that I came closest to creating a really new bit of math, when I discovered some interesting properties of random sequences that were first discovered in my lifetime. Granted, the one reference to the subject I managed to find was from a paper published when I was just a year old or so, but still! It was quite exciting.

As with many mathematical concepts, this one may be most easily conveyed in the form of a game. The first version goes like this:

1. You and I each simultaneously pick a sequence of N heads and tails.
2. We then flip a fair coin N times to construct a random sequence.
3. If that sequence matches one of our sequences, that person wins! If not, we go back to 2.

(There’s not much of a game here if we pick the same sequence, of course, but we can require them to be different.)

Now, I don’t think it will come as much surprise that there’s no strategy to this game. It doesn’t matter what sequence either of us picks - in the long run, we’ll each win about the same number of times. Every sequence of N heads and tails is equally likely to be constructed by N fair coin flips, practically by definition.

Since there’s not much excitement in this game, let’s at least make it faster. Rather than constructing whole sequences every time, let’s just add a new coin flip to our existing sequence every time and use the last N flips as our target. Whoever’s sequence comes up first wins. So if I pick HHT and you pick THH, we might flip H, T, H, H, H, T, and then I win. Or we could flip T, T, H, T, H, H and you win.

Version two here is still a fair game, but there is now a strategy, in the sense that some choices are better than others. With N=4, for instance, playing each pair of sequences against each other many times, the highest-scoring sequence gets about 5/3 as many wins as the lowest-scoring. With N=5 it’s closer to 3/2.

Now, if we introduce a little asymmetry into the game we can uncover an even more interesting property. In version three, player one picks a sequence and shows it to player two; player two then chooses their sequence. In this version, player two always has an advantage! In other words, this game is non-transitive: knowing what sequence you’ve chosen, I can always choose another that’s likely to come up first more often. The first player’s strategy is to choose a sequence with the best worst case. For N=4, the best player one can manage is to win about 36% of the time.

There are some more interesting properties of this game, and another formulation that makes it a bit clearer why some sequences are better than others, which I’ll write about some day, maybe.