# Counting with martingales

In this post I will provide a gentle introduction to the theory of martingales (also called “fair games”) by way of a beautiful proof, due to Johan Wästlund, that there are precisely $n^{n-2}$ labeled trees on $n$ vertices.

Apertif: a true story

In my early twenties, I appeared on the TV show Jeopardy! That’s not what this story is about, but it’s the reason I found myself in the Resorts Casino in Atlantic City, where the Jeopardy! tryouts were held (Merv Griffin owned both the TV show and the casino). At the time, I had a deep ambivalence (which I still feel) toward gambling: I enjoyed the thrill of betting, but also believed the world would be better off without casinos preying on the poor and vulnerable in our society. I didn’t want to give any money to the casino, but I did want to play a little blackjack, and I wanted to be able to tell my friends that I had won money in Atlantic City. So I hatched what seemed like a failsafe strategy: I would bet $1 at the blackjack table, and if I won I’d collect$1 and leave a winner. If I lost the dollar I had bet in the first round, I’d double my bet to $2 and if I won I’d stop playing and once again leave with a net profit of$1. If I lost, I’d double my bet once again and continue playing. Since I knew the game of blackjack reasonably well, my odds of winning any given hand were pretty close to 50% and my strategy seemed guaranteed to eventually result in walking home with a net profit of $1, which is all I wanted to accomplish. I figured that most people didn’t have the self-discipline to stick with such a strategy, but I was determined. Here’s what happened: I lost the first hand and doubled my bet to$2. Then I lost again and doubled my bet to $4. Then I lost again. And again. And again. In fact, 7 times in a row, I lost. In my pursuit of a$1 payoff, I had just lost $127. And the problem was, I didn’t have$128 in my wallet to double my bet once again, and my ATM card had a daily limit which I had already just about reached. And frankly, I was unnerved by the extreme unlikeliness of what had just happened. So I tucked my tail between my legs and sheepishly left the casino with a big loss and nothing to show for it except this story. You’re welcome, Merv.

Martingales

Unbeknownst to me, the doubling strategy I employed (which I thought at the time was my own clever invention) has a long history. It has been known for hundreds of years as the “martingale” strategy; it is mentioned, for example, in Giacomo Casanova‘s memoirs, published in 1754 (“I went [to the casino of Venice], taking all the gold I could get, and by means of what in gambling is called the martingale I won three or four times a day during the rest of the carnival.”) Clearly not everyone was as lucky as Casanova, however (in more ways than one). In his 1849 “Mille et un fantômes”, Alexandre Dumas writes, “An old man, who had spent his life looking for a winning formula (martingale), spent the last days of his life putting it into practice, and his last pennies to see it fail. The martingale is as elusive as the soul.” And in his 1853 book “Newcomes: Memoirs of a Most Respectable Family”, William Makepeace Thackeray writes, “You have not played as yet? Do not do so; above all avoid a martingale if you do.” (For the still somewhat murky origins of the word ‘martingale’, see this paper by Roger Mansuy.)

# Calendar Calculations with Cards

As readers of this previous post will know, I’m rather fond of mental calendar calculations. My friend Al Stanger, with whom I share a passion for recreational mathematics, came up with a remarkable procedure for finding the day of the week corresponding to any date in history using just a handful of playing cards. What’s particularly noteworthy about Al’s algorithm is that it involves no calculations whatsoever, and the information which needs to be looked up can be cleanly displayed on one of the cards.

When you work through Al’s procedure, it will feel like you’re performing a card trick on yourself – you will be amazed, surprised, and will likely have no idea how it works. I’ve never seen anything quite like this before, and I’m grateful to Al for allowing me to share his discovery with the public for the first time here on this blog.

# An April Fools’ Day to Remember

Today is the 10th anniversary of the death of Martin Gardner. His books on mathematics had a huge influence on me as a teenager, and I’m a fan of his writing on magic as well, but it was only last year that I branched out into reading some of his essays on philosophy, economics, religion, literature, etc. In this vein, I highly recommend “The Night Is Large”, a book of collected essays which showcases the astonishingly broad range of topics about which Martin had something interesting to say. It’s out of print, but it’s easy to find an inexpensive used copy if you search online.

