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.

Rolling dice expectation

The day after my previous expectation related post, I kind of realised what lies behind intuitive answer to the question:

“What is the expected number of times we need to roll a dice to get ‘6’ for the first time?”

Answer 1:

The question above is equivalent to the following. Let’s roll the dice large number of times. We will get long sequence, like:

3, 4, 6, 5, 6, 1, 2, 4, 3, 5, 1, 4, 5, 6, 6, …

Next, let’s cut the tail off after the last ‘6’. Let’s mark the length of the remaining sequence with N. Now we need to count “distances” between every two consecutive ‘6’s. In our example above, we will get 3, 2, 9, 1, … Distance is defined as the number of rolls between two consecutive ‘6’s. Since ‘6’s are at positions: 3, 5, 14, 15, … in the sequence above, distances are 3, 5-3=2, 14-5=9, 15-14=1, … The answer to the question, about the expected number of times, is the same as the average distance between every two consecutive ‘6’s. Let’s mark distances with the sequence: . is the total number of distances. Basically, will correspond to the number of experiments performed. The cut off tail is unfinished last experiment, which we decided to ignore. If X is the number of tries to get ‘6’ for the first time, we can write:

Furthermore, sum of all distances must be equal to the total number of tries – N.

Since is the number of distances, it is also the number of ‘6’s in the whole sequence. Since there is no reason for any number on the dice to appear (by expectation) different number of times than any other number (on the dice), we expect for to be:

 If we replace last two equations in the formula for E(X), we get:

and no mathematics knowledge was needed for this proof. So, maybe this is what lies behind the instinctive answer.

Answer 2:

If we write down the results of each experiment (experiment is said to be finished once we get ‘6’ for the first time):

Since there are experiments, we have exactly 6’s, but we also expect to have each other dice number also times, so the sum of all lengths of all experiments is expected to be , which makes average length to be .

Recursive expectation

I’ll start this with an example:

What is the expected number of tries to get ‘6’ when rolling dice?

Or even simpler, experiment is performed where the dice is thrown as many times as necessary to get ‘6’ for the first time. Save the number of throws for this experiment. Repeat the same experiment many times. What is the average value of throws in all experiments?

Some people would immediately say: “6”. Why 6? Because the probability to get ‘6’ on each throw is 1/6, so the expected number of throws will be:

Although intuitively everything looks fine, formal proof is far from trivial:

but one must be more than intermediate mathematician to be able to go through this proof. I will not go through the details since it’s not the purpose of this post.

There is also a very intuitive solution as well, for which you don’t need to be some mathematician:

and it’s fairly easy to come to solution from this simple equation. What does this equation say? It says that there is 1/6 chance that our experiment will be finished after only one throw (we get 6 from the first try), or there is 5/6 chance that it will be longer. In this case it will be 1 throw longer than what we expected before the first throw. This is probably the hardest part to imagine. If we don’t get 6 from the first throw, we are basically at the same place where we were before we even started the experiment. The only difference is that counter is already on 1 and not on zero as it was before we started the experiment.

To put it even simpler. Let’s say that we do this experiment 600,000 times. 1/6 of them will be finished after first throw, because 1 in 6 times, we’ll get 6 in the first attempt. So, there will be 100,000 experiments out of 600,000 times for which the result will be 1 throw. The rest of 500,000 experiments will have, by average, one throw more than the average in all 600,000 experiments. What is then the average for all 600,000 experiments.

which is basically the same as formula above. It’s very easy to get the result .

Generalization

If we keep on trying succeeding the event that has probability p, how many times is expected to try it until the first success?

Programming solution

Following c# code will prove the dice problem using Monte Carlo simulation.

using System;

namespace RecursiveExpectation
{
    class Program
    {
        static void Main()
        {
            var r = new Random((int)DateTime.Now.Ticks);
            var total = 0;

            // repeat experiment 10000 times
            for (var game = 1; game <= 10000; game++)
            {
                // number of throws in the current game
                var throws = 0;

                // current number on the dice
                var dice = 0;

                // roll the dice until we get '6'
                while (dice != 6)
                {
                    // choose the random number between 1 and 6
                    dice = r.Next(1, 7);

                    // increase the number of throws
                    throws++;
                }

                // total sum of throws in all games
                total += throws;

                // calculate average number of throws in
                // all experiments (games)
                var avg = (double)total / game;

                Console.WriteLine(avg);
            }
            Console.WriteLine("Finished");
            Console.ReadLine();
        }
    }
}