Enumerative Combinatorics

Sam has $255$ cakes, each labeled with a unique non-empty subset of $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Each day, he chooses one cake uniformly at random out of the cakes not yet eaten. Then, he eats that cake, and all remaining cakes that are labeled with a subset of that cake (for example, if he chooses the cake labeled with $\{1, 2\}$, he eats that cake as well as the cakes with $\{1\}$ and $\{2\}$). The expected number of days that Sam eats a cake before all cakes are gone can be expressed in the form ${p\over q}$, where $p$ and $q$ are relatively prime natural numbers. Find $p+q$.

Fix $n>1$. Let $S=\{1,\ldots,n\}$. In the end, we will set $n=8$ to solve the problem.

Let $\{X_i\}_{i\ge 1}$ be the sequence of random sets as described in the problem. $\{X_i\}$ is a random sequence with random finite length. Let $N$ be the number of days on which cake is eaten, i.e., the length of this sequence.

We will construct a different random sequence of sets $\{X'_i\}_{i\ge 1}$ that is equivalent to $\{X_i\}_{i\ge 1}$, but that is much easier to analyze.

Let $\{X'_i\}_{i\ge 1}$ be an i.i.d. sequence of random sets in which $X'_i$ is chosen uniformly from $2^S$, the power set of $S$ (null set included). Define $I_i$ as follows: \begin{eqnarray} I_1 &=& \begin{cases} 1\text{ if } X'_1 \ne \emptyset\\ 0 \text{ otherwise} \end{cases}\\ I_i &=& \begin{cases}1\text{ if } X'_i \not \subset X'_{j} \mbox{ for all } j<i \\ 0 \text{ otherwise}. \end{cases} \end{eqnarray}

Let $M_i$ be the $i^{\text{th}}$ smallest index $j$ such that $I_j=1$. For example, if $I_1=I_2=I_4=I_6=0$ and $I_3=I_5=1$, then $M_1=3$ and $M_2=5$. Then the random sequence $\{X'_{M_i}\}$ has exactly the same probability distribution as $\{X_i\}$.

Intuitively, $\{X'_i\}$ generates $\{X_i\}$ by repeatedly sampling $2^S$ until the next element of $X_i$ is found. At each step, if the generated $X'_i$ is a subset of some previous $X'_j$, $j<i$, then $X'_i$ is essentially ignored. This is reflected in setting $I_i=0$. Each time a new set $X'_i$ is generated with $I_i=1$, the next element of the sequence $X_j$ is generated.

Let $$ N' = \sum_{i=1}^{\infty} I_i. $$ Observe that, by the argument above, $N'$ has precisely the same distribution as $N$.

We will calculate $\mathbb{E}(N')$. By definition, we see $$ \mathbb{E}(I_i) = \mathbb{P}(I_i=1). $$ Thus, $$ \mathbb{E}(I_1) = 1 - 2^{-n}. $$ For $i>1$, we may condition on the size $s$ of $X'_i$ and use the facts that $X'_i$ are i.i.d. and that a subset of $S$ with $s$ elements has $2^{n-s}$ supersets in $S$, and so $$ \mathbb{P}(X'_i\not \subset X'_j|X'_i\mbox{ has $s$ elements}) = 1 - 2^{-s} \ \mbox{ if $i\ne j$}. $$ We have \begin{eqnarray} \mathbb{P}(X'_i\not\subset X'_j \mbox{ for all }j<i) &=& \sum_{s=0}^n 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (1-2^{-s})^{i-1}. \end{eqnarray} Thus, \begin{eqnarray} \mathbb{E}(N) &=& \sum_{n=1}^{\infty} \mathbb{E}(I_i) \\ &=& 1 - 2^{-n} + \sum_{i=2}^{\infty} \sum_{s=0}^n 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (1-2^{-s})^{i-1} \\ &=& 1 - 2^{-n} + \sum_{s=0}^n \sum_{i=2}^{\infty} 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (1-2^{-s})^{i-1} \\ &=& 1 - 2^{-n} + \sum_{s=0}^n 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (2^s - 1) \\ &=& \frac{3^n - 1}{2^n}. \end{eqnarray}

For $n=8$, this reduces to $$ \mathbb{E}(N) = \frac{205}{8} = 25.625. $$