Expected number of days before all magical seeds become apple trees This is a question that I came across recently.
At the end of day $0$, $6$ magical seeds are planted. On each day following it, each seed has a chance to magically transform into an apple tree with a probability of $\frac{1}{2}$. The outcomes of seeds are independent of each another.
What is the expected number of days for all six seed to have become apple trees?
My solution:
$E(n)$ - number of expected days from the point that there is only n seed(s) left.
So, $E(1)$ - number of expected days for the last seed to grow.
$E(1) = 1 + \frac{1}{2} E(1) \,or \,E(1) = 2$. This we anyway know from a coin flip analogy.
$E(2) = 1 + \frac{2}{4} E(1) + \frac{1}{4} E(2) \,or\, E(2) = \frac{8}{3}$.
This comes from the fact that if at the end of a day, two seeds are left, I have 3 possible events - i) both seeds become trees the next day ($+1$ day). ii) one seed becomes tree and one seed is left (probability $\frac{2}{4}$). So we further add expected number of days for $E(1)$. iii) None of the seeds become a tree (probability $\frac{1}{4}$). So we add further expected number of days for $E(2)$.
Similarly, $E(3) = 1 + \frac{3}{8} E(1) + \frac{3}{8} E(2) +  \frac{1}{8} E(3)$
$E(4) = 1 + \frac{4}{16} E(1) + \frac{6}{16} E(2) +  \frac{4}{16} E(3) + \frac{1}{16} E(4)$
$E(4) = 1 + \frac{4}{16} E(1) + \frac{6}{16} E(2) +  \frac{4}{16} E(3) + \frac{1}{16} E(4)$
$E(5) = 1 + \frac{5}{32} E(1) + \frac{10}{32} E(2) +  \frac{10}{32} E(3) + \frac{5}{32} E(4) + \frac{1}{32} E(5)$
$E(6) = 1 + \frac{6}{64} E(1) + \frac{15}{64} E(2) +  \frac{20}{64} E(3) + \frac{15}{64} E(4) + \frac{6}{64} E(5) + \frac{1}{64} E(6)$
This gives me an answer of $E(6) = \frac{55160}{13671}$. However the answer given is $(\log_2 6)$. I do not understand how the answer got into $\log$. When I calculate both, they are not same values.
Also, are there more generic and faster methods that I could use to get to the answer?
 A: Let $X_i$ the time of growth of the $i$th seed, $X$ the time until all grow.
$X_i\sim Geom (0.5)$ so $\Pr(X_i\leq t)=1-0.5^t$ for $t=1,2,\ldots$.
$X$ is the maximum of $X_1,\ldots,X_6$ so $\Pr(X\leq t)=\prod\limits_{i=1}^6\Pr(X_i\leq t)=(1-0.5^t)^6$ and $\Pr(X=t)=\Pr(X\leq t)-\Pr(X\leq t-1)=(1-0.5^t)^6-(1-0.5^{t-1})^6$
Finally, $E(X)=\sum\limits_{t=1}^\infty t\Pr(X=t)=\sum\limits_{t=1}^\infty t\left((1-0.5^t)^6-(1-0.5^{t-1})^6\right)=4.034$ (used Wolfram; I guess there are general methods to compute it) so I guess you are correct and I don't understand the $\log_2(6)$ either.
It could come from an argument like "each day half of the seeds become trees, so we need $\log_2(6)$ days for all to turn trees" but I don't see why this is correct.
A: Let $X_i$ be the r.v. corresponding to the number of the day where the $i$-th seed become an apple tree. Obviously, for all $i=1, ..., 6$ and for all $n \geq 1$,
$$\mathbb{P}(X_i = n) = \frac{1}{2^n}$$
What you are asked to compute is
$$\mathbb{E}(\max(X_i))$$
But for all integer $n \geq 1$,
$$\mathbb{P}(\max(X_i)=n) = \mathbb{P}(\max(X_i) \leq n) - \mathbb{P}(\max(X_i) \leq n-1) = \prod_{i=1}^6 \mathbb{P}(X_i \leq n) - \prod_{i=1}^6 \mathbb{P}(X_i \leq n-1)$$
$$=\left( 1 - \frac{1}{2^n} \right)^6-\left( 1 - \frac{1}{2^{n-1}} \right)^6$$
And $$\mathbb{E}(\max(X_i)) = \sum_{n=1}^{+\infty} n \left[\left( 1 - \frac{1}{2^n} \right)^6-\left( 1 - \frac{1}{2^{n-1}} \right)^6\right]$$
A: The problem can be restated as: given the random geometric variables $X_i$ for $1 \leq i \leq 6$, find $$E[\max_i(X_i)]$$
There is in fact no closed form expression, but there are ways to approximate the answer. See this question, or Bennett Eisenberg's paper "On the expectation of the maximum of IID geometric random variables" (Statistics and Probability Letters 78 (2008) 135-143). The answer $\log_2(6)$ seems to be an approximation by considering the expectation of the maximum of i.i.d exponentially distributed variables with parameter $\log(2)$ (the exponential distribution is the continuous analogue of the geometric distribution). This expectation is equal to $$\frac{1}{\log(2)}\sum_{k=1}^6 \frac{1}{k}$$The harmonic sum can be (very badly) approximated by $\log(6)$, giving you the approximation you want.
