Given a positive integer
N, compute the proportion of
N-step walks on a plane that don't intersect themselves.
Each step can have any of the
4 possible directions North, East, South, West.
A walk intersects itself if it visits a previously visited point.
N=1: a single-step walk obviously doesn't intersect itself. So the result is
N=2: given the first step in any direction, there are
3possible directions that avoid intersection, and one that goes back to the origin, causing intersection. So the result is
3/4 = 0.75.
N=3: if the second step doesn't cause intersection, which happens
3/4of the times, the third step will not cause intersection with probability again
3/4. So the result is
(3/4)^2 = 0.5625.
N=4: things become more interesting because proper loops can be formed. A similar computation as above gives
(3/4)^3 - 8/4^4 = 0.390625, where the second term accounts for the
8proper loops out of the
4^4possible paths (these are not excluded by the first term).
- Output can be floating-point, fraction, or numerator and denominator.
- If floating point, the result should be accurate up to at least the fourth decimal.
- Input and output are flexible as usual. Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
- Shortest code in bytes wins.
1 -> 1 2 -> 0.75 3 -> 0.5625 4 -> 0.390625 5 -> 0.27734375 6 -> 0.1904296875 7 -> 0.132568359375 8 -> 0.09027099609375 9 -> 0.0620574951171875 10 -> 0.042057037353515625 11 -> 0.02867984771728515625 12 -> 0.0193674564361572265625