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 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.

First, let's dispense with the 2 second waiting periods.  The expected value of the waiting time before a left or right decision is made is the infinite sum of 2/3 + 2/9 + 2/27 + ... = 1 second.  So for expected value purposes, the problem can be restated without any waiting times as:  there is a 50:50 chance of a left vs right decision and the travel time between nodes is 6 seconds.
Since the spider and fly are on nodes of opposite parity, there must always be an odd number of steps, the shortest being 3, so le't call the number of steps:  2n+3.

At first, I started to consider any travel trajectory as a binary number (0 for left, 1 for right).  I worked this through and got the same solution, but it was quite tedious, although this might be the best way if done with a computer program.

Next I started thinking of the spider of having 4 "states" 0 through 3, defined as the number of moves away from his starting point.  Every first move goes from state 0 to state 1.  Every last move goes from state 2 to state 3.  In fact, every second to last move goes from state 1 to state 2.  For trajectories longer than 3 moves, if you eliminate the first one and the last 2 moves, all other moves occur in pairs that start at state 1 and end at state 1.
First move:  (state 0 to state 1) 2 possible combinations and both are part of winning trajectories.
Each subsequent pair of moves except the last pair:  (state 1 to state 1) 4 possible combinations and 3 of the 4 successfully end at state 1
The last pair: (state 1 to state 3)  4 possible combinations but only 1 of the 4 successfully end at state 3.

So the number of 2n+3 step trajectories is:
(2/2) * (3/4)^n * (1/4)
n  steps  Probability
0   3   1/4
1   5   3/16
2   7   9/64
n  2n+3  3^n/(2^(2n+2))

For each n, multiply:
 the # of steps, times
 the Probablity of a meal after that many steps, times
 6 seconds
And then sum all of those.

Answer:  54 seconds.

Posted by Larry on 2019-09-12 10:19:23