The challenge
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.
Examples
N=1
: a single-step walk obviously doesn't intersect itself. So the result is1
.N=2
: given the first step in any direction, there are3
possible directions that avoid intersection, and one that goes back to the origin, causing intersection. So the result is3/4 = 0.75
.N=3
: if the second step doesn't cause intersection, which happens3/4
of the times, the third step will not cause intersection with probability again3/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 the8
proper loops out of the4^4
possible paths (these are not excluded by the first term).
Additional rules
- 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.
Test cases
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