7
$\begingroup$

An ant has three passages to choose from:

  1. Passage A takes 7 minutes to get ant out of the ant house to the woods.

  2. Passage B takes 8 minutes to get ant back to the starting point where he is.

  3. Passage C takes 12 minutes to get ant back to the starting point where he is.

The ant chooses a passage randomly until it gets out of the ant house to the woods.

How to calculate the expected average time ant needs to get out?

Does simple mean value (7 + 8 + 12) / 3 = 9 answer the question?

| cite | improve this question | | | | |
$\endgroup$
  • 9
    $\begingroup$ Note that if the ant doesn't get out on the first try in 7 minutes, he will take at least 15 minutes to get out. To get an average time of only 9 minutes, the ant would have to escape on the first try more than half the time, which we know isn't the case. Just trying to give an intuitive idea of what range of answers might make sense, as a sanity check to rule out possible lines of thought - we can see that the mean answer is too low. $\endgroup$ – Nuclear Wang Jan 30 at 19:17
  • 1
    $\begingroup$ If there is only one way out and $n-1$ ways of wasting time then the simple sum answers the question $\endgroup$ – Henry Jan 31 at 12:38
  • $\begingroup$ This is same as this popular question. $\endgroup$ – StubbornAtom Feb 1 at 19:50
25
$\begingroup$

$$T=7/3+(8+T)/3+(12+T)/3=9+2T/3$$ $$T/3=9$$ $$T=27$$ From start point, each of 3 paths are equally possible. Two paths lead you back to start point.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ What is ` 8+T` and 12+T ? $\endgroup$ – dokondr Jan 30 at 17:44
  • 5
    $\begingroup$ +1 Very elegant! @dokondr $T$ is the expected time the ant will take to get out of the forest. If it goes on passage $B$ or $C$ it's back to square one, and has to embark on a journey with expected time $T$ all over again, plus the time it took for that particular passage. $\endgroup$ – Bridgeburners Jan 30 at 18:14
  • 1
    $\begingroup$ So it is a recurrent definition of T $\endgroup$ – dokondr Jan 30 at 19:14
  • 4
    $\begingroup$ $T$ is not defined recursively, but the initial formula is a recursive relationship that arises out of the definition of the expectation. $\endgroup$ – whuber Jan 30 at 22:07
  • 1
    $\begingroup$ It's not a recursive definition of T; it's just an equation which is true of T, where T is the entire left-hand side and where T also appears on the right-hand side. $\endgroup$ – Tanner Swett Jan 31 at 14:03
10
$\begingroup$

To answer this question, you have to sum over all possible paths the ant can take, and get the duration of that path, multiplied by the probability of taking that path. That is, $$ E[T] = \sum_{\text{path} \in \text{possible paths}} p(\text{path}) T(\text{path}) $$

Every possible path takes Passage $A$ only once, but can take passages $B$ and $C$ any number of times, in any permutation. So possible paths can be $A$, $BA$, $BBCCA$, $BCCBA$, etc.

Suppose the probabilities of choosing passages $A,$ $B,$ and $C,$ are $p_a$, $p_b$, and $p_c$ respectively. Then, for example, the probability of taking path $CBBCCA$ is $p_a p_b^2 p_c^3.$ And, because there are ${5 \choose 2} = 10$ ways of taking $B$ twice and $C$ three times, the contribution of the expected path time given by the possibility of 3 $C$s and 2 $B$s is $10 p_a p_b^2 p_c^3 (T_a + 2 T_b + 3 T_c)$, where $T_a$, $T_b$, and $T_c$ are the path times of each passage respectively.

The above gives the contribution to the expected time for taking two $B$s and three $C$s before $A$. But in general, you have to sum over the expected time contribution of all possible combinations of paths $B$ and $C$ before $A$ I'll do that below, but I suggest you stop here and try it yourself first.


SPOILER

In general, the ant can take a non-$A$ passage any number of times between zero and infinity before taking passage $A$, and for that number of times, it can be any combination of passages $B$ and $C$. So, to get the expected path time, we sum up the contribution of all passage possibilities, multiplied by their time, which looks like,

$$ E[T] = T_a + p_a \sum_{n=0}^\infty \sum_{i=0}^n {n \choose i} p_b^i p_c^{n-i} [i T_b + (n-i) T_c]. $$

These sums can be evaluated. Using the Binomial theorem and taking the derivative, you can show that, $$ \sum_{i=0}^n i {n \choose i} x^i y^{n-i} = n x (x+y)^{n-1} $$ and

