Record-breaking Collatz chains!

One of my favorite bits of mathematics is the Collatz conjecture. It’s so simple that you can explain it to any grade schooler, and yet is so mysterious that Paul Erdös declared “Mathematics may not be ready for such problems.”

Here’s the conjecture:

Take any natural number N. If this number is even, divide it by two. If on the other hand N is odd, we multiply it by three and add 1. So N becomes N/2 if N is even, and 3N+1 if N is odd. Now, repeat this process for the resulting number! If even, divide by two. If odd, multiply by three and add one. And then repeat with the new number, and keep on chugging away.

The conjecture is that you will always eventually get to 1 (regardless of the initial value of N!)

That’s it! It’s that simple. Here are some examples:

Say we start with N=2. Since 2 is even, we divide by 2 and get 1. And that’s that, we’re done!

What if we start with N=3? Now, since 3 is even, we must multiply by three and add 1. So 3 becomes 10. 10 is even, so we divide by 2 to get 5. And 5 is odd, so we multiply by three and add one to get 16. And lo and behold, 16 goes to 8, which goes to 4, which goes to 2, and then back down to 1!

Here’s a table of the first few “Collatz sequences”:

Screen Shot 2019-06-11 at 10.37.52 PM.png

A few comments:

First, if you look closely, you’ll notice that there’s a lot of repetition in that list. For instance, look at the chain that starts at 9. It ends up at 7 after just three steps. And then the whole rest of the chain is identical to the one two above it! And starting at 10, one step takes us to 5, the chain of which we had already calculated.

This hints that any method for calculating the Collatz sequences of numbers could likely benefit from dynamic programming: using the work you’ve previously done to make your future tasks quicker. Think about it, by calculating the chains of just the numbers 3 through 10, we’ve also managed in the process to figure out the exact chains for 11, 13, 14, 16, 17, 20, and more numbers up to 52!

Second comment: Notice that these chains look really weird. They jump up and down unpredictably, and their lengths are all over the place. Here’s what the “9” chain looks like as it jumps up and down:

Screen Shot 2019-06-11 at 10.46.17 PM.png

And, to take an even more dramatic example, here’s what the chain starting with 27 looks like:


That takes 111 steps to stop! And in the process, it rises as high as 9,232!

Based on this example, you might be thinking that these chains are in general going to increase faster than their starting value. But don’t be deceived: I cherry-picked 27 because I knew that it would generate an interesting long chain. In fact, the lengths of the chains are in general remarkably small relative to their starting value. Here’s a plot of the first 100 chain lengths:


Though the values are growing, and some of them are up in the 100s, most of them are in the sub-40 range.

If you’re like me, though, you might notice some very curious patterns in this graph. What’s going on with those clusters of three or two that keep showing up right beside each other? And why do we seem to have these two distinct “regions” of chain lengths? Let’s look to see if these patterns persist as we plot the chain lengths for higher values, this time up to 1000:


Interesting! So it appears like the “two regions” kind of blend together, but this pattern of strings of nearby numbers with similar chain lengths stays the same! This is extremely mysterious to me. Many of the time the specific paths the numbers take on their way to zero are quite different, so why should we see them having the same length?

Well, part of the answer might be that in fact, the paths taken by nearby numbers are sometimes actually not too different at all. For instance, 500 and 501 both take 110 steps to get to 1, but their chains become identical after just four steps. Let’s look closely at these steps:

500 becomes 250 becomes 125 becomes 376
501 becomes 1504 becomes 752 becomes 376

Let’s look in general at what happens to N and N+1 if they follow this exact sequence of moves:

N becomes N/2 becomes N/4 becomes 3N/4 + 1
N+1 becomes 3(N+1) + 1 becomes (3(N+1) + 1)/2 becomes (3(N+1) + 1)/4

But hold on: (3(N+1) + 1)/4 just is 3N/4 + 1! So in fact, we should expect that whenever we do these sequences of moves, N and N+1 will have the same chain length. And when does this happens? Well, N had to be divisible by 4 but not 8. And 3N + 4 had to be divisible by 4. This specific set of conditions is true for about 1/8 of all numbers, so this already tells us that at least 1/8 of neighboring numbers have the same length!

