November « 2010 « Spencer Bliven

Probabilistic Towers of Hanoi

November 23, 2010 | Posted in Math, Tagged hanoi, open problem, statistics hanoi, open problem, statistics

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 $\left\lfloor \frac{log(1-\epsilon)}{log(1-p)}\right\rfloor$ 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 ( $2^{n-2}-1$ 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 ( $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)$ .

Latex!

November 22, 2010 | Posted in Math,Metablog, Tagged blogging, latex, wordpress blogging, latex, wordpress

I installed a $\LaTeX$ plugin! It will pretty up any of my mathy posts, and you can use it in comments too! For inline math formulas, surround your $\LaTeX$ code with two dollar signs: $$\frac{4}{3}\pi r^3$$ gives $\frac{4}{3}\pi r^3$ . For display equations, add an exclamation mark: $$!E\psi(r)=-\frac{\hbar^2}{2m}\nabla^2\psi(r)+V(r)$$ gives

$E\psi(r)=-\frac{\hbar^2}{2m}\nabla^2\psi(r)+V(r)$

If you need two dollar signs for some reason, use the html escape sequence for dollar, $.

WordPress with Sqlite on PHP 5.1

November 12, 2010 | Posted in Metablog, Tagged blogging, wordpress blogging, wordpress

After a long plod, I finally got wordpress running on acsweb! This is exciting, since it means it is possible to comment on posts, link to them, google for them, etc. Setting up wordpress was made challenging at every turn by my crappy UCSD server, which is outdated or badly configured in a number of respects:

No MySQL, so I had to use the PDO plugin with a Sqlite database
PHP 5.1, which should be compatible with PDO, but is missing the preg_last_error() function
Error logging and printing is disabled, making discovering the previous error an hours-long debugging process

For anyone else trying to setup wordpress on a similar setup, here were the steps that worked for me:

Run phpinfo() to make sure php is running properly and you can access the webserver. Make sure PDO support is enabled, which should result in a section called ‘pdo_sqlite’.
Download and unpack wordpress
Download PDO for WordPress. Copy all the contents of the zip file into wordpress/wp-content/.
Set up wp-config.php, as described in the PDO instructions
Apache needs permission to create the sqlite database file in your wordpress directory. For now, I just
```
chmod -R a+w wordpress
```
If you are running PHP version 5.0-5.1 (PHP 4 is SOL due to PDO requirements), then edit the file wp-content/pdo/driver_sqlite/pdo_sqlite_driver_create.php. Look for the function addQuery($query) around line 207. Comment out the line with preg_last_error():
```
private function addQuery($query) {
    $this->_query[] = $query;
    //$this->_errors[] = preg_last_error(); // PHP >= 5.2;
}
```
Look at your wordpress install from a browser. It should guide you through the “easy” install process and set you up with an admin account. Make sure everything works right.
Eventually you probably want to remove that global write permission we added to the wordpress directory, except for the database and the uploads folder.
```
chmod -R go-w wordpress
mkdir -p wordpress/wp-content/uploads
chmod -R go+w wordpress/wp-content/uploads
```

Note that these instructions were tested with WordPress 3.0.1 with PDO plugin 2.7.0. I submitted a patch to PDO for wordpress, so hopefully future versions will be compatible with PHP 5.1.

Spencer Bliven

Thoughts and Research