14

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$.

Kay K.
  • 9,931
  • This is essentially a single player, $8$ dimensional version of the game Chomp. Idk if that is relevant to solving the problem though. – JimmyK4542 Dec 29 '15 at 04:37
  • 2
    I simulated this game $100000$ times. The average number of steps taken to eat all the cookies over all $100000$ trials was roughly $25.6575$. – JimmyK4542 Dec 29 '15 at 05:01
  • Deleted my comment. Your calculation for $n=2$ exposed an error in the part of my calculation weighting $2$ into the expected value. – 2'5 9'2 Dec 29 '15 at 05:33
  • In your calculations, the sum of the probabilities of the $8$ orders you have is $\frac{11}{12}$. You are missing $\emptyset \rightarrow {1} \rightarrow {1,2}$ and $\emptyset \rightarrow {2} \rightarrow {1,2}$. – JimmyK4542 Dec 29 '15 at 05:34
  • Oops, you're right.. I fixed it and now it's $\cfrac94$. – Kay K. Dec 29 '15 at 05:35
  • @alex.jordan Sorry $2$ was an error. You might be still right. – Kay K. Dec 29 '15 at 05:41
  • 5
    Conjecture: If we play the game with $2^n$ cookies whose labels are subsets of ${1,2,\ldots,n}$, then the expected number of steps is $(3/2)^n$. – JimmyK4542 Dec 29 '15 at 05:42
  • @KayK. No, my calculation had a different error. $9/4$ is good. – 2'5 9'2 Dec 29 '15 at 05:49
  • 1
    I worked through the case of $n=3$ (8 subsets). It involved drawing a lot of diagrams of cubes and parts of cubes. The answer worked out to 3.375 (assuming I made no mistakes). This is in line with JimmyK4542's $1.5^n$ conjecture. – paw88789 Dec 29 '15 at 19:12

2 Answers2

6

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. $$

leonbloy
  • 63,430
Julian Rosen
  • 16,142
1

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.

Ross Millikan
  • 374,822
  • Assuming that a step includes eating all the subset cookies of the chosen cookie, then a solution needs to take into account that more than one cookie may get eaten in one step. – paw88789 Dec 29 '15 at 04:53
  • This is true if he randomly picks a cookie amongst all $256$ cookies at each step (including the ones he's already eaten). Otherwise, the probability of picking the ${1,2,3,4,5,6,7,8}$ cookie increases as he eats more cookies. – JimmyK4542 Dec 29 '15 at 04:56
  • I think you missed the part where one step can have numerous cookies eaten. – 2'5 9'2 Dec 29 '15 at 04:56
  • @JimmyK4542: No, think of putting the cookies in order and eating them. The expected position of that cookie is $\frac {257}2$. alex.jordan is right, though,that he has fewer cookies to choose from because the ones with few entries get eaten with others. – Ross Millikan Dec 29 '15 at 05:11
  • @RossMillikan Thanks. I added an experiment for the case of {$1,2$}. Based on your solution, the expected steps for that case should be $\frac52$ but I get $2$... – Kay K. Dec 29 '15 at 05:29
  • @RossMillikan Sorry I think it's $\frac94$. – Kay K. Dec 29 '15 at 05:39