And this was only looking at chains that became identical after three steps! We could go further and look at other possible sequences of moves that would make our chains become identical quickly, and in the process get a better understanding of the structure of the graph.

By the way, want to see how this graph behaves for even larger starting values? Here ya go! N up to 10,000:


Our N has 10-tupled, but our chain lengths have barely increased at all! Same for N up to 100,000:


Same story! Increasing our N by a factor of 10 seems to really only increase our chain lengths by adding about 100! This indicates that the relationship between starting value and chain length might be logarithmic (a multiplicative increase in starting value corresponding to an additive increase in chain length). Let’s look at a semilog plot of the same range of starting values:


Wow! This exposes a whole new level of structure in the chain lengths. Look at all those parallel lines of clusters! And also look at how nicely linearly the chain lengths appear to grow with the exponent of the x-axis! This is a bit mind-blowing to me that the chain length of N seems to be so naturally related to log(N).

Extending this graph to 100 times more values of N:


We can really clearly see how linear everything remains! Another feature that pops out here is the little “ledges” that occasionally jut out to the left in the graph. These tend to appear whenever we find an N whose chain length is dramatically larger than the previous numbers, and it then carries along some of its larger neighbors.

This might raise the question: how often do we actually see new record chain lengths? I mean, clearly we’re going to get larger and larger chain lengths forever, off to infinity, but how often do these record-breaking chains appear?

Surprisingly rarely! Let’s define a record-breaking Collatz chain as a Collatz chain such that all the Collatz chains with smaller starting values are shorter in length. Let’s look at where these record-breakers appear for N up to 100,000:


They look pretty evenly spaced! But remember, the x-axis is growing exponentially. So in fact, they get exponentially farther apart.

By the way, look at that weird straight line that appears about midway between 101 and 102. The exact values of these record breakers are:

54: 112
73: 115
97: 118
129: 121
171: 124
241: 127
313: 130

That’s right, the record increases by exactly 3, six times in a row! This might be a fluke, or maybe there’s something deeper going on.

Also, I’m sure you’re curious about that one record-breaker that jumps way above the previous record-breakers. It turns out that you’ve already seen it: it’s 27!

27 is unique in just how much it exceeds all the previous records, going from 23 to 111 (increasing the record by 89). As you can see in the graph, no other record-breaker beats its previous records by nearly as much, even though we’re looking all the way up to 100,000. Perhaps this is just a fluke caused by the early records being especially low? This seems supported by the fact that if we look all the way up to 10 million, we still see that nothing beats 27.


Define a record-breaking record-breaker as a record-breaker that beats the previous record by a greater amount than all previous record breakers. Now, 27 is clearly a record-breaking record-breaker. There is also one before it, namely 3, which beats the previous record by 6. (7 is a record-tying record-breaker, as it also beats the previous record by 6.)

We might have a postulate in mind: 3 and 27 are the only record-breaking record-breakers. Can we prove this?

Well, it turns out that we can’t. Because the postulate is not true! Let’s extend our graph by another factor of 10, going up to 100 million. (By the way, the dynamic programming I mentioned earlier is absolutely essential at this point for any of this to be possible.)


Now we can see that in fact there is another record-breaking record-breaker, all the way over to the right side of the graph! It turns out to be 63,728,127, and it beats the previous record by 205! So 27 is apparently not the largest one. A new question that naturally arises, a question to which I have no answer, is: are there infinitely many record-breaking record-breakers? Or does the sequence end at some point? I conjecture that yes, there are infinitely many such overachievers.

I have two more things to geek out about before I finish up. First of all, take a look at the actual values of the record-breakers up to 10000:

2: 1
3: 7
6: 8
7: 16
9: 19
18: 20
25: 23
27: 111
54: 112
73: 115
97: 118
129: 121
171: 124
231: 127
313: 130
327: 143
649: 144
703: 170
871: 1780
1161: 181
2223: 182
2463: 208
2919: 216
3711: 237
6171: 261
10971: 267
13255: 275
17647: 278
23529: 281
26623: 307
34239: 310
35655: 323
52527: 339
77031: 350

If you skim this list over, you’ll notice that these record-breakers appear to all be odd. But there are in fact four exceptions in this list that appear near its beginning: 2, 6, 18, and 54. And after these four, the even record-breakers appear to disappear. This sort of makes sense; if the first thing you do with your number is make it larger, this will in general result in a longer chain. But are there any more even record breakers larger than 54?

