## November 8, 2011

### Ant on a Cube

An ant is placed at one corner of a wire frame in the shape
of a cube. At the diagonally opposite corner is a piece of sugar.
The ant crawls along the all the wires of the frame searching for
the sugar. At each of the 8 corners the ant randomly chooses one of
the 3 wires to follow next (including the one it just traveled)

What is the expected number of edges the Ant will traverse until it
reaches the sugar?

What if the Ant never doubles back on the wire it just crossed?

Raghav said...

Lets say the expected number of steps for ant is a

expected number of steps from 3 corners immediately next to ant is b.

and expected number of steps from 3 corners immediately next to sugar is c.

If ant is at c, it chooses the path for sugar with probability 1/3 which takes (1+0) steps and with 2/3 probability for choosing two 'b' corners which now will take it (1+b) steps.
now c = (1/3)*(1+0)+(2/3)*(1+b) as these corners will have 2 b's next to them and one corner with sugar.
thus c = 1+(2/3)*b

similarly b = (1/3)*(1+a)+(2/3)*(1+c)

thus b = 1+(2/3)*c + (1/3)*a

and similarly a = 1+b
as it is surrounded from all sides by 'b' corner.

all these three equations gives expected number of steps for ant a=10.

Raghav said...

Similarly for 2nd part. Here there will be 2 equations for b.

b(a) is expected number of steps when ant is coming from a to b.

b(c) is expected number of steps when ant is coming from c to b.

a = 1+b(a)

b(a) = 1+c

c = 1+b(c)/2

b(c) = 1+ a/2 + c/2

all equations are formulated on the same logic

This returns a = 6

Caterpillar Turbo said...

You have really done a great work to share the hidden art of the great man. It is really a nice work by them. Thanks a lot for this