Sarah the Squirrel's Square Search
Sarah the squirrel is trying to find her acorn, but she can't remember where she left it!
She starts in the lower-left corner of the 2 × 2 grid, and at each point, she randomly steps to one of the adjacent vertices (so she may accidentally travel along the same edge multiple times).
What is the expected value for the number of steps Sarah will take before she finds her acorn in the top-right corner?
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.
2 solutions
How did you come up with this equations?
Log in to reply
The above is the solution I used, too. I encountered the problem whilst reading this page . If you haven't read it, it is very useful as it has various techniques which allows you to solve these types of problems. The section in particular where this problem is encountered talks about states.
As shown above, the 3x3 grid can be considered as having 5 states. (State 5 is the end point). To solve this problem, we are going to try to find the expected number of moves it takes to finish the puzzle from 1 particular state.
Now, when the squirrel starts the puzzle, she is at state 1. We are trying to find E ( X ) , which is the expected number of moves for Sarah to finish the puzzle. This is also the same as E 1 . This means E ( X ) = E 1 .
Once she is in state 5, the puzzle has ended, and so E 5 = 0 , as Sarah doesn't need to move any more.
The way the equations above are derived is to consider what happens when Sarah is at a particular state.
So if she is at state 1, she will definitely go to state 2, as there is nowhere else she can go. Therefore, E 1 = 1 + E 2 , since she takes up 1 move, and then goes to state 2.
If she is at state 2, there is 3 1 chance she will go back to state 1, and 3 2 chance she will go to state 3, as there are 2 paths back, but 4 paths forward. From this, the second equation is derived: E 2 = 1 + 3 1 E 1 + 3 2 E 3 . This says that she always takes one move to get from state 2 to anywhere, and 3 1 of that time she goes to state 1, and 3 2 to state 3.
The other equations are derived in a similar manner. I hope this makes sense.
Wow, this solution was much easier than the 8x8 system, which is what I did.
Elegant solution. I've started to appreciate the method of states now. Thanks!
this solution is not clear to me
To solve such type of questions for a Large number of variables/states, we can use Gaussian elimination.
My approach, which doesn't require solving complex set of equations:
Let E i be the expected number of steps to move from state i to state i + 1 for 1 ≤ i ≤ 4 where state 5 is the goal state.
From state 1, clearly you need 1 step to move to state 2, so E 1 = 1
From state 2, with 2 / 3 probability, you can move to state 3 in 1 step, and with 1 / 3 probability, you can move to state 1, then you'll take E 1 number of steps to advance to state 2, and then E 2 number of steps to advance to state 3. Thus:
E 2 = 3 2 ( 1 ) + 3 1 ( 1 + E 1 + E 2 ) On solving, we get E 2 = 2 .
Similarly,
E 3 = 2 1 ( 1 ) + 2 1 ( 1 + E 2 + E 3 ) , giving: E 3 = 4 .
E 4 = 3 1 ( 1 ) + 3 2 ( 1 + E 3 + E 4 ) , giving: E 4 = 1 1 .
Our final required answer will be the sum of expected number of steps to move from state 1 to 2, 2 to 3, 3 to 4, and 4 to 5, which is the sum of all the above values:
a n s = E 1 + E 2 + E 3 + E 4 = 1 8 .
What does it mean? Could you elaborate please?
Let's write the various vertices as "states". Let E 1 be the expected value we desired and let E 2 be the expected value if Sarah started at one of the two vertices adjacent to the bottom-left vertex (it is the same for either vertex by symmetry).
Let E 3 be the expected value if Sarah starts in the top-left or bottom-right corner, and let E 4 be the expected value if she starts in the top-middle or right-middle vertices. Furthermore, note that E 3 is also the expected value if she starts in the middle vertex, since the middle vertex is equally likely to take Sarah to states 2 or 4, just like the state 3 corners. If anything isn't clear, let's summarize with this state diagram:
Looking at this diagram, we see that E 1 = 1 + E 2 , E 2 = 1 + 3 1 E 1 + 3 2 E 3 , E 3 = 1 + 2 1 E 2 + 2 1 E 4 and E 4 = 1 + 3 2 E 3 . Combining all four of our equations, we can solve to find E 1 = 1 8 .