Hexagonal Spider Web - a modified version
A spider has its web in the shape of a regular hexagon . A fly is stuck to the web at a vertex that is diametrically opposite from the vertex at which the spider is. The spider can walk freely along the edges of the hexagon. At each vertex, it randomly chooses between walking on one of the two adjacent edges or staying at the vertex, all three choices with equal probability. If the time it takes to travel an edge is 5 seconds, while the waiting time at a vertex is 2 seconds, find the expected time (in seconds) it will take the spider to get to the fly?
Note: At the end of a waiting period at a vertex, a new random decision to stay at the vertex, or move along one of the two edges is made, with equal probability for the three choices.
The answer is 54.
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
Great solution! A question and a comment.
1) Can you say what about the recurrence relation tipped you off to a quadratic solution? I can see that the solution works, but would not have come up with it.
2) The previous version of this problem had solution E j = 0 , 5 , 8 , 9 , 8 , 5 , 0 for N = 6 . This new version has solution E j = 0 , 3 0 , 4 8 , 5 4 , 4 8 , 3 0 , 0 . So the only dependence on the moving time ( m = 5 seconds) and the waiting time ( w = 2 seconds) amounts to a scaling factor of m + 2 w = 6 . I have been trying to see a way to just argue this directly without building the algebraic relations.
Log in to reply
Recurrence relations are very much like differential equations. If you are familiar with the methods for solving second order DEs with constant coefficients, this is not hard. E j + 1 − 2 E j + E j − 1 = − 1 2 is a nonhomogeneous second order recurrence relation with constant coefficients. We need a CF and a PI.
For the CF, we try to solve E j + 1 − 2 E j + E j − 1 = 0 by looking for solutions of the form E j = u j . This brings us to the indicial equation u 2 − 2 u + 1 = 0 , of which u = 1 is the only repeated root. This yields the CF as A + B j for constants A , B .
To find the PI, we note that the nonhomogeneous term − 1 2 is part of the CF, associated to the double root u = 1 of the indicial equation. This leads us to look for a PI of the form α j 2 , and all we now need to do is determine α .
Log in to reply
Thanks. I was mainly curious if you first looked for exponential solutions like E j = u j for the homogeneous part (which is probably what I would have done), or if you expected pure polynomials from the beginning. The coefficients ( 1 , − 2 , 1 ) are exactly what's needed to represent the 2nd differences of a sequence and to give the repeated root of 1 . So E n is a sequence with constant 2nd differences of − 1 2 .
Suppose that the spider is moving on a regular N -gon. Let the vertices be labelled 0 , 1 , 2 , . . . , N − 1 , with the fly at vertex 0 . Let E j be the expected time for the spider to reach the fly, given that it is at vertex j and just about to move. Then E j = 3 1 ( 2 + E j ) + 3 1 ( 5 + E j − 1 ) + 3 1 ( 5 + E j + 1 ) = 4 + 3 1 ( E j − 1 + E j + E j + 1 ) for 1 ≤ j ≤ N − 1 , with E 0 = E N = 0 . Thus E j + 1 − 2 E j + E j − 1 + 1 2 = 0 1 ≤ j ≤ N − 1 and hence E j = A + B j − 6 j 2 for 0 ≤ j ≤ N . Since E 0 = E N = 0 we see that E j = 6 j ( N − j ) .
In this case N = 6 , and we want E 3 = 5 4 .