The PacMan problem

I came across this mathematical problem the other day:

Consider n points on a circle, labeled clockwise from 0 to n-1. Initially PacMan begins at 0 and there is a dot at each of the remaining n-1 points. PacMan takes a random walk around the circle; at each step, it moves with probability 1/2 to one neighbor and with probability 1/2 to the other neighbor. (Note that points 0 and n-1 are neighbors.) The first time PacMan visits any point it eats the dot that is there. Which dot is most likely to be the last eaten?

(This is edited from the original since the professor who formulated it wants to reuse it in a different class and I’d rather not students find this with a simple search.)

Here’s the game plan then for 10 points around the circle:

My first basic thought was, since the question asks for a single dot, it would make sense from a symmetry point of view for that dot to be directly opposite. In other words: it’s the dot furthest away that gets eaten last most of the time. Seems like a viable proposition, no? But maybe I’m trying to be too clever in reading between the lines of the problem: maybe there is more than one dot that is likely to be the last eaten, say at 1/3 and at 2/3 of the way round the circle. It’s getting a bit complicated now.

Mitzenmacher indicated that many students decided to simulate the problem to find out the answer, and then to reason the proof from the statistical results. I decided to do the same. And because I’m into JavaScript at the moment, I used that as my language. It also gives me an opportunity to expand a little on how to write long-running programs that can run in a browser.

In essence I wrote a program to cycle through game after game, recording the last dot to be eaten. To make it statistically significant, I went for some 90,000 games. Here’s my code:

  var i, 
      gameNumber = 0, 
      totalGames = 90000,
      pointCount = 10,
      stats = [];

  // zero out the stats array
  for (i = 0; i < pointCount; i++) {
    stats[i] = 0;
  }

  var dotsToEat,
      dotsEaten,
      pacManPosition,
      goLeft,
      dotPositions = [false];
            
  for (gameNumber = 0; gameNumber < totalGames; gameNumber++) {

    // reset game
    dotsEaten = 0;
    dotsToEat = pointCount - 1;
    for (i = 1; i < pointCount; i++) {
      dotPositions[i] = true;
    }
    pacManPosition = 0;

    // continue moving PacMan until all dots are eaten
    while (dotsEaten < dotsToEat) {
      // go left or right?
      goLeft = Math.random() < 0.5;

      // move PacMan
      if (goLeft) {
        pacManPosition = pacManPosition - 1;
        if (pacManPosition < 0) {
          pacManPosition = pointCount - 1;
        }
      }
      else {
        pacManPosition = pacManPosition + 1;
        if (pacManPosition === pointCount) {
          pacManPosition = 0;
        }
      }
            
      // if there's a dot, eat it
      if (dotPositions[pacManPosition]) {
        dotPositions[pacManPosition] = false;
        dotsEaten += 1;
      }
    }

    // increment stats for the last position
    stats[pacManPosition] += 1;
  }

  alert(stats);

There’s nothing too difficult here: in essence, I set up a loop to run game after game. For each game I simulate PacMan doing a random walk around the circle, back and forth, eating dots when he gets to them. I make a note of the last dot eaten in a statistics array, before going round again and starting a new game. Finally after 90,000 games I report the stats array.

If you run this in Firebug (like I did) you’ll see that the browser times the script out because it’s taking too long. Time to refactor to use setTimeout.

(I would take a look at a three part series I did a while back on callbacks (one, two, three) since I will be using the same techniques here.)

The first thing to do is to make the code that runs a single game into its own function since it’ll be easier to pass it to the setTimeout function. For simplicity though, I’m going to nest it inside another function so I can take advantage of function scoping for the variables that apply across all games. Here’s the main outer function and its call.

var runSimulation = function () {

  // code goes here

};

runSimulation();

Now for the run-a-single-game function:

  var runGame = function () {
    // reset game
    var dotsEaten = 0,
        dotsToEat = pointCount - 1,
        pacManPosition = 0,
        i, goLeft,
        dotPositions = [false];

    for (i = 1; i < pointCount; i++) {
      dotPositions[i] = true;
    }

    // continue moving PacMan until all dots are eaten
    while (dotsEaten < dotsToEat) {
      // go left or right?
      goLeft = Math.random() < 0.5;

      // move PacMan
      if (goLeft) {
        pacManPosition = pacManPosition - 1;
        if (pacManPosition < 0) {
          pacManPosition = pointCount - 1;
        }
      }
      else {
        pacManPosition = pacManPosition + 1;
        if (pacManPosition === pointCount) {
          pacManPosition = 0;
        }
      }
            
      // if there's a dot, eat it
      if (dotPositions[pacManPosition]) {
        dotPositions[pacManPosition] = false;
        dotsEaten += 1;
      }
    }

    // increment stats for the last position
    stats[pacManPosition] += 1;
  };

The variables for this nested function that come from the outer function are stats[] and pointCount.

We’ll also write a self-delaying function to run all the games:

  var runAsync = function () {
    runGame();
    gameNumber += 1;
    if (gameNumber < totalGames)
      setTimeout(runAsync, 10);
    else 
      alert(stats);
  };

In other words, run a game, after it completes and there are more games to run, queue up the next one with setTimeout, otherwise display the stats array. The full code now looks like this:

var runSimulation = function () {

  var i, 
      gameNumber = 0, 
      totalGames = 90000,
      pointCount = 10,
      stats = [];

  var runGame = function () {
    // code above
  };

  var runAsync = function () {
    // code above
  };

  // zero out the stats array
  for (i = 0; i < pointCount; i++) {
    stats[i] = 0;
  }

  runAsync();
};

Way cool. Except that, since it runs one game every 10 milliseconds, it takes 900+ seconds (90,000 games * 10 ms) to give an answer. That’s a quarter of an hour. I’m sorry but, although I’d like to know the answer, 15 minutes to see it is a little too long. Let’s refactor the runAsync function to batch up the games. It should try and run as many games as it can during 50 milliseconds (say) before queuing up another batch. Replace the old runAsync function with this new one (plus a little helper function):

  var now = function () {
    return +new Date();
  };

  var runAsync = function () {
    var start = now();

    do {
      runGame();
      gameNumber += 1;
    } while ((gameNumber < totalGames) && ((now() - start) < 50));

    if (gameNumber < totalGames)
      setTimeout(runAsync, 10);
    else 
      alert(stats);
  };

Now we’re really rocking. On my machine just now, this runs 90,000 games and produces an answer in about 3 seconds. The answer just now?

0,9994,10079,10039,9919,10004,9879,10073,10027,9986

Wow. In other words, any dot is just as likely to be the last one eaten as any other. (If you like, the probability of any dot being the last one eaten is 1/9.)  My initial guess of the opposite dot is dead wrong.

To prove this mathematically involves rather more knowledge about random walks and Markov processes than I now know (it’s been a while since I did probability at University). It’s also linked to the Gambler’s Ruin problem.

  Loading links to posts on similar topics...