Skip to main content
Image links broken; now fixed.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path http://cs.smith.edu/%7Eorourke/MathOverflow/TrappedPath.jpgTrapped Path
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability http://cs.smith.edu/%7Eorourke/MathOverflow/TrappingPlot.jpgTrapping Probability
Addendum. Incidentally, I have some evidence—not definitive—that the mean path length before reaching a cul-de-sac is about 71.6 steps.

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path http://cs.smith.edu/%7Eorourke/MathOverflow/TrappedPath.jpg
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability http://cs.smith.edu/%7Eorourke/MathOverflow/TrappingPlot.jpg
Addendum. Incidentally, I have some evidence—not definitive—that the mean path length before reaching a cul-de-sac is about 71.6 steps.

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability
Addendum. Incidentally, I have some evidence—not definitive—that the mean path length before reaching a cul-de-sac is about 71.6 steps.

Addendum on mean path length.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path http://cs.smith.edu/%7Eorourke/MathOverflow/TrappedPath.jpg
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability http://cs.smith.edu/%7Eorourke/MathOverflow/TrappingPlot.jpg
Addendum. Incidentally, I have some evidence—not definitive—that the mean path length before reaching a cul-de-sac is about 71.6 steps.

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path http://cs.smith.edu/%7Eorourke/MathOverflow/TrappedPath.jpg
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability http://cs.smith.edu/%7Eorourke/MathOverflow/TrappingPlot.jpg

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path http://cs.smith.edu/%7Eorourke/MathOverflow/TrappedPath.jpg
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability http://cs.smith.edu/%7Eorourke/MathOverflow/TrappingPlot.jpg
Addendum. Incidentally, I have some evidence—not definitive—that the mean path length before reaching a cul-de-sac is about 71.6 steps.

Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

As per Ron Maimon's suggestion, I did a little simulation for the lattice version, counting the number of paths that get trapped at or before $n$ steps. For example, here is a trapped path of 45 steps:
Trapped Path http://cs.smith.edu/%7Eorourke/MathOverflow/TrappedPath.jpg
Because there is a positive probability at any point of forming a shape like the letter 'G' (if there is sufficient room), the probability of trapping goes to 1 as $n \rightarrow \infty$. For $n=100$, the probability is already over $\frac{3}{4}$.
        Trapping Probability http://cs.smith.edu/%7Eorourke/MathOverflow/TrappingPlot.jpg