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 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 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 , what is the best strategy for moving disks such that the expected probability of failure is less than and the expected number of moves is minimal?
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 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:
- Disks 1…(n-2) from A to C ( moves)
- Disk (n-1) from A to C (1 inverted move)
- Disk n from A to B (1 move)
- Disk (n-1) from C to B (1 move)
- Disks 1…(n-2) from C to B ( moves)
This takes a total of 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 moves†.
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.