The Lunch of Hanoi
Yellow curry on rice, Thai iced tea, and mango sticky rice.

At lunch after stats class I received the three to-go boxes at right. Probably due to some sort of brain-addling by aforementioned stats class, this lead me to think about the Towers of Hanoi problem, and how in real life stacking problems (eg lunches, moving trucks, etc) it is often ok to have one or two big boxes stacked on top of little boxes. This led to the following problem:

Probabilistic Towers of Hanoi

Like the Towers of Hanoi problem, we have three pegs and a stack of N disks. Disks are initially sorted on one peg, and the goal is to move single disks between pegs until all the disks are stacked in order on the second peg.

Unlike Towers of Hanoi, we allow larger disks to be stacked on top of smaller disks. This exponentially reduces the number of moves required, since it effectively reduces the stack height by 1 (recall that solving Towers of Hanoi requires $$2^n-1$$ moves).

However, every time we stack a larger disk on top of a smaller disk, the tower falls over with probability p. In general, p could be some function $$g(cdot)$$ which varies depending on the differences in disk sizes, the height of the stack, etc., or it could be something simple like a fixed number. If the tower falls we lose the game and civilization is destroyed. Alternately, maybe we just have to redo the fallen tower, wasting some moves to do so.

The probabilistic towers of hanoi problem then becomes: Given some probability $$epsilon$$, what is the best strategy for moving disks such that the expected probability of failure is less than $$epsilon$$ and the expected number of moves is minimal?

Solution

If there is a fixed probability p of losing the game each time we add a disk to a stack that contains a smaller disk, we can make at most $$leftlfloor frac{log(1-epsilon)}{log(1-p)}rightrfloor$$ inverted moves. These should be distributed in such a way as to reduce the number of moves as much as possible. For one inverted move, this is as follows:

  1. Disks 1…(n-2) from A to C ($$2^{n-2}-1$$ moves)
  2. Disk (n-1) from A to C (1 inverted move)
  3. Disk n from A to B (1 move)
  4. Disk (n-1) from C to B (1 move)
  5. Disks 1…(n-2) from C to B ($$2^{n-2}-1$$ moves)

This takes a total of $$2^{n-1}-1$$ moves, including one inversion. That’s around 50% better than the original algorithm. If additional inverted moves are allowed while keeping the probability of failure low, they should be distributed evenly between steps 1 and 5 to further reduce the moves. Given sufficient inverted moves, this procedure will move a stack of n disks in only $$3(2^{n/2}-1)$$ moves.

Open Problems

The fixed-probability case isn’t particularly interesting statistically. A more interesting probability function would be some physics-inspired statistic reflecting how ‘top-heavy’ a pile is; a large disk perched precariously on top of a stack would be more likely to fall than a medium disk on a slightly smaller base. I feel like some surprising behavior could emerge in these situations requiring more clever algorithms.

For even n. For odd n, it takes $$!2^{(n+3)/2 }-3)$$.
Share

3 thoughts on “Probabilistic Towers of Hanoi

  1. Hi, I apologize for inquiring this query here, but I can’t find a contact form or something so I thought I leave my inquiry here. I run a blogengine blog but I am receiving increased amounts of spam. I see u use wordpress, is it uncomplicated to regulate spam with wordpress or doesn’t it make any difference? I hope you will respond to my comment or maybe send me an email with your answer if you don’t want to approve the comment. Best regards, Annie

    1. Hello, “Annie,” why yes I do use spam filter, and yes it does notice if someone posts the same comment on three posts with different addresses. Hope your pulsatile tinnitus clears up soon, bot.

Leave a Reply

Your email address will not be published. Required fields are marked *