Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / U / U2 / b / ii / Solution

The scheme is not uniform in general. A particular successful path has probability equal to the product of the reciprocals of its available-neighbour counts. Those counts depend on the path geometry.

For length four, the straight path $(0,0),(1,0),(2,0),(3,0),(4,0)$ has probability $1/(4\cdot 3\cdot 3\cdot 3)=1/108$. The path $(0,0),(1,0),(1,1),(0,1),(-1,1)$ has only two available neighbours at its last choice, because the previous point and the origin block two directions. Its probability is $1/(4\cdot 3\cdot 3\cdot 2)=1/72$. There is no trapping before four steps, so these are already the output probabilities. They differ, disproving uniformity on $S_4$.

At lengths where restarts occur, conditioning an attempt on success normalizes these path probabilities by a common success probability; it does not remove the unequal products.