Problem 64. Half Cookies

-

There are 15 cookies in a container. Each day, we randomly pick one of the contents of this container. If it is a whole cookie, we eat half of it and put the other half back in the container. If it is a half-eaten cookie, we eat it.

What is the expected number of half-eaten cookies in the container when we take out the last whole cookie?

-

The solution to the problem is approximately 2.3182.
We number the cookies in the order they are removed from the container (for the first time). Therefore, the half-cookie that is placed in the container after halving the \(k\)-th whole cookie is numbered \(k\). We define random variable \(X_k\) to be 1 if the \(k\)-th half-cookie is removed from the container after the last whole cookie, and 0 otherwise. Since we wish to find the expected number of the half-cookies that are removed after the 15th whole cookie, the answer to the problem is

\[E(X_1 + X_2 + ... + X_{14}) = E(X_1) + E(X_2) + \ldots + E(X_{14}).\]

After the \(k\)-th half-cookie is returned to the container, there are still \(15 - k\) whole cookies in the container, and \(X_k\) = 1 if and only if the \(k\)-th half-cookie is the last one to be removed from the container among this set of \(15 - k\) whole cookies and the \(k\)-th half-cookie. Since in each step, the probability of removing any member of this set is the same, we have:

\[E(X_k) = P(X_k = 1) = 1 / (15 - k + 1).\]

Therefore, the answer to the problem is:

\[E(X_1) + \ldots E(X_{14}) = 1/15 + 1/14 + \ldots + 1/2 \simeq 2.3182.\]