As it turns out, yes there are! But the next even record breaker doesn’t appear until we get into the tens of millions. It is 31,466,382. This is pretty baffling! Try showing your friends the sequence [2, 6, 18, 54, 31466382] and see if they can figure out what comes next! (It turns out that the next number is 127,456,254, which is exactly twice the previous record breaker!)

And now one final observation. There seem to be disproportionately many record-breakers whose chain lengths differ by only 1 or 3. For the heck of it, let’s define shiftless record-breakers as any record breakers who only beat the previous record by 3, and lazy record-breakers as any record-breakers who beat the previous record by 1.

One simple way this might happen is if the previous record breaker is N, and there are no new record breakers up to 2N. Then 2N will be the new record breaker, since its first step will be dividing by 2, and then it will take the rest of Ns chain for itself. So its chain length will be one larger than the chain length of N. (By the way, it turns out that our large even record breaker is in fact an example of a lazy record breaker.)

Are there really disproportionately many lazy and shiftless record breakers? Let’s look at the amount that each record breaker beat its previous record breaker by. This sequence looks like:

6, 1, 8, 3, 1, 3, 88, 1, 3, 3, 3, 3, 3, 3, 13, 1, 26, 8, 3, 1, 26, 8, 21, 24, 6, 8, 3, 3, 26, 3, 13, 16, 11, 3, 21, 8, 3, 57, 6, 21, 39, 16, 3, 3, 26, 3, 3, 21, 13, 16, 52, 21, 3, 3, 13, 1, 39, 205

This is another really mind-blowing observation for me! It looks like the differences between record breakers always seem to take on only very specific values, like 1, 3, 6, 8, and 11. Is there ever a difference of 2? or 5? I have no idea, and I’d love to know! I’ve leave you with this histogram showing how often each difference appears in all record-breakers up to 100 million:


Producing all numbers using just four fours

How many of the natural numbers do you think you can produce just by combining four 4s with standard mathematical operations?

The answer might blow your mind a little bit. It’s all of them!

In particular, you can get any natural number by using the symbols ‘4’, ‘√’, ‘log’, and ‘/’. And in particular, you can do it with just four 4s!

Try it for yourself before moving on!



Continue reading “Producing all numbers using just four fours”

Buddhabrot, Mandelbrot’s older sibling

Many people have heard of Mandelbrot’s famous set. But far fewer have heard of its older sibling: the Buddhabrot. I find this object even more beautiful than the Mandelbrot set, and want to give it its proper appreciation here.

To start out with: What is the Mandelbrot set? It is defined as the set of complex values c that stay finite under arbitrary many repeated applications of the function fc(z) = z2 + c (where the first iteration is applied to z = 0).

So, for example, to check if the number 2 is in the Mandelbrot set, we just look at what happens when we plug in 0 to the function f2 and repeat:

0 becomes 02 + 2 = 2
2 becomes 22 + 2 = 6
6 becomes 62 + 2 = 38
38 becomes 382 + 2 = something large, and on and on.

You can probably predict that as we keep iterating, we’re going to eventually run off to infinity. So 2 is not in the set.

On the other hand, see what happens when we plug in -1:

0 becomes 02 + (-1) = -1
-1 becomes (-1)2 + (-1) = 0
0 becomes -1
-1 becomes 0
… and so on to infinity

With -1, we just bounce around back and forth between 0 and -1, so we clearly never diverge to infinity.

Now we can draw the elements of this set pretty easily, by simply shading in the numbers on the complex plane that are in the set. If you do so, you get the following visualization:


Cool! But what about all those colorful visualizations you’ve probably seen? (maybe even on this blog!)

Well, whether you’re in the Mandelbrot set or not is just a binary property. So by itself the Mandelbrot set doesn’t have a rich enough structure to account for all those pretty colors. What’s being visualized in those pictures is not just whether an element is in the Mandelbrot set, but also, if it’s not in the set (i.e. if the 0 diverges to infinity upon repeated applications of fc), how quickly it leaves the set!

In other words, the colors are a representation of how not in the set numbers are. There are some complex numbers that exist near the edge of the Mandelbrot that hang around the set for many many iterations before finally blowing up and running off to infinity. And these numbers will be colored differently from, say, the number “2”, which right away starts blowing up.

