Details

Snapshot 1: Most paths stop early. Here, , that is, the possible steps are , , , and . In this simulation, house 2 was visited at step 3 and also at step 6; thus the walk stops.

Snapshot 2: With a small probability, the walk can continue some time. In this case, house was visited at step 9 and also at step 11; thus the walk stops.

Snapshot 3: Here we see the relative frequencies of the length of the walk (they are based on one million simulations for each ). Two steps is the minimum. If the possible steps are , , , and , as in this snapshot, three steps is the most probable case and most walks do not continue more than, say, 10 steps, but one walk among the one million walks lasted 28 steps. The average is only 3.8 steps.

Snapshot 4: Here . Now the most probable length of the path is 5 and most walks do not continue more than, say, 20 steps, but one walk among the one million walks lasted 55 steps. The average is now about 8 steps.

This Demonstration is based on problem 9 in [2]. There, the case is considered. It is very difficult to calculate exact probabilities for the length of the walk. For , exact probabilities are derived in [1] for the cases that the walk continues 2, 3, 4, 5, 6, or 7 steps. With the recursive formulas derived in this article, more probabilities can easily be calculated with Mathematica; the relative frequencies based on our simulations agree very well with the exact probabilities.

The process considered in this Demonstration has the property that each newly visited location transforms into an absorbing location. Another example with absorbing states is the so-called gambler's ruin process (there we have two fixed absorbing states).

References

[1] C. Foster and A. Rapoport, "The Case of the Forgetful Burglar," The American Mathematical Monthly, 65(2), 1958 pp. 71–76.

[2] P. J. Nahin, Digital Dice: Computational Solutions to Practical Probability Problems, Princeton: Princeton University Press, 2008.