A "Slimy Slug" is a simple probabilistic cellular automata defined as follows:

The Slimy Slug lives on an infinite, two-dimensional, white-coloured, square grid. For each iteration, the slug follows these rules:

  1. Paint the cell the Slug is on black.
  2. Look at the 4 orthogonal adjacent cells (i.e. N,E,S,W)
    • If zero of the cells are white, Halt.
    • If exactly one of the cells is white, move to the white cell.
    • If more than one of the cells are white, randomly move to one of the white cells. (e.g. if the white cells are N,E,W, each cell has a 1/3 probability of being the destination.)
  3. Go to rule 1.

The slug will follow a random walk, and although it could theoretically continue for an infinite number of steps, it will generally halt when it traps itself. An example of a possible trail of the slug is shown below (Instead of black and white, I have false-coloured the cells with a gradient to illustrate the path of the slug). This trail has a length of 99 steps, and the slug started in the top right, and worked it's way down to the bottom left.

Slimy Slug Trail

Is it possible to arrive at an expression for the expected length of the Slimy Slug's trail?

This is outside my field, so I haven't had much success in researching if this is a studied problem or not. Via numerical simulation, I have arrived at a value of 70.799611 for a set of 1,000,000 runs, but I'm interested in seeing if a value can be arrived at without numerical simulation. This is motivated by a related problem in game design/educational exercise design.

  • 2
    $\begingroup$ In the movement rules, the second bullet point is a special-case of the third, fwiw $\endgroup$
    – AakashM
    Mar 8 at 10:00
  • $\begingroup$ BAsically same question here: cstheory.stackexchange.com/questions/17438/… $\endgroup$
    – leonbloy
    Mar 8 at 11:42
  • $\begingroup$ @AakashM - Agreed, just trying to spell it out to make it as clear as possible. $\endgroup$ Mar 8 at 11:47
  • 2
    $\begingroup$ I'd search by "self avoiding random walk". $\endgroup$
    – leonbloy
    Mar 8 at 11:49
  • 1
    $\begingroup$ This paper says that the average is $70.85\pm 0.05$, but they don't have an exact value. $\endgroup$ Mar 11 at 19:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.