## 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.

## Monster fly

Now I understand my daughter when she asks me: “Daddy, why is your face looking like a monster while swimming?”

## 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?”

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: $d_1, d_2, d_3, \dots d_m$. $m$ is the total number of distances. Basically, $m$ 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:

$E\left ( X \right ) = \frac{1}{m}\sum_{i=1}^{m}d_i$

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

$\sum_{i=1}^{m}d_i=N$

Since $m$ 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 $m$ to be:

$m = \frac{N}{6}$

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

$\begin{array}{rcl} E\left ( X \right ) & = & \frac{1}{\frac{N}{6}} \cdot N \\ & = & \frac{1}{\frac{1}{6}} \\ & = & 6 \end{array}$

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

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

$\begin{array}{rl} E_1: & 3, 4, 6 \\ E_2: & 5, 6 \\ E_3: & 1, 2, 4, 3, 5, 1, 4, 5, 6\\ E_4: & 6 \\ \cdots \\ E_m: & 1, 5, 3, 4, 6 \end{array}$

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

# High hips

Some months ago, I was so desperate since I couldn’t push my hips above the water (after first kick). In fact, it (hips up) was happening occasionally, but most of the time they would come up very close to the surface, but wouldn’t break it. Then, completely by chance, I did a video of myself where I swim fly with much higher pace than usually. Usually, my stroke cycle is longer than 2 seconds, sometimes even 3 seconds when I swim really slowly. I knew it was much slower than race pace which is slightly above 1 second per stroke cycle. So, I made a video and I was very surprised. My hips were so unexpectedly moving nicely (for my standards) above the water :).

So, I had to come up with some conclusions. My first guess was that there was a relationship between the time distance between the second and the first kick and hips height. During the recovery, swimmer’s center of mass reaches its highest point. In this phase of the stroke, especially if it’s a no breathing one, arms, head and shoulders are above the water surface, so buoyancy is weaker than the gravity force, which means that at some moment, center of mass will start falling down. Usually it happens during recovery, that’s why recovery cannot be slowed down significantly. This falling down will not happen in a moment, it is a gradual process. And it will even continue, by inertia, below the equilibrium point. So, if we wait for too long, center of mass could dive deep and we wouldn’t be able to raise our hips above the water surface. But if we kick while we didn’t sink completely yet, we could still have a chance to put our hips above.
This also can explain why it’s much easier to keep the hips high when swimming only with legs. Or one arm drill. When swimming one arm drill, only one arm is out of water, half of head, one shoulder, plus extended arm can create some upforce as well by moving it downwards together with the upper body, or even relative to the upper body if we need more help. It’s harder with the arm next to the body, since it can’t create upforce in that position, unless moved in the opposite direction than during the real stroke.

But this theory doesn’t stand since I learnt how to swim butterfly and lift my hips above the water even when swimming very slow pace. In this “drill” I try to emphasize hips breaking the surface by stopping the moment when they are above the surface. I can even feel it on my lower back when I break the surface.

Talking about slow pace butterfly, I gradually came up with a version of butterfly with slightly modified timing that could literally be swum effortlessly for very long time. This version of butterfly allows even for the recovery to be prolonged. It allows for the swimmer to highly concentrate on every single part of the stroke. And, what is very important, it’s very easy.

This is the same exercise underwater:

The point is to take the arms slowly out of the water after the head is already back into the water. So, there is no moment when both head and arms are above the water which keep our buoyancy in “good” range. Recovery could be very slow too. Second kick is very close to the first one. Basically, both of them happen while the arms are fully extended in gliding position. There is a variation when gliding is quite short and second kick happens almost at the right time, which is slightly harder. Head goes out of water while arms are doing underwater stroke, thus giving necessary lift for the head.

I experimented also with another version of this exercise, with two first kicks. First first kick happens when head enters the water, the second first kick happens when arms enter the water. There is only one second kick. It’s harder since first first kick brings the upper body down (since there are no extended arms to prevent it), so recovery somehow starts with shoulders little bit deeper in the water than usually. Although it could be good exercise for shoulders flexibility

In conclusion, it could be that all of above have something to do with how high hips go. Firstly, if we don’t go too high above the water when breathing, we will sink less afterwards. So, soft head and arms entry is very helpful in that aspect. Secondly, if the pace is high, body doesn’t have time to sink as much as during the low pace butterfly. Thirdly, most probably, lower back flexibility helps it a bit. And what I think helped me a lot was my shallow water drills since they taught me how to swim softly. Shallow water exercises taught me how not to kick too deep (with legs), how to “jump back” into the water softly and how to swim butterfly (almost) effortlessly.

## 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:

$\frac{1}{\frac{1}{6}}=6$

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

$\begin{array}{rcl} E\left ( X \right ) & = & \sum_{n=1}^{\infty}n\cdot P\left ( X=n \right ) \\ & = & \sum_{n=1}^{\infty}n\cdot\frac{1}{6}\cdot\left ( \frac{5}{6}\right )^{n-1} \\ & = & \frac{1}{5}\sum_{n=1}^{\infty}n\cdot\left ( \frac{5}{6}\right )^n \\ & = & \frac{1}{5}\frac{\frac{5}{6}}{\left ( 1-\frac{5}{6}\right )^2} \\ & = & 6 \end{array}$

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:

$\begin{array}{rcl} E\left ( X \right ) & = & \frac{1}{6}\cdot 1+ \frac{5}{6}\cdot \left ( 1+E\left ( X \right ) \right )\end{array}$

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.

$E=\frac{100,000 \cdot 1+500,000 \cdot \left ( E+1 \right )}{600,000}$

which is basically the same as formula above. It’s very easy to get the result $E=\6$.

## 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?

$\begin{array}{rcl} E\left ( X \right ) & = & p \cdot 1 + \left ( 1 - p \right ) \cdot \left ( E\left ( X \right ) + 1 \right ) \\ E\left ( X \right ) \cdot \left ( 1 - \left ( 1 - p \right ) \right ) & = & p + 1 - p \\ E\left ( X \right ) & = & \frac{1}{p} \end{array}$

## 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");