And that’s how you end up with pictures like the following:

Screen Shot 2019-05-22 at 3.37.11 PM.png

Now, what if instead of visualizing how in the set various complex numbers are, we instead look at what complex numbers are most visited on average when running through Mandelbrot iterations? Well, that’s how we get the Buddhabrot!

Specifically, here’s a procedure we could run:

  1. Choose a random complex number c.
  2. Define z = 0
  3. Update: z = fc(z)
  4. Give one unit of credit to whatever complex number z is now.
  5. Repeat 3 and 4 for some fixed number of iterations.
  6. Start over back at 1 with a new complex number.

As you run this algorithm, you can visualize the results by giving complex numbers with more credits brighter colors. And as you do this, a curious figure begins to appear on the (rotated) complex plane:

Screen Shot 2019-05-22 at 4.23.06 PM.png



That’s right, Buddha is hanging out on the complex plane, hiding in the structure of the Mandelbrot set!

Hopping Midpoints

Put down three points on a piece of paper. Choose one of them as your “starting point”. Now, randomly choose one of the three points and hop from your starting point, halfway over to the chosen point. Mark down where you’ve landed. Then repeat: randomly choose one of the three starting points, and move halfway from your newly marked point to this new chosen point. Mark where you land. And on, and on, to infinity.

What pattern will arise? Watch and see!

E to increase points/second.
Q to decrease points/second.
Click and drag the red points to move them around.
Pressing a number key will make a polygon with that number of sides.

Exploring Julia Sets

Here’s a natural follow-up to my last post on the Mandelbrot set – an interactive Julia set explorer!

The Julia set corresponding to a particular point c = x + iy in the complex plane is defined as the set of complex numbers z that stay finite upon arbitrary iterations of the following function: fc(z) = z2 + c. The Mandelbrot set, by comparison, is defined as the set of complex numbers c such that the value obtained by starting with 0 and iterating the function fc arbitrarily many times converges.

What’s remarkable is now beautiful and complex the patterns that arise from this simple equation are. Take a look for yourself: just hover over a point to see its corresponding Julia set!

Resolution is preset at a value good for seeing lots of details and loading at a reasonable speed, but should you want to change it, controls are ‘E’ to increase it and ‘Q’ to decrease it. To reset to default, press ‘SPACE’.

Mandelbrot Exploration

I finally figured out how to embed programs that I write onto these blog posts! I’m really excited about the way this will expand my ability to describe and explain all sorts of topics in the future. I’ll inaugurate this new ability with an old classic: a program that allows you to explore the Mandelbrot set. I’ve preset it with a pretty good resolution limit that allows for nice viewing as well as not too slow load times, but you can adjust it as you please! Enjoy!


UP or W to zoom in

DOWN or S to zoom out

CLICK to center view on the clicked point

E to double resolution (mashing this will slow things down a LOT, so use sparingly)

Q to halve resolution

SPACE to reset everything

Try zooming in on a region near the edge of the set where there are black regions and increasing the resolution. “Resolution” here really means “the number of Mandelbrot iterations run to test if the point diverges or converges”, and the black points are those that were judged to be convergent. So some of these points might be found to be no longer convergent with increasing resolution! Which is why you might notice black regions suddenly filling up with color if you increase the resolution. (Of course, some regions are truly convergent, like the central chunk of the Mandelbrot set around (0,0), so such points’ colors will not depend on the resolution.)

If you’re confused about what this image is, I recommend checking out Numberphile’s video on the Mandelbrot set. (Actually, I recommend it even if you aren’t confused.)

How will quantum computing impact the world?

A friend of mine recently showed me an essay series on quantum computers. These essays are fantastically well written and original, and I highly encourage anybody with the slightest interest in the topic to check them out. They are also interesting to read from a pedagogical perspective, as experiments in a new style of teaching (self-described as an “experimental mnemonic medium”).

There’s one particular part of the post which articulated the potential impact of quantum computing better than I’ve seen it articulated before. Reading it has made me update some of my opinions about the way that quantum computers will change the world, and so I want to post that section here with full credit to the original authors Michael Nielsen and Andy Matuschak. Seriously, go to the original post and read the whole thing! You won’t regret it.

No, really, what are quantum computers good for?

