4 ms·
I think that the intuition here has to do with the dimensionality of the problem, in the sense that we have proved that in 3 dimensions a random walk will never
by hyperion2010 8y ago
I think that the intuition here has to do with the dimensionality of the problem, in the sense that we have proved that in 3 dimensions a random walk will never return to it's starting point, bit in two dimensions it will. Mapping all probabilistic algorithms into demensional random walk space is probably extremely difficult though.
- dcow 8y ago> in the sense that we have proved that in 3 dimensions a random walk will never return to it’s (sic.) starting point We have? I believe the probability is ~34%. http://mathworld.wolfram.com/PolyasRandomWalkConstants.html http://mathworld.wolfram.com/PolyasRandomWalkConstants.html
- hyperion2010 8y agoSorry, I had it reversed in my head. For 1 and 2 dimensions they will return to the starting point with probability 1. For 3 dimensions it simply that it is not probability 1. Obviously a weaker result.