Probability of being caught in own loops

Suppose you are wondering randomly on a chessboard, starting from a corner, making one step up, down, left or right every time. You are not allowed to step on cells which you have already visited earlier. What are the chances that at some point you’ll not be able to go anywhere, i.e. you get caught in a dead end made by your own previous steps?

I got no idea how to solve this “purely”. Out of curiosity, I calculated the probabilities programmatically for 8×8 board for any path length (up to 63, naturally). Blue line shows the probability of being stuck at given path length or earlier, yellow line – 10 x probability of being stuck exactly at this path length.

Probabilities

Graphs do not show anything unexpected, except – what happens at points 48 and 49? I have no idea.

The calculation was straightforward by “first thought” without any optimizations. For each path length, I did 10^6 runs; with this amount, dispersion in the results between runs was by far under 1%, and run time acceptable (I do not indicate the units of the right Y-axis 🙂 )

Surprisingly I was not able to profile the run with gprof; looks like MacOS default C compiler and/or libraries just do not do it.

Still interested in a general solution, if there exists one.

2 thoughts on “Probability of being caught in own loops

  1. @Kirill: No, not at all! Oscillations in the beginning come from a clear reason. In the end, there is almost no oscillation at all – which I would expect. Except that strange jump at 48.

Leave a Reply

Your email address will not be published. Required fields are marked *