Posts tagged: triangle

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:

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

Now, the solution for the expectation becomes:

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:

So, the overall expectation is:

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

WordPress Themes

cheap beats by dre beats by dre uk cheap beats moncler outlet moncler sale moncler uk

air max pas cher, nike pas cher, nike blazer pas cher, nike air max pas cher, air max pas cher, air max one, nike air max pas cher, free run, nike free run 2, nike free 5.0