Walk the grid

You start at the point ( x , y ) = ( 1 , 1 ) (x,y) = (1,1) in a Cartesian coordinate system.

Every second you move randomly 1 unit either up, down, left or right.

What is the expected value for the number of seconds it will take for you to land on a point ( 5 m , 5 n ) (5m, 5n) where m m and n n are integers ?

Clarification : You can walk anywhere in all four quadrants of the Cartesian coordinate system. m m and/or n n can be negative.


Image credit: clipartfreefor.com


The answer is 30.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Geoff Pilling
Jun 10, 2016

By symmetry there are only five unique expectation values in the problem.

They are represented by the expectation values from the following points:

( 1 , 0 ) , ( 1 , 1 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 2 ) (1,0), (1,1), (2,0), (2,1), (2,2)

Let E 1 E_1 through E 5 E_5 be defined as the expected value for the number of moves it would take to get to ( 5 m , 5 n ) (5m,5n) for integral m m and n n from each of these locations respectively.

From each grid point the expectation value is given by E = 1 + 1 / 4 E = 1 + 1/4 * (sum of neighboring expectation values)

So, we have the following set of linear equations:

E 1 = 1 + 0.25 ( 2 E 2 + E 3 ) E_1 = 1 + 0.25(2E_2+E_3) E 2 = 1 + 0.25 ( 2 E 4 + 2 E 1 ) E_2 = 1 + 0.25(2E_4+2E_1) E 3 = 1 + 0.25 ( E 1 + E 3 + 2 E 4 ) E_3 = 1 + 0.25(E_1+E_3+2E_4) E 4 = 1 + 0.25 ( E 2 + E 3 + E 4 + E 5 ) E_4 = 1 + 0.25(E_2+E_3+E_4+E_5) E 5 = 1 + 0.25 ( 2 E 4 + 2 E 5 ) E_5 = 1 + 0.25(2E_4+2E_5)

Sovling for E 2 E_2 , this gives, E 2 = 18 E_2 = \boxed{18}

The first equation should be E 1 = 1 + 0.25 ( E 2 + E 3 ) E_1 = 1 + 0.25(E_2 + E_3) . This leads to E 2 = 30 E_2 = 30 .

Jon Haussmann - 5 years ago

Log in to reply

I agree - I also got 30.

Melissa Quail - 5 years ago

Log in to reply

OK, I've updated the first equation. Thanks for noticing!

Geoff Pilling - 5 years ago

Log in to reply

@Geoff Pilling Thanks - no worries!

Melissa Quail - 5 years ago

Ooops, I think you are both correct... I've asked @Calvin Lin to see if the answer can be updated... My apologies...

Geoff Pilling - 5 years ago

Would it take the same expected number of seconds to move from 1 , 1 1,1 to 5 , 5 5,5 or 55 , 5 55,5 or 555 , 55 555,55 ? Strange..

Vishal Yadav - 4 years, 3 months ago

Log in to reply

Not quite... The expected number is the expected number that after so many moves you will be at a number where the x and y coordinate will be divisible by 5. But this is different from saying that the expected number is the same for all such N. In fact the sum of all the expectation values of all of these should add up to 30, but they don't all independently add up to 30, since for example, if they are far enough away, there is no way you can reach them in 30 s.

Geoff Pilling - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...