Expected number of steps to finish all the cookies Please help on this question:

Steve has 256 cookies. Each cookie has a label that is a distinct subset of $\{1,2,3,4,5,6,7,8\}$. At each step, Steve chooses a cookie randomly and eats it as well as all othe cookies whose label is a subset of the chosen one. What is the expected number of steps Steve takes before finishing all the cookies?

All I could find was that he should anyway eat the root cookie with the $\{1,2,3,4,5,6,7,8\}$ to finish the game. But the probability to choose it depends on what kind of cookies he has chosen before he grabs the final one, and I have no idea how to tackle it. Thanks.

I tried to see what happens for a much simplified case. If Steve has 4 cookies that are subsets of {$1,2$}, the possible cases are:
\begin{align}
&\emptyset\rightarrow\{1\}\rightarrow\{2\}\rightarrow\{1,2\}&=4\times\frac14\times\frac13\times\frac12\\
&\emptyset\rightarrow\{2\}\rightarrow\{1\}\rightarrow\{1,2\}&=4\times\frac14\times\frac13\times\frac12\\
&\emptyset\rightarrow\{1\}\rightarrow\{1,2\}&=3\times\frac14\times\frac13\times\frac12\\
&\emptyset\rightarrow\{2\}\rightarrow\{1,2\}&=3\times\frac14\times\frac13\times\frac12\\
&\emptyset\rightarrow\{1,2\}&=2\times\frac14\times\frac13\\
&\{1\}\rightarrow\{2\}\rightarrow\{1,2\}&=3\times\frac14\times\frac12\\
&\{1\}\rightarrow\{1,2\}&=2\times\frac14\times\frac12\\
&\{2\}\rightarrow\{1\}\rightarrow\{1,2\}&=3\times\frac14\times\frac12\\
&\{2\}\rightarrow\{1,2\}&=2\times\frac14\times\frac12\\
&\{1,2\}&=1\times\frac14\\
\end{align}
that sums up to $\cfrac94$.
 A: Let's consider the general case with $2^s$ cookies, labelled with subsets of $\{1,2,\ldots,s\}$. Steve begins by choosing a random ordering of all the cookies. At each step, Steve eats the next available cookie, and instead of eating the remaining cookies whose label is a subset, let's say he simply discards them. The number of steps is equal to the total number of cookies eaten.
A particular cookie will eventually be eaten if and only if that cookie is first among those cookies whose labels are supersets of that cookie's label. If the label on a cookie has size $k$, there are $2^{s-k}$ possible supersets, so the probability that cookie gets eaten is $2^{k-s}$. There are ${s\choose k}$ cookies whose label has length $k$, so by linearity of expectation, the expected number of steps (= cookies eaten) is
$$
\sum_{k=0}^s {s\choose k}2^{k-s}=\left(\frac{3}{2}\right)^s.
$$
A: All you care about is when he eats the $\{1,2,3,4,5,6,7,8\}$ cookie.  If he chooses it he is done, and no other combination of cookies will cause him to eat it.  He chooses cookies until he chooses $\{1,2,3,4,5,6,7,8\}$, which is uniform on $[1,256]$ with expected value $\frac {257}2$  
Added:  as alex.jordan points out, this is not correct.  If he doesn't choose the empty set cookie first, it gets eaten in the first batch and will never get chosen.  This reduces the number of choices before $\{1,2,3,4,5,6,7,8\}$ gets chosen.
