edges.
We can categorize the 8 vertices as being one of 4 types: the Start, the End, layer 1 and layer 2.
Layer 1 connects to the Start, layer 2 connects to the end. My labelling has A as the Start, G as the End, and has one way of getting to the goal in 3 moves as A-B-C-G.
If you lay out the cube, flattened into 2 dimensions and draw all the connections, you get something like:
B C
A D F G (Goal)
E H
There are no connections which allow the bug to stay in the same layer: it must move to an adjacent layer.
Let x be the answer we are seeking, the expected value of moves to get from A to G
Let y be the expected number of moves from any of the 1st layer group (B,D,E)
Let z be the expected number of moves from any of the 2nd layer group (C,F,H)
Of course the expected number of moves from G to G is zero.
At A, the next move is always to Layer 1.
At a Layer 1 vertex, the next move 1/3 of the time is back to A; 2/3 of the time to Layer 2.
From a Layer 2 vertex, the next move 1/3 of the time is to G; 2/3 of the time back to Layer 1.
x = y + 1
y = (1/3)x + (2/3)(z) + 1
z = (1/3)*0 + (2/3)(y) + 1
Solving this system gives (x,y,z) = (10, 9, 7).
So the expected number of moves (edges) is 10.
Part 2:
If the bug never doubles back, the equations change and the analysis is more complicated.
When the bug is in Layer 2, it cannot have come from G, it must have come from Layer 1, so it has a 50:50 chance of going back to Layer 1 or to G.
But when the bug is at Layer 1, it matters whether it came from A or from Layer 2.
x = y + 1
y = z + 1 if bug came from A
y = (1/2)x + (1/2)z + 1 if bug came from Layer 2
z = (1/2)*0 + (1/2)(y) + 1
I don't know how to resolve this system.
So look at the problem differently. At the start, the bug will always be at Layer 2 after 2 moves, so let's just start the bug at Layer 2 but starting with a score of 2 moves. Now there is a 50:50 chance it will go on to G in one more move: Exp Val = (1/2)*3 + (1/2)*??
If it goes back to Layer 1, then it is guaranteed to return to Layer 2 in either 1 or 3 moves (each with 50% probability). Or, once at Layer 2, the bug will either go to the sugar or waste 2 or 4 moves. That's an average number of 3 wasted moves.
Analytic
