Sam ha $255$ tortas, cada una etiquetada con un único no-vacío es subconjunto de a $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Cada día, elige un pastel uniformemente al azar fuera de los pasteles y aún no se come. Entonces, él se lo come el pastel, y el resto de los pasteles que están etiquetados con un subconjunto de ese pastel (por ejemplo, si elige la torta de la etiqueta $\{1, 2\}$, se come el pastel, así como los pasteles con $\{1\}$$\{2\}$). El número esperado de días que Sam se come un pastel antes de que todos los pasteles se han ido puede ser expresado en la forma ${p\over q}$ donde $p$ $q$ son relativamente primos números naturales. Encontrar $p+q$.
Respuesta
¿Demasiados anuncios?
Will Nelson
Puntos
3966
Fix $n>1$. Deje $S=\{1,\ldots,n\}$. En la final, vamos a establecer $n=8$ a resolver el problema.
Deje $\{X_i\}_{i\ge 1}$ ser la secuencia de grupos aleatorios como se describe en el problema. $\{X_i\}$ es una secuencia aleatoria aleatoria longitud finita. Deje $N$ el número de días en que el pastel se come, es decir, la longitud de esta secuencia.
Vamos a construir una diferente secuencia aleatoria de los conjuntos de $\{X'_i\}_{i\ge 1}$ que es equivalente a $\{X_i\}_{i\ge 1}$, pero que es mucho más fácil de analizar.
Deje $\{X'_i\}_{i\ge 1}$ ser un yo.yo.d. secuencia aleatoria de los conjuntos en que $X'_i$ es elegido de manera uniforme de $2^S$, el juego de poder de $S$ (null conjunto incluido). Definir $I_i$ como sigue: \begin{eqnarray} I_1 &=& \begin{cases} 1\text{ if } X'_1 \ne \emptyset\\ 0 \text{ otherwise} \end{casos}\\ I_i &=& \begin{cases}1\text{ if } X'_i \not \subset X'_{j} \mbox{ for all } j<i \\ 0 \text{ otherwise}. \end{casos} \end{eqnarray}
Deje $M_i$ $i^{\text{th}}$ menor índice de $j$ tal que $I_j=1$. Por ejemplo, si $I_1=I_2=I_4=I_6=0$$I_3=I_5=1$,$M_1=3$$M_2=5$. A continuación, la secuencia aleatoria $\{X'_{M_i}\}$ tiene exactamente la misma distribución de probabilidad como $\{X_i\}$.
Intuitivamente, $\{X'_i\}$ genera $\{X_i\}$ por muestreo repetitivo $2^S$ hasta el siguiente elemento de $X_i$ se encuentra. En cada paso, si el generado $X'_i$ es un subconjunto de algunos de los anteriores $X'_j$, $j<i$, a continuación, $X'_i$ es esencialmente ignorada. Esto se refleja en el establecimiento $I_i=0$. Cada vez que un nuevo set $X'_i$ se genera con $I_i=1$, el siguiente elemento de la secuencia de $X_j$ es generado.
Vamos $$ N' = \sum_{i=1}^{\infty} I_i. $$ Observar que, por el argumento anterior, $N'$ tiene exactamente la misma distribución en $N$.
Vamos a calcular el $\mathbb{E}(N')$. Por definición, vemos $$ \mathbb{E}(I_i) = \mathbb{P}(I_i=1). $$ Por lo tanto, $$ \mathbb{E}(I_1) = 1 - 2^{-n}. $$ Para $i>1$, podemos condición en el tamaño de la $s$ $X'_i$ y el uso de los hechos de que $X'_i$ son yo.yo.d. y que un subconjunto de a $S$ $s$ elementos de ha $2^{n-s}$ superseries en $S$, y así $$ \mathbb{P}(X'_i\no \subconjunto X'_j|X'_i\mbox{ ha $s$ elementos}) = 1 - 2^{s} \ \mbox{ si $i\ne j$}. $$ Tenemos \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} Por lo tanto, \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}
Para $n=8$, esto se reduce a $$ \mathbb{E}(N) = \frac{205}{8} = 25.625. $$