It’s comforting that we can always simulate a classical circuit – it means quantum computers aren’t slower than classical computers – but doesn’t answer the question of the last section: what problems are quantum computers good for? Can we find shortcuts that make them systematically faster than classical computers? It turns out there’s no general way known to do that. But there are some interesting classes of computation where quantum computers outperform classical.

Over the long term, I believe the most important use of quantum computers will be simulating other quantum systems. That may sound esoteric – why would anyone apart from a quantum physicist care about simulating quantum systems? But everybody in the future will (or, at least, will care about the consequences). The world is made up of quantum systems. Pharmaceutical companies employ thousands of chemists who synthesize molecules and characterize their properties. This is currently a very slow and painstaking process. In an ideal world they’d get the same information thousands or millions of times faster, by doing highly accurate computer simulations. And they’d get much more useful information, answering questions chemists can’t possibly hope to answer today. Unfortunately, classical computers are terrible at simulating quantum systems.

The reason classical computers are bad at simulating quantum systems isn’t difficult to understand. Suppose we have a molecule containing n atoms – for a small molecule, n may be 1, for a complex molecule it may be hundreds or thousands or even more. And suppose we think of each atom as a qubit (not true, but go with it): to describe the system we’d need 2^n different amplitudes, one amplitude for each bit computational basis state, e.g., |010011.

Of course, atoms aren’t qubits. They’re more complicated, and we need more amplitudes to describe them. Without getting into details, the rough scaling for an natom molecule is that we need k^n amplitudes, where . The value of k depends upon context – which aspects of the atom’s behavior are important. For generic quantum simulations k may be in the hundreds or more.

That’s a lot of amplitudes! Even for comparatively simple atoms and small values of n, it means the number of amplitudes will be in the trillions. And it rises very rapidly, doubling or more for each extra atom. If , then even natoms will require 100 million trillion amplitudes. That’s a lot of amplitudes for a pretty simple molecule.

The result is that simulating such systems is incredibly hard. Just storing the amplitudes requires mindboggling amounts of computer memory. Simulating how they change in time is even more challenging, involving immensely complicated updates to all the amplitudes.

Physicists and chemists have found some clever tricks for simplifying the situation. But even with those tricks simulating quantum systems on classical computers seems to be impractical, except for tiny molecules, or in special situations. The reason most educated people today don’t know simulating quantum systems is important is because classical computers are so bad at it that it’s never been practical to do. We’ve been living too early in history to understand how incredibly important quantum simulation really is.

That’s going to change over the coming century. Many of these problems will become vastly easier when we have scalable quantum computers, since quantum computers turn out to be fantastically well suited to simulating quantum systems. Instead of each extra simulated atom requiring a doubling (or more) in classical computer memory, a quantum computer will need just a small (and constant) number of extra qubits. One way of thinking of this is as a loose quantum corollary to Moore’s law:

The quantum corollary to Moore’s law: Assuming both quantum and classical computers double in capacity every few years, the size of the quantum system we can simulate scales linearly with time on the best available classical computers, and exponentially with time on the best available quantum computers.

In the long run, quantum computers will win, and win easily.

The punchline is that it’s reasonable to suspect that if we could simulate quantum systems easily, we could greatly speed up drug discovery, and the discovery of other new types of materials.

I will risk the ire of my (understandably) hype-averse colleagues and say bluntly what I believe the likely impact of quantum simulation will be: there’s at least a 50 percent chance quantum simulation will result in one or more multi-trillion dollar industries. And there’s at least a 30 percent chance it will completely change human civilization. The catch: I don’t mean in 5 years, or 10 years, or even 20 years. I’m talking more over 100 years. And I could be wrong.

What makes me suspect this may be so important?

For most of history we humans understood almost nothing about what matter is. That’s changed over the past century or so, as we’ve built an amazingly detailed understanding of matter. But while that understanding has grown, our ability to control matter has lagged. Essentially, we’ve relied on what nature accidentally provided for us. We’ve gotten somewhat better at doing things like synthesizing new chemical elements and new molecules, but our control is still very primitive.

We’re now in the early days of a transition where we go from having almost no control of matter to having almost complete control of matter. Matter will become programmable; it will be designable. This will be as big a transition in our understanding of matter as the move from mechanical computing devices to modern computers was for computing. What qualitatively new forms of matter will we create? I don’t know, but the ability to use quantum computers to simulate quantum systems will be an essential part of this burgeoning design science.

