Random "Icosahedron" Walk

Probability Level 3

A bug starts on one vertex of an icosahedron. Every second he randomly walks along one edge to another vertex. What is the expected value of the number of seconds it will take for him to reach the vertex opposite to the original vertex he was on?

Clarification: Every second he chooses randomly between the five edges available to him, including the one he might have just walked along.

Other Expected Value Quizzes

Image credit: www.kjmaclean.com.

The answer is 15.

1 solution

Geoff Pilling
May 24, 2016

We can classify the icosahedron's $12$ vertices into four groups: (1) The vertices neighboring the vertex he starts at, (2) the vertices neighboring the opposite vertex, (3) the vertex he is on, and (4) the opposite vertex. And by symmetry we can call $E_1$ , $E_2$ , and $E$ the expectation values for the number of seconds it will take to get from any vertex in those sets respectively. e.g. $E_1$ is the expectation value for the number of seconds it will take to reach the "opposite vertex" (opposite from where he started) from any vertex in group (1).

This gives us the following set of linear equations:

$E = E_1 + 1$
$E_1 = 1 + (1/5)E + (2/5)E_1 + (2/5)E_2$
$E_2 = 1 + (2/5)E_1 + (2/5)E_2$

Solving for $E$ , gives us $E=\boxed{15}$

See Will's write up below for a more thorough explanation! :^)

It took me a long time to understand what's happening here, let me expand in more detail.

There are four stages of the journey - starting vertex A; the adjacent set of 5 vertices B; the next set of 5 vertices C; and the finishing vertex D. (Look at an icosahedron to see why).
The Expected Time for a particular vertex, is the sum of the Expected Times for all adjacent vertices - plus in each case 1 second for the time to get there - weighted by the probability of the bug choosing to walk to each respective vertex.
Expected Time from A (call it Ea). 100% of the time, the bug takes 1 second to move to a vertex in set B, at which point the Expected Time is whatever it is for B (Eb). Therefore Ea = 1 + Eb.
Expected Time from vertices in set B (Eb). 2/5 of the time, the bug takes 1 second to move forward to a vertex in set C; 2/5 of the time 1 second to move to another vertex in set B; 1/5 of the time, it takes 1 second to go back to vertex A. Therefore Eb = (2/5 x (Ec + 1)) + (2/5 x (Eb + 1)) + (1/5 x (Ea + 1)).
Expected Time from vertices in set C (Ec). 2/5 of the time, the bug takes 1 second to move back to a vertex in set B; 2/5 of the time 1 second to move to another vertex in set C; 1/5 of the time, it takes 1 second to move forward to vertex D. Therefore Ec = (2/5 x (Eb + 1)) + (2/5 x (Ec + 1)) + (1/5 x Ed + 1)).
Expected Time from D (Ed) = 0. The bug has already arrived!

If you crunch crunch crunch these four simultaneous equations (and don't make silly mistakes like I did all afternoon), eventally you'll see that Ea = 15 seconds.

Will Hawkes - 5 years ago

Nice explanation, @Will Hawkes !

Geoff Pilling - 5 years ago

Thanks @Geoff Pilling . I enjoyed your other Bug Polyhedron Walk Questions too, nice.

Will Hawkes - 5 years ago

Come on, don't make it look so easy. Geez.

Michael Mendrin - 5 years ago

Hahaha... Nicely done, Michael! :^)

Geoff Pilling - 5 years ago

Random "Icosahedron" Walk

The answer is 15.

1 solution

0 pending reports