Expected days to finish a box of cookies

Adam has a box containing 10 cookies. Each day he eats each cookie with a probability of $\frac12$. Calculate the expected number of days it takes Adam to complete the cookies.

As a start we can set $X$ as the expected days it takes for Adam to finish eating the cookies. However I'm unable to progress further.

Solution 1:

Let $E_n$ denote the expected number of days for Adam to finish a box containing $n$ cookies. For a given $n$ and a given $k$ with $0\le k\le n$, with probability $\frac1{2^n}\binom nk$ Adam will eat $k$ cookies on that day and take an expected $E_{n-k}$ more days to finish the box. From here we can derive an equation for $E_n$: $$\begin{align} E_n&=\sum_{k=0}^n\frac1{2^n}\binom nk(1+E_{n-k})\\ &=\sum_{k=0}^n\frac1{2^n}\binom nk(1+E_k)\\ &=1+\sum_{k=0}^n\frac1{2^n}\binom nkE_k\\ E_n-\frac1{2^n}E_n&=1+\sum_{k=0}^{n-1}\frac1{2^n}\binom nkE_k\\ E_n&=\frac{2^n}{2^n-1}\left(1+\sum_{k=0}^{n-1}\frac1{2^n}\binom nkE_k\right) \end{align}$$ The last line is a formula for $E_n$ in terms of all $E_k$ with $0\le k<n$. Trivially we know that $E_0=0$, which allows us to recursively work our way to $E_{10}$. However, beyond the first terms ($E_1=2$, $E_2=\frac83$, etc.) the sequence gets very unwieldy to compute by hand; I wrote a Python script for this purpose and got $$E_{10}=\frac{1777792792}{376207909}=4.725559\dots$$ So Adam will take this many days on average to empty the box.

Solution 2:

Supposing the cookies are eaten independently, let $X_i$ be the number of days until cookie $i$ is eaten

$X_i \sim Geometric(1/2)$

$P(X_i=k)=(1/2)^k$ for $k\ge 1$

Let $Y=\max(X_1,...,X_{10})$

Then what you want is $E[Y]$

$P(Y\le k)=P(X_1\le k,...,X_{10}\le k)=P(X_1\le k)\cdot...\cdot P(X_{10}\le k)=\left(1-\frac{1}{2^k}\right)^{10}$

(assuming independence)

$P(Y > k)=1-\left(1-\frac{1}{2^k}\right)^{10}$

Then what you want is:

$E[Y]=\sum_{k>0}P(Y>k)$

Solution 3:

I asked my friend Ruby to eat a couple of jars that way. She told me $n = 1000000, \text{avg} = 4.724956$ and feels a bit stuffed now.