Towers of Hanoi

Inspired by this FiveThirtyEight Riddler problem.

The setup: we have three pegs and N rings of increasing size, and our goal is to restack all the rings on another peg, one at a time, without ever stacking a larger ring on a smaller one.

Suppose we approach this game blindly, choosing a random legal move at each turn. What's the expected number of moves we have to make before we succeed?

Let's play a bunch of games.

First, set the number of rings and the number of times we play the game. We'll save all our results as samples.

If you choose 5 or more rings, I recommend you set the number of trials lower by orders of magnitude. (e.g. at most 100 for 8). You can check the console to see the progress.

Number of rings Number of trials

Click "start" to collect your samples!

With these samples, let's get a bootstrapped estimate of the variance.

Set the bootstrapping parameters below:

Number of samples Sample size

Click "Bootstrap" to estimate the variance!

Finally, let's visualize a random walk.

Deriving the expected value relies beautifully on the fractal-like structure of the Markov decision graph (and a little intuition for circuits!). Let's observe how we walk from node to node as we simulate a random set of moves with 2 rings. Notice that our goal is to reach the bottom two vertices, so take note of when we hit that.

If you understand circuits, something that might jog your inuition: when there are multiple paths from one node to another, wouldn't you get there faster? Does that remind you intuitively of...equivalent resistance?

Credit again to Alekseyev & Berger (2014), though one of the states is redundant! Can you catch which one?