< Back to the problem

Solution to a Random Walk in the Park

The distance travelled on average is 610 meters - exactly the same as going straight across at each crossing.

This is true in general no matter how many crossings there are. If you can reach everywhere by just following the path then always going randomly left or right at each crossing will give the same average length.

This can be shown by setting up an equation for each section of the path pi saying the expected distance till the end when that bit s reached is its length and the average of the left and right paths at the end:

Exp(pi) = Len(pi) + ( Exp(pleft(i)) + Exp(pright(i)) ) / 2

for all i except for the end section where:

Exp(pend) = Len(pend)

Each path is only ever traversed in one direction as a be seen by marking each area in black or white.Then each edge goes in the same direction as the start path when it has black on the same side.

Adding all the equations for all the sections of the path gives:

Sum for i= start to end of Exp(pi) =
   Sum for i= start to end of Len(pi) +
   Sum for i= all except end of ( Exp(pleft(i)) + Exp(pright(i)) ) / 2

But the left and right paths at the ends of the paths include every path except the start so the last part of that sum is:

Sum for i = all except start of ( Expi + Expi ) / 2

So we get:

Sum for i= start to end of Exp(pi) =
   Sum for i= start to end of Len(pi) +
   Sum for i= all except start of Exp(pi)

Subtracting the common part on the right of the equation from the left then gives:

Exp(pstart) = Sum for i= start to end of Len(pi)

i.e. the expected distance is the total length of the path.

Going left with probability one third and right with probability two thirds will give exactly the same average using the same argument as above. The one third and two thirds add up to one as the left path for the opposite path coming in is the same path as the right path when going ahead. In fact one could have a different probability at each junction provided it applies to say the left side whichever way the junction is approached. It is important though that the entrance and exit are on the outside, that one could join them without crossing any paths.