Quantum computing for the very curious
(Andy Matuschak and Michael Nielsen)

Hopping Midpoints and Mathematical Snowflakes

Let me start this off by saying that if you’re reading this blog and haven’t ever checked out the Youtube channel Numberphile, you need to go there right away and start bingeing their videos. That’s what I’ve been doing for the last few days, and it’s given me tons of cool new puzzles to consider.

Here’s one:

Naturally, after watching this video I wanted to try this out for myself. Here you see the pattern arising beautifully from the randomness:


I urge you to think hard about why the Sierpinski triangle would arise from something as simple as randomly hopping between midpoints. It’s very non-obvious, and although I have a few ideas, I’m still missing a clear intuition.

I also made some visualizations for other shapes. I’ll show some of them, but encourage you to make predictions about what pattern you’d expect to see before scrolling down to see the actual result.



Instead of three points arranged as above, we will start out with four points arranged in a perfect square. Then, as before, we’ll jump from our starting point halfway to one of these four, and will continue this procedure ad infinitum.

What pattern will arise? Do you think that we’ll have “missing regions” where no points can land, like with the triangle?

Scroll down to see the answer…





Okay! So it looks like the whole square gets filled out, with no missing regions. This was pretty surprising to me; given that three points gave rise to a intricate fractal pattern, why wouldn’t four points do the same? What’s special about “3” .

Well, perhaps things will be different if we tweak the positions of the corners slightly? Will any quadrilateral have the same behavior of filling out all the points, or will the blank regions re-arise? Again, make a prediction!


Let’s see:

4 TemplesCross4 Double Temples4 Rolos

Okay, now we see that apparently the square was actually a very special case! Pretty much any quadrilateral we can construct will give us a nested infinity of blank regions, as long as at least one angle is not equal to 90º. Again, this is fascinating and puzzling to me. Why do 90º angles invariably cause the whole region to fill out? I’m not sure.

Let’s move on to a pentagon! Do you think that a regular pentagon will behave more like a triangle or a square?


Take a look…


And naturally, the next question is what about a hexagon?



Notice the difference between the hexagon and all the previous ones! Rather than having small areas of points that are never reached, it appears that suddenly we get lines! Again, I encourage you to try to think about why this might be (what’s so special about 6?) and leave a comment if you have any ideas.

Now, I because curious about what other types of patterns we can generate with simple rules like these. I wondered what would happen if instead of simply jumping to the average of the current point and a randomly chosen point, we built a pattern with some “memory”. For instance, what if we didn’t just look at the current point and the randomly chosen point, but also at the last chosen point? We could then take the middle of the triangle formed by these three points as our new point.

It turns out that the patterns that arise from this are even more beautiful than the previous ones! (In my opinion, of course)

Take a look:


Threes Triangle


Threes Square


Threes Pentagon


Threes Hexagon


Threes Heptagon

I’ll stop here, but this is a great example of how beautiful and surprising math can be. I would have never guessed that such intricate fractal patterns would arise from such simple random rules.

Backwards induction and rationality

A fun problem I recently came across:

Consider two players: Alice and Bob. Alice moves first. At the start of the game, Alice has two piles of coins in front of her: one pile contains 4 coins and the other pile contains 1 coin. Each player has two moves available: either “take” the larger pile of coins and give the smaller pile to the other player or “push” both piles across the table to the other player. Each time the piles of coins pass across the table, the quantity of coins in each pile doubles. For example, assume that Alice chooses to “push” the piles on her first move, handing the piles of 1 and 4 coins over to Bob, doubling them to 2 and 8. Bob could now use his first move to either “take” the pile of 8 coins and give 2 coins to Alice, or he can “push” the two piles back across the table again to Alice, again increasing the size of the piles to 4 and 16 coins. The game continues for a fixed number of rounds or until a player decides to end the game by pocketing a pile of coins.

(from the wiki)

(Assume that if the game gets to the final round and the last player decides to “push”, the pot is doubled and they get the smaller pile.)