$$ \sum_{i=0}^n (n-i) {n \choose i} x^i y^{n-i} = n y (x+y)^{n-1}. $$

Using these identities, we get

$$ E[T] = T_a + p_a (p_b T_b + p_c T_c) \sum_{n=0}^\infty n (p_b + p_c)^{n-1}. $$

Taking the derivative of the sum of the famous geometric series, you can show that, for $|x| < 1$,

$$ \sum_{n=0}^\infty n x^{n-1} = \frac{1}{(1 - x)^2}. $$

Noting that $1 - (p_b + p_c) = p_a$, we get,

$$ E[T] = T_a + \frac{1}{p_a} (T_b p_b + T_c p_c). $$

If we take $p_a = p_b = p_c = 1/3$ and your values for the times, we get $E[T] = T_a + T_b + T_c$ which is 27 minutes.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Great explanation! $\endgroup$ – Davide ND Jan 30 at 15:19
8
$\begingroup$

Hello donkordr and welcome to CV.
No, the mean does not answer the question unfortunately.

You can read your problem as a Markov Chain with two states: woods, and ant house.
Now, your transition probabilities are:

  • From the woods: (does not really matter as it's the goal) $p=1$ to stay in the woods
  • From the ant house: $p_1=\frac{2}{3}$ to stay at the ant house and $p_2=\frac{1}{3}$ to go to the woods

We want to know how many movements it takes on average to reach the woods - and you can do so as explained here

This results in an average of 3 movements.
Of these 3 movements, one and only one will be the one leading to the woods, while the rest will be any of the others. The average time of a movement that does not go to the woods is $(8+12)/2 = 10$ minutes.

As a result, the average time before you reach the woods is $27$ minutes: $7$ from the last step, and $2\cdot10$ from the previous ones.

PS - there are other ways to make this computation with intermediate states that might be cleaner, but this seemed easy enough.

| cite | improve this answer | | | | |
$\endgroup$
5
$\begingroup$

Let me join with an explanation which, to me at least, seems even easier:

First, observe that the paths $B$ and $C$ can be joined into a single path $X$, with the passage time equal to the mean times of $B$ and $C$, i.e. $10$ minutes. This is due to the fact that these paths have the same probability. If they didn't, we'd need to take a weighted average. The probability of taking the path $X$ is the sum of probabilities of taking either the path $B$ or $C$: $P(X) = P(B) + P(C) = 2/3$.

Now, there are the following ways of getting to the woods:

$$\begin{array}{lrr} i & \text{path}_i & P(i) & T(i)\\ \hline 0 & A & 1/3 & 7\\ 1 & XA & 2/3 \cdot 1/3 & 10 + 7 \\ 2 & XXA & (2/3)^2 \cdot 1/3 & 20 + 7 \\ 3 & XXXA & (2/3)^3 \cdot 1/3 & 30 + 7 \\ & ... & \\ i & (i \cdot X)A & (2/3)^i \cdot 1/3 & 10\cdot i + 7 \end{array}$$

and the expected time is:

$$\begin{array}{lcl} E(T) & = & \sum_{i=0}^\infty P(i)T(i) \\ & = & 1/3 \cdot \sum_{i=0}^\infty \left( 10 \cdot i + 7 \right) \cdot(2/3)^i \\ & = & 10/3 \cdot \sum_{i=0}^\infty i \cdot(2/3)^i + 7/3 \cdot \sum_{i=0}^\infty (2/3)^i\\ & = & 10/3 \cdot 6 + 7/3 \cdot 3 \\ & = & 27 \\ \end{array}$$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks! Very nice explanation. Yet how do you get sum(i * (2/3)**i) equal to 6? And sum((2/3)**i) equal to 3 ? $\endgroup$ – dokondr Jan 30 at 17:11
  • 1
    $\begingroup$ @dokondr Use the formula for sum of infinite geometric series. $\sum_{n=1}^\infty n x^n=\frac{x}{(x-1)^2}$ and $\sum_{n=0}^\infty x^n=\frac{1}{1-x}$. $\endgroup$ – mai Jan 30 at 22:30
5
$\begingroup$

Typical way to solve this:

The ant will either take path a and finish or take path b or c and be back in it's starting position.

Let $k$ be the number of times that the ant already has taken path b or c. Let $T_k$ be the expectation value for the time to finish for an ant that took already $k$ times the path. Then the expectation value for an ant with $k$ steps can be expressed in terms of an ant with $k+1$ steps.

$$T_k = \underbrace{\frac{1}{3} 7}_{\substack{\frac{1}{3}th\text{ chance to finish with path} \\ \text{ a in 7 minutes }}} + \underbrace{\frac{1}{3} (T_{k+1} + 8)}_{\substack{\frac{1}{3}th\text{ chance to finish with path b} \\ \text{ in 8 minutes} \\ \text{plus what ant $k+1$ needs on average }}} + \underbrace{\frac{1}{3} (T_{k+1} +12)}_{\substack{\frac{1}{3}th\text{ chance to finish with path c} \\ \text{ in 12 minutes}\\ \text{ plus what ant $k+1$ needs on average }}}$$

Since the ants are in the same starting position independent from the history (number of steps $k$) the average time is (you have $T_k = T_{k+1}$ which you can use to solve the above equation) :

$$T_k = \frac{1}{3}7+\frac{1}{3}(8+T_k)+\frac{1}{3}(12+T_k)$$

and after some rearrangments

$$T_k = 7+8+12 = 27 $$


Using an average

You can solve this with a mean, sort of.

  • The ant finishes at least with path a which at least takes at least 7 minutes
  • In addition, the ant has 2/3 probability to take paths b or c (each time) which take on average $\frac{8+12}{1+1} = 10$ minutes.

The mean times that the ant takes paths b or c is:

$$1 \cdot \frac{1}{3}\left(\frac{2}{3}\right) + 2 \cdot \frac{1}{3}\left(\frac{2}{3}\right)^2 + 3 \cdot \frac{1}{3}\left(\frac{2}{3}\right)^3 + 4 \cdot \frac{1}{3}\left(\frac{2}{3}\right)^4 + .... = \sum_{k=1}^\infty k \cdot \frac{1}{3}\left(\frac{2}{3}\right)^k = 2$$

note that this is related to a geometric distribution and the average number of extra steps that the ant needs is 2 (and each step takes on average 10 minutes). So the ant will take (on average):

$$ \text{ $7$ minutes $+$ 2 times $\times$ $10$ minutes $= 27$ minutes}$$


Interestingly: you could also say the mean time for a single step is $9$ minutes (what you computed), and the mean number of steps is $3$, so the ant takes $3 \times 9 = 27$ minutes (you were not very far from the solution).

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ "Interestingly: you could also say the mean time for a single step is 9 minutes (what you computed), and the mean number of steps is 3, so the ant takes 3×9=27 minutes (you were not very far from the solution)." Is this solution guaranteed? Or just an approximation that happens to be correct $\endgroup$ – Cruncher Jan 31 at 19:07
  • $\begingroup$ After reasoning about this problem, it does appear that it actually does work for every combination of values. Definitely unexpected. $\endgroup$ – Cruncher Jan 31 at 19:24
  • $\begingroup$ @cruncher, I agree with you that at first it feels a bit simplistic to multiply two averages, because that is indeed not guaranteed to work every time. So I have to still look into that 'interestingly 3×9=27 part' which seems to be indeed a happy coincidence. But the 2×10 minutes seems sound to me. You can multiply the average number of steps with the average time per step when they are independent. Under the hood you are summing each possible combinations of step times with each possible number of steps. $\endgroup$ – Sextus Empiricus Jan 31 at 21:04
2
$\begingroup$

Commenting on @Igor F.'s post (not enough reputation in this subforum to simply comment):

Both terms are geometric series:

$\sum_{i=0}^\infty i\cdot (\frac{2}{3})^i \overset{q=2/3}{=}\sum_{i=0}^\infty i\cdot q^i=q \frac{d}{dq}\sum_{i=0}^\infty q^i=\frac{q}{(1-q)^2}, \text{ for } |q|<1$, so for $q=\frac{2}{3}$ this equals $6$.

$\sum_{i=0}^\infty (\frac{2}{3})^i$ is just a basic infinite geometric series and we have $\sum_{i=0}^\infty c\cdot q^i=\frac{c}{1-q}, \text{ with constant }c \text{ and } |q|<1$, which is $3$ for $q=\frac{2}{3}$ and $c=1$.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

It always take $7$ min to succeed, which happens once. It takes an average of $10$ min to fail. The probability of failing is $2/3$ on each try, or $(2/3)^n$ for n tries. So the total time is ($7 + 10\cdot \sum_n (2/3)^n$) min. Which is $7$ min + $2 \cdot 10$ min $ = 27$.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.