Thinking back on my favorite Martin Gardner columns, my all-time favorite has to be the April 1975 issue of Scientific American. In that issue, Martin wrote an article about the six most sensational discoveries of 1974. The whole article was an April Fools’ Day prank: among the discoveries he reported were a counterexample to the four-color problem and an artificial-intelligence computer chess program that determined, with a high degree of probability, that P-KR4 is always a winning move for white. The article also contained the following:

# A Very Meta Monday

Usually my blog posts are rather tightly focused, but today I’d just like to post a few stream-of-consciousness thoughts.

(1) My blog was recently featured in the AMS Blog on Math Blogs. Perhaps by mentioning this here I can create some sort of infinite recursion which crashes the internet and forces a reboot of the year 2020.

# Mental Math and Calendar Calculations

In this previous post, I recalled a discussion I once had with John Conway about the pros and cons of different systems for mentally calculating the day of the week for any given date. In this post, I’ll present two of the most popular systems for doing this, the “Apocryphal Method” [Note added 5/3/20: In a previous version of this post I called this the Gauss-Zeller algorithm, but its roots go back even further than Gauss] and Conway’s Doomsday Method. I personally use a modified verison of the apocryphal method. I’ll present both systems in a way which allows for a direct comparison of their relative merits and let you, dear reader, decide for yourself which one to learn.

# Some Mathematical Gems from John Conway

John Horton Conway died on April 11, 2020, at the age of 82, from complications related to COVID-19. See this obituary from Princeton University for an overview of Conway’s life and contributions to mathematics. Many readers of this blog will already be familiar with the Game of Life, surreal numbers, the Doomsday algorithm, monstrous moonshine, Sprouts, and the 15 theorem, to name just a few of Conway’s contributions to mathematics. In any case, much has already been written about all of these topics and I cannot do justice to them in a short blog post like this. So instead, I’ll focus on describing a handful of Conway’s somewhat lesser-known mathematical gems.

# Zero Knowledge Identification and One-Way Homomorphisms

Sounds too good to be true, right?

In fact, such password schemes do exist, and they’re quite easy to implement. They are known as zero knowledge authentication systems. In this post, I’ll explain the main idea behind such protocols using the notion of a “one-way homomorphism”. Before diving into the technicalities, though, here’s a useful thought experiment which conveys the main idea.

# Complementary sets of natural numbers and Galois connections

In this post, I’d like to discuss a beautiful result about complementary sets of natural numbers due to Lambek and Moser. I first learned about their theorem as a high school student (from Ross Honsberger’s delightful book “Ingenuity in Mathematics”), but it’s only more recently that I learned about the “Galois” connection.

To motivate the discussion, consider the following question. Let $F = \{ 0,1,4,9,16,25,\ldots \}$ be the sequence of squares, and let $G = \{ 2,3,5,6,7,8,10,\ldots \}$ be its complement in ${\mathbb N} = \{ 0,1,2,3,\ldots \}$. What is the $n^{\rm th}$ term of the sequence $G$? In other words, can we give a formula for the $n^{\rm th}$ non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the $n^{\rm th}$ non-square is equal to $n + \{ \sqrt{n} \}$, where $\{ x \}$ denotes the closest integer to $x$. Similarly, if $T = \{ 0,1,3,6,10,\ldots \}$ denotes the set of triangular numbers, the $n^{\rm th}$ element of the complement of $T$ is equal to $n + \{ \sqrt{2n} \}$.

# p-adic Numbers and Dissections of Squares into Triangles

My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog).  One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post).  Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry. Continue reading

# John Nash and the theory of games

John Forbes Nash and his wife Alicia were tragically killed in a car crash on May 23, having just returned from a ceremony in Norway where John Nash received the prestigious Abel Prize in Mathematics (which, along with the Fields Medal, is the closest thing mathematics has to a Nobel Prize). Nash’s long struggle with mental illness, as well as his miraculous recovery, are depicted vividly in Sylvia Nasar’s book “A Beautiful Mind” and the Oscar-winning film which it inspired. In this post, I want to give a brief account of Nash’s work in game theory, for which he won the 1994 Nobel Prize in Economics. Before doing that, I should mention, however, that while this is undoubtedly Nash’s most influential work, he did many other things which from a purely mathematical point of view are much more technically difficult. Nash’s Abel Prize, for example (which he shared with Louis Nirenberg), was for his work in non-linear partial differential equations and its applications to geometric analysis, which most mathematicians consider to be Nash’s deepest contribution to mathematics. You can read about that work here. Continue reading

# Post-Cherylmania wrap-up

My last post was about “Cheryl’s birthday puzzle”, which recently became an internet sensation.  I mentioned several additional puzzles in that post and promised solutions; here they are.

Let me begin, though, with a “cryptography” variant of the Cheryl puzzle which was sent to me by my friend and puzzle guru Pete Winkler:

Cheryl’s birthday possibilities are now May 14 or 15, June 15 or 16, July 16 or 17 or August 14 or 17. Albert gets the month and Bernard the day as before, and they both want to find out the birthday.  But Eve, who’s listening in, mustn’t find out.  How can A and B, who’ve never met before (and aren’t cryptographers), accomplish this mission?

Think about it, it’s a fun little puzzle!  [Pete writes in addition: “You can also do this with a cycle of 5 months (10 dates total) but then you need a coin to flip.”]

My Meta-Cheryl Challenge (as revised on April 20) was to come up with a list of dates for which the following puzzle will have a unique solution:

# Cherylmania

Many of you have undoubtedly heard by now the math puzzle about Cheryl’s birthday which has been sweeping across the internet.  I appeared on CNN on Wednesday to explain the solution — here is a link to the problem and my explanation.  Since that appearance, I’ve received dozens of emails about the problem and/or my explanation of it.   I thought I’d share a few of my thoughts following this flurry of activity. Continue reading

# A motivated and simple proof that pi is irrational

Today is 3/14/15 — Super Pi Day — so was I telling my 7-year-old son all about the number $\pi$ this afternoon.  When I told him that $\pi$ keeps on going forever and ever he asked “How do you know that?”  Although I don’t know a proof that I could explain to a 7-year-old, I wanted to record the following proof which uses only basic calculus.  It is essentially Niven’s famous proof, as generalized by Alan Parks, but I have tried to write it in a way which is more motivated than the usual treatments.  As a bonus, the proof also shows that e is irrational.

# Spooky inference and the axiom of choice

A large crowd had gathered in Harvard Square, and I was curious what all the cheering and gasping was about.  Working my way through the crowd, I saw a street performer who (according to the handwritten red letters on his cardboard sign) went by the name “Zorn the Magnificent”.  He displayed a large orange, borrowed an extremely sharp knife from his assistant, and proceeded to chop the orange into five exotic-looking pieces while standing on one hand.  Working with almost unfathomably deft precision, he rearranged the pieces into two oranges, each the same size as the original one.  The oranges were given out for inspection and the crowd cheered wildly.  I clapped as well — even though I was familiar with the old Banach-Tarski paradox — since it was nevertheless an impressive display of skill and I had never seen it done one-handed before.  I heard a man with a long white beard whisper to the woman next to him “He hides it well, but I know that he’s secretly using the Axiom of Choice.” Continue reading

# Real Numbers and Infinite Games, Part II

In my last post, I wrote about two infinite games whose analysis leads to interesting questions about subsets of the real numbers.  In this post, I will talk about two more infinite games, one related to the Baire Category Theorem and one to Diophantine approximation.  I’ll then talk about the role which such Diophantine approximation questions play in the theory of dynamical systems.

The Choquet game and the Baire Category Theorem

The Cantor game from Part I of this post can be used to prove that every perfect subset of ${\mathbf R}$ is uncountable.  There is a similar game which can be used to prove the Baire Category Theorem.  Let $X$ be a metric space.   In Choquet’s game, Alice moves first by choosing a non-empty open set $U_1$ in $X$.  Then Bob moves by choosing a non-empty open set $V_1 \subseteq U_1$.  Alice then chooses a non-empty open set $U_2 \subseteq V_1$, and so on, yielding two decreasing sequences $U_n$ and $V_n$ of non-empty open sets with $U_n \supseteq V_n \supseteq U_{n+1}$ for all $n$.  Note that $\bigcap U_n = \bigcap V_n$; we denote this set by $U$.  Alice wins if $U$ is empty, and Bob wins if $U$ is non-empty. Continue reading