Assuming that they are self-interested, what do you think is the rational strategy for each of Alice and Bob to adopt? What is the rational strategy if they each know that the other reasons about decision-making in the same way that they themselves do? And what happens if two updateless decision theorists are pitted against each other?

If you have some prior familiarity with game theory, you might have seen the backwards induction proof right away. It turns out that standard game theory teaches us that the Nash equilibrium is to defect as soon as you can, thus never exploiting the “doubling” feature of the setup.

Why? Supposing that you have made it to the final round of the game, you stand to get a larger payout by “defecting” and taking the larger pile rather than the doubled smaller pile. But your opponent knows that you’ll reason this way, so they reason that they are better off defecting the round before… and so on all the way to the first round.

This sucks. The game ends right away, and none of that exponential goodness gets taken advantage of. If only Alice and Bob weren’t so rational! 

We can show that this conclusion follows as long as the three things are true of Alice and Bob:

  1. Given a choice between a definite value A and a smaller value B, both Alice and Bob will choose the larger value (A).
  2. Both Alice and Bob can accurately perform deductive reasoning.
  3. Both (1.) and (2.) are common knowledge to Alice and Bob.

It’s pretty hard to deny the reasonableness of any of these three assumptions!

Here’s a related problem:

An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical antiques. An airline manager tasked to settle the claims of both travelers explains that the airline is liable for a maximum of $100 per suitcase—he is unable to find out directly the price of the antiques.

To determine an honest appraised value of the antiques, the manager separates both travelers so they can’t confer, and asks them to write down the amount of their value at no less than $2 and no larger than $100. He also tells them that if both write down the same number, he will treat that number as the true dollar value of both suitcases and reimburse both travelers that amount. However, if one writes down a smaller number than the other, this smaller number will be taken as the true dollar value, and both travelers will receive that amount along with a bonus/malus: $2 extra will be paid to the traveler who wrote down the lower value and a $2 deduction will be taken from the person who wrote down the higher amount. The challenge is: what strategy should both travelers follow to decide the value they should write down?

(again, from the wiki)

Suppose you put no value on honesty, and only care about getting the most money possible. Further, suppose that both travelers reason the same way about decision problems, and that they both know this fact (and that they both know that they both know this fact, and so on).

The first intuition you might have is that both should just write down $100. But if you know that your partner is going to write down $100, then you stand to gain one whole dollar by defecting and writing $99 (thus collecting the $2 bonus for a total of $101). But if they know that you’re going to write $99, then they stand to gain one whole dollar by defecting and writing $98 (thus netting $100). And so on.

In the end both of these unfortunate “rational” individuals end up writing down $2. Once again, we see the tragedy of being a rational individual.

Of course, we could take these thought experiments to be an indication not of the inherent tragedy of rationality, but instead of the need for a better theory of rationality.

For instance, you might have noticed that the arguments we used in both cases relied on a type of reasoning where each agent assumes that they can change their decision, holding fixed the decision of the other agent. This is not a valid move in general, as it assumes independence! It might very well be that the information about what decision you make is relevant to your knowledge about what the other agent’s decision will be. In fact, when we stipulated that you reason similarly to the other agent, we are in essence stipulating an evidential relationship between your decision and theirs! So the arguments we gave above need to be looked at more closely.

If the agents do end up taking into account their similarity, then their behavior is radically different. For example, we can look at the behavior of updateless decision theory: two UDTs playing each other in the Centipede game “push” every single round (including the final one!), thus ending up with exponentially higher rewards (on the order of $2N, where N is the number of rounds). And two UDTs in the Traveller’s Dilemma would write down $100, thus both ending up roughly $98 better off than otherwise. So perhaps we aren’t doomed to a gloomy view of rationality as a burden eternally holding us back!


One final problem.

Two players, this time with just one pile of coins in front of them. Initially this pile contains just 1 coin. The players take turns, and each turn they can either take the whole pile or push it to the other side, in which case the size of the pile will double. This will continue for a fixed number of rounds or until a player ends the game by taking the pile.

On the final round, the last player has a choice of either taking all the coins or pushing them over, thus giving the entire doubled pile to their opponent. Both players are perfectly self-interested, and this fact is common knowledge. And finally, suppose that who goes first is determined by a coin flip.

Standard decision theory obviously says that the first person should just take the 1 coin and the game ends there. What would UDT do here? What do you think is the rational policy for each player?