Uso de la recursión para resolver el colector de cupones

Question

He leído un brillante respuesta de Mike Spivey en una de las preguntas y me preguntaba cómo podría utilizarlo para resolver un problema de coleccionistas de cupones.

El problema es : Hay cupones etiquetados como 1,2,3...,10 ¿cuántos cupones tengo que reunir para tener uno de cada etiqueta? Sé que la respuesta es $\displaystyle \sum_{i=1}^{10} \dfrac{10}{i}$

Este es mi intento: Dejemos que $X_i$ sea la variable aleatoria correspondiente al número de cupones que hay que recoger para tener exactamente $i$ etiquetas únicas.

\begin {align} E(X_1)&=1 \\ E(X_2|X_1)&= \dfrac {9}{10}.(X_1+1)+ \dfrac {1}{10}.(E(X_2)) \\ \implies E(X_2)&= \dfrac {9}{10}.(E(X_1)+1)+ \dfrac {1}{10}.(E(X_2)) \\ \text {Similarmente,} \\ E(X_3)&= \dfrac {8}{10}.(E(X_2)+1)+ \dfrac {2}{10}.(E(X_3)) \\ \vdots \end {align} Pero esto me da una respuesta equivocada. Sé que hay un problema en mi segunda ecuación pero no sé por qué. Mi lógica era la siguiente: Asumiendo que sé cuánto se necesita para obtener 1 cupón $(E(X_1))$ con una probabilidad de 9/10 encuentro 2 en $E(X_1)+1$ Si no, sólo tengo $E(X_2)$ .

Tampoco funciona la fórmula de la mencionada pregunta. ¿Puede alguien ayudarme a establecer la ecuación de recursión?

(Si es posible, conserve mis Variables Aleatorias. Me interesa más saber por qué falla mi lógica en el diseño de la recursión que responder a la pregunta original)

Answer 1

Dejemos que $W_1$ sea el "tiempo de espera" (número de compras) hasta el primer cupón, y que $W_2$ sea el tiempo de espera entre el primer cupón y el segundo, y así sucesivamente hasta $W_{10}$ . Entonces recogeremos $X=W_1+W_2+\cdots +W_{10}$ cupones para cuando los tengamos todos.

Queremos $E(X)=E(W_1)+E(W_2)+\cdots +E(W_{10})$ .

$W_1$ es muy simple, es $1$ con probabilidad $1$ , también lo ha hecho la expectativa $1$ .

Después de haber $i$ diferentes cupones, la probabilidad de que un cupón que obtengamos sea nuevo es $\frac{10-i}{10}$ . Así que $W_{i+1}$ es una variable aleatoria geométricamente distribuida con probabilidad de éxito $p=\frac{10-i}{10}$ . Esta variable aleatoria geométrica tiene una media $\frac{1}{p}=\frac{10}{10-i}$ .

Ahora suma.

El análisis anterior puede establecerse como una recurrencia. Sea $X_i$ sea el tiempo hasta el $i$ -el quinto cupón (nuevo). A continuación, $X_{i+1}=X_i+W_{i+1}$ donde $W_j$ es como en la discusión anterior. Tenemos $$E(X_{i+1})=E(X_i)+E(W_{i+1})=E(X_i)+\frac{10}{10-i}.$$

Answer 2

Para seguir tu planteamiento, tienes que tener en cuenta que si fallas en el segundo cupón porque coincide con el primero, no estás en el principio sino en el punto en el que ya tienes uno. Esto dice que tu segunda ecuación debe ser $E(X_2)-E(X_1)=\frac 9{10}\cdot 1 + \frac 1{10}(1+E(X_2)-E(X_1))$ . El primer término proviene del éxito en el siguiente cupón y el segundo dice que con el azar $\frac 1{10}$ sacas uno y vuelves al punto de partida. El hecho de que $E(X_2)-E(X_1)$ es el mismo que André Nicolas $W_2$ muestra el paralelismo entre estos enfoques. El resultado es $\frac 9{10}(E(X_2)-E(X_1))=1$ o $E(X_2)=\frac {20}9$