Walking At Random (Computer Science)

Computer Science Level 5

Imagine that you are walking along the lines of the grid of unit squares below.

If your starting place and the steps you take are random, after $10$ steps, what is the average Euclidean (straight line) distance you end up away from your starting point? Round your answer to three decimal places.

Details And Assumptions

One step counts as moving from your current location to an adjacent point along one of the line segments (no moving diagonally)

The answer is 2.067.

1 solution

Bill Bell
Aug 27, 2015

State machine.

from random import choice, randint
import numpy
from math import sqrt

class Intersection:
    def __init__(self, i,j,size=5):
        self.neighbours=[]
        for item in [(max(1,i-1),j),(min(size,i+1),j), (i,max(1,j-1)), (i,min(size,j+1))]:
            if (i,j)!=item:
                self.neighbours.append(item)
    def next(self):
        return choice(self.neighbours)

size=5

lattice=numpy.empty(shape=(size+1,size+1),dtype=object)
for i in range(1,size+1):
    for j in range(1,size+1):
        lattice[i,j]=Intersection(i,j)

N=1000000
totalDistance=0
for n in range(N):
    start=(randint(1,size), randint(1,size))
    position=start
    for k in range(10):
        position=lattice[position].next()
    distance=sqrt((start[0]-position[0])**2+(start[1]-position[1])**2)
    totalDistance+=distance
print totalDistance/N

Walking At Random (Computer Science)

The answer is 2.067.

1 solution

0 pending reports