Monthly Archives: December 2021

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.)

Continue reading →

The Eudoxus reals

Let’s call a function f : {\mathbb Z} \to {\mathbb Z} a near-endomorphism of \mathbb Z if there is a constant C>0 such that |f(a+b)-f(a)-f(b)| \leq C for all a,b \in \mathbb Z. The set of near-endomorphisms of \mathbb Z will be denoted by N. We put an equivalence relation \sim on N by declaring that f \sim g iff the function f-g is bounded, and let {\mathbb E} denote the set of equivalence classes.

It’s not difficult to show that defining f+g in terms of pointwise addition and f \cdot g in terms of composition of functions turns {\mathbb E} into a commutative ring. And it turns out that this ring has a more familiar name… Before reading further, can you guess what it is?

Continue reading →

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.

Continue reading →

Firing games and greedoid languages

In an earlier post, I described the dollar game played on a finite graph G, and mentioned (for the “borrowing binge variant”) that the total number of borrowing moves required to win the game is independent of which borrowing moves you do in which order. A similar phenomenon occurs for the pentagon game described in this post.

In this post, I’ll first present a simple general theorem due to Mikkel Thorup which implies both of these facts (and also applies to many other ‘chip firing games’ in the literature). Then, following Anders Björner, Laszlo Lovasz, and Peter Shor, I’ll explain how to place such results into the context of greedoid languages, which have interesting connections to matroids, Coxeter groups, and other much-studied mathematical objects.

Continue reading →