Número esperado de pasos para terminar todas las cookies

Question

Por favor, ayudar en esta pregunta:

Steve tiene 256 cookies. Cada galleta tiene una etiqueta que es un subconjunto distinto de $\{1,2,3,4,5,6,7,8\}$. En cada paso, Steve elige una cookie al azar y se la come, así como todos los otros cookies cuya etiqueta es un subconjunto de la elegida. ¿Cuál es el número esperado de pasos de Steve toma antes de terminar todas las cookies?

Todo lo que pude encontrar fue que debía de todos modos comer la raíz de la galleta con el $\{1,2,3,4,5,6,7,8\}$ para terminar el juego. Pero la probabilidad de que elija depende de qué tipo de cookies que él ha escogido antes de que él se agarra a la final, y no tengo idea de cómo hacerle frente. Gracias.

---

Traté de ver lo que sucede durante un simplifica mucho caso. Si Steve tiene 4 galletas que son subconjuntos de {$1,2$}, los casos posibles son:

\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}

que resume a $\cfrac94$.

Answer 1

Vamos a considerar el caso general con $2^s$ cookies, con la etiqueta de subconjuntos de a $\{1,2,\ldots,s\}$. Steve comienza por la elección de un ordenamiento al azar de todas las cookies. En cada paso, Steve se come la galleta, y en lugar de comer el resto de las galletas, y cuya etiqueta es un subconjunto de, digamos que simplemente se descarta. El número de pasos es igual a la cantidad total de cookies comido.

Un cookie en particular eventualmente ser comido si y sólo si la galleta es la primera entre los cookies cuyas etiquetas son superseries de la galleta de la etiqueta. Si la etiqueta de un cookie tiene el tamaño de $k$, $2^{s-k}$ posible superseries, por lo que la probabilidad de que la cookie se come es $2^{k-s}$. Hay ${s\choose k}$ cookies cuya etiqueta tiene una longitud de $k$, por la linealidad de la expectativa, el número esperado de pasos (= cookies comido) es $$ \sum_{k=0}^s {s\elegir k}2^{k-s}=\left(\frac{3}{2}\right)^s. $$

Answer 2

Todo lo que importa es que cuando se come la $\{1,2,3,4,5,6,7,8\}$ cookie. Si él decide que él es, y no otra combinación de cookies le causan a comer. Elige las cookies hasta que él elige $\{1,2,3,4,5,6,7,8\}$, que es uniforme en $[1,256]$ con valor esperado $\frac {257}2$

Agregado: como alex.jordan señala, esto no es correcto. Si él no elegir el conjunto vacío cookie en primer lugar, se come en la primera tanda y nunca va elegido. Esto reduce el número de opciones antes de $\{1,2,3,4,5,6,7,8\}$ obtiene elegido.