La comprensión de una recurrencia para resolver el Cupón Colector problema?

Question

Recientemente me encontré con esta recurrencia para el cupón colector problema:

$$\text{draws}(n) = \text{draws}(n-1) \cdot\dfrac{n}{n-1} + 1$$

donde $\text{draws}(n)$ que se espera que el número de cupones que se adopte para obtener todos los $n$ único cupones.

¿Por qué es esto de la recurrencia de la verdad? Yo preferiría un enfoque intuitivo.

Answer 1

Ah, he descubierto la idea detrás de esto. El siguiente argumento que dan es algo nonrigorous y me gustaría tratar con sospecha, pero al menos nos transmite la idea básica de la que luego se puede tomar como punto de partida para una búsqueda de un argumento puede ser confiado en.

---

Para dibujar $n$ distintos cupones, usted debe:

• sorteo de un cupón
• sorteo de uno de cada clase de los restantes $n-1$

El segundo punto es casi el cupón colector problema para $n-1$ tipos de cupones; la diferencia es que una fracción $\frac{1}{n}$ de sus retiros "no cuentan", ya que eran del mismo tipo que el primer cupón.

En otras palabras, en promedio, usted tiene que hacer $\frac{n}{n-1}$ sorteos para conseguir uno más de la pica en el $n-1$ cupón subproblem. Por lo tanto,

$$ \text{draws}(n) = 1 + \frac{n}{n-1} \text{draws}(n-1) $$

Answer 2

Con "dibuja(n)" usted parece decir el número esperado de sorteos para obtener todos los elementos, si $n$ tienen que ser recogidos.

La probabilidad de obtener un objeto que ya no está dibujado, disminuye de $\frac{n}{n}=1$ downto $\frac{1}{n}$. Así, se espera que el número de sorteos necesita es $$E_n=\sum_{j=1}^n \frac{n}{j}=n\cdot H(n)$$

Para ello contamos $$E_{n-1}=\sum_{j=1}^{n-1} \frac{n-1}{j}$$

Esto implica $$\frac{n}{n-1}\cdot E_{n-1}=\sum_{j=1}^{n-1}\frac{n}{j}$$ hence $$E_n=\frac{n}{n-1}\cdot E_{n-1}+ \frac{n}{n}=\frac{n}{n-1}\cdot E_{n-1}+1$$