## Recursive expectation (part 2)

This post follows the previous recursive expectation post.

### Problem:

There is an equilateral triangle ABC and the bug is in the vertex A. The bug can move only along edges of the triangle. Once it starts going along an edge, it doesn’t change its moving direction until it reaches the next vertex. It starts walking from the vertex A. It takes bug 1 minute to walk between any two vertices. Every time it comes to a new vertex, it makes a random choice about which of other two vertices to go to next. What is the expected time for the bug to return to the starting vertex A?

### Solution 1:

First, completely intuitive solution, without (much) mathematics. It takes one minute for the bug to come to the edge BC. From that edge, each minute there is 1/2 chance that the bug will return to A. Basically we start the experiment that has 1/2 chance of success each time. So, according to the previous post, expected time to get back to A from BC will be 2 minutes, so all together with the first minute, we get the final result – 3 minutes.

### Solution 2:

And now, let’s try to do it pure mathematical way, without much thinking.

Possible solutions for number of minutes (length of trip) to return back to A are 2, 3, 4, … until infinity. If we take one of the possible solutions, let’s say n minutes, how many different paths do we have for this to happen? Basically, we can go from A to B and then go n-2 times between B and C and then the last time, we go back to A, either from B or from C. Another path would be from A to C and then n-2 times between B and C and then the last time, we go back to A. So, for each n, number of possible paths is always 2. Probability for each path of length n is:

$\left ( \frac{1}{2} \right )^n$

So, probability for n-minutes solution to happen is:

$P\left ( n \right ) = \left ( \frac{1}{2} \right )^n \cdot 2 = \left ( \frac{1}{2} \right )^{n-1}$

Now, the solution for the expectation becomes:

$\begin{array}{rcl} E\left ( X \right ) & = & \sum_{n=2}^{\infty }n\cdot\left ( \frac{1}{2}\right )^{n-1} \\ & = & \sum_{n=0}^{\infty }\left [n\cdot\left ( \frac{1}{2}\right )^{n-1} \right ] - 1 \\ & = & \frac{1}{\left ( 1 - \frac{1}{2}\right )^2} - 1 \\ & = & 4 - 1 \\ & = & 3 \end{array}$

which requires some mathematical knowledge, but doesn’t require much of the intuition.

### Solution 3:

This one will actually use recursive expectation (please see the previous post). Expected time from A back to A is equal to expected time from A to edge BC + expected time from edge BC back to A. Expected time from A to BC is 1. Expected time from BC to A (following the logic from the previous post) is:

$\begin{array}{rcl} E\left ( BC\rightarrow A \right ) & = & \frac{1}{2}\cdot1+\frac{1}{2}\left ( 1 + E\left ( BC\rightarrow A \right )\right ) \\ \frac{1}{2} \cdot E\left ( BC\rightarrow A \right ) & = & 1 \\ E\left ( BC\rightarrow A \right ) & = & 2 \end{array}$

So, the overall expectation is:

$\begin{array}{rcl} E\left ( A\rightarrow A \right ) & = & E\left ( A \rightarrow BC \right ) + E\left ( BC\rightarrow A \right ) \\ & = & 1 + 2 \\ & = & 3 \end{array}$

Recursive expectation once again, provides much easier solution than the mathematical one. Additionally, it’s much more intuitive.

WordPress Themes