14
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ This is essentially a single player, $8$ dimensional version of the game Chomp. Idk if that is relevant to solving the problem though. $\endgroup$
    – JimmyK4542
    Dec 29, 2015 at 4:37
  • 2
    $\begingroup$ 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$. $\endgroup$
    – JimmyK4542
    Dec 29, 2015 at 5:01
  • $\begingroup$ Deleted my comment. Your calculation for $n=2$ exposed an error in the part of my calculation weighting $2$ into the expected value. $\endgroup$
    – 2'5 9'2
    Dec 29, 2015 at 5:33
  • 5
    $\begingroup$ 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$. $\endgroup$
    – JimmyK4542
    Dec 29, 2015 at 5:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – paw88789
    Dec 29, 2015 at 19:12

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Very elegant answer! $\endgroup$
    – leonbloy
    Dec 30, 2015 at 18:41
  • $\begingroup$ Thanks. This is very nice! (There's a minor typo on the last line - length $k$ instead of length $s$.) $\endgroup$
    – Kay K.
    Dec 30, 2015 at 18:45
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – paw88789
    Dec 29, 2015 at 4:53
  • $\begingroup$ 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. $\endgroup$
    – JimmyK4542
    Dec 29, 2015 at 4:56
  • $\begingroup$ I think you missed the part where one step can have numerous cookies eaten. $\endgroup$
    – 2'5 9'2
    Dec 29, 2015 at 4:56
  • $\begingroup$ @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. $\endgroup$ Dec 29, 2015 at 5:11
  • $\begingroup$ @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$... $\endgroup$
    – Kay K.
    Dec 29, 2015 at 5:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .