¿Adivinar la duración de una lista de reproducción en "aleatorio aleatorio"?

Question

La otra noche estaba con unos amigos y alguien puso una lista de reproducción en aleatorio, donde las canciones se extraen uniformemente al azar de una lista de reproducción fija. La persona que preparó la lista se olvidó de cuántas canciones contenía, así que surgió el tema de cómo calcular el tamaño de la lista basándonos únicamente en lo que oímos.

Se nos ocurrieron algunas ideas de alto nivel sobre cómo hacerlo. Por ejemplo, utilizando ideas de la paradoja del cumpleaños, pensamos que podíamos escuchar hasta que oyéramos una canción repetida por primera vez y, a partir de ahí, hacer una estimación de cuántas canciones había en total en la lista de reproducción. También pensamos que podríamos escuchar durante mucho tiempo y construir un histograma de frecuencias del número de veces que se ha reproducido cada canción, y luego utilizar el hecho de que debería tener un aspecto de distribución normal para obtener la media y la varianza y, a partir de ahí, estimar el número total de canciones de la lista.

Ninguno de nosotros es estadístico ni tiene mucha formación en aprendizaje automático, pero sospecho que probablemente se trate de un problema bien estudiado y que hay algunas técnicas realmente buenas que podemos utilizar para estimar el tamaño de la lista de reproducción.

¿Existe una buena familia de técnicas para estimar el tamaño de la lista de reproducción? Desde un punto de vista práctico, ¿sería alguna de estas técnicas relativamente fácil de calcular sin ordenador ni calculadora?

Gracias.

Answer 1

Desde el Papel Langford&Langford Supongo que has oído $m$ canciones, de las cuales $i$ eran diferentes, y $i<m$ . Se desea hallar el tamaño de la lista de reproducción, cuyo valor más probable (en el sentido de máxima verosimilitud) es $\hat{N}$ que viene dado por $$\hat{N}=\left\lfloor \frac{1}{1-y^\star} \right\rfloor$$ donde $\lfloor \cdot \rfloor$ denota la función suelo, y $y^\star$ denota la raíz positiva más pequeña del polinomio $$y^m-iy+(i-1)=0$$

Nota: si $i=m$ entonces todas las canciones que has escuchado hasta ahora han sido distintas. Entonces no hay forma de estimar el tamaño de la lista de reproducción; por lo que sabemos, podría ser infinita.

Para mayor comodidad, aquí tiene una tabla de valores para $\hat{N}$ todo por $m=10$ . Por ejemplo, si escucha $m=10$ canciones y escuchar $i=7$ diferentes entre ellos, entonces el tamaño más probable de la lista de reproducción es $\hat{N}=12$ .

\begin{array} {|r|r|} \hline i & \hat{N}\\ \hline 1 &1 \\ 2&2\\ 3&3\\ 4&4\\ 5&5\\ 6&8\\ 7&12\\ 8&19\\ 9&42\\ \hline \end{array}

Answer 2

Como sugiere @dsaxton, un método es la "captura-recaptura" (también llamada marcar-recapturar'). Consulte el artículo de Wikipedia para obtener algunos detalles técnicos (si puede lidiar con la notación innecesariamente confusa). He aquí el método básico con un argumento intuitivo.

Método. Escuchar $c = 20$ distintas canciones, anotando sus títulos. A continuación, escucha otra $r = 20$ canciones (también distintas entre sí), y contar las $x$ se repite entre los dos grupos de canciones.

Estimación. Sea $T$ es el número total de canciones de la lista de reproducción. La fracción $x/r$ es la proporción de canciones del primer grupo que también están en el segundo. La fracción $c/N$ es el proporción de canciones de toda la lista de reproducción que están en el primer grupo. Intuitivamente, las dos proporciones deberían ser aproximadamente iguales: $x/r \approx c/N$ lo que conduce a $N \approx cr/x.$ Así que si tuvieras $x = 5$ se repite, entonces se estima que $N = 400/5 = 80$ canciones de la lista de reproducción.

Obviamente, este método no funciona si tiene $x = 0$ se repite, Debido a la posible dificultad con $x = 0$ El estimación no tiene media ni varianza. Esta dificultad se sortea (técnicamente) añadiendo $1$ a cada una de las cantidades de la estimación: $N = (c+1)(r+1)/(x+1).$ Aun así, el método funciona mejor para grandes $x$ (y también para $c$ y $r$ (si tienes paciencia).

Sin duda, el método podría mejorarse mediante un seguimiento continuo de de las repeticiones, pero estas estrategias podrían ser demasiado complicadas de aplicar en el entorno recreativo de tu pregunta ("sin ordenador ni calculadora").

Answer 3

Comentario sobre los resultados de la simulación del método basado en el tiempo hasta la primera repetición.

Método: Sea $Y$ sea la espera (número de canciones) hasta la primera repetición. A continuación, calcula el tamaño $N$ de la lista de reproducción como $\hat N = Y(Y-1)/2.$ Esto sin duda satisface la petición del OP de simplicidad computacional.

Algunos resultados de simulación: Basado en 100.000 iteraciones para cada uno de los diez valores de $N$ de 10 a 200, parece que este estimador es insesgado, $E(\hat N) = N$ pero tiene una relativamente grande (casi tan grande como $N$ ). La distribución de $\hat N$ es fuertemente sesgada a la derecha.

Creo que he visto esto método antes, pero no puedo recordar inmediatamente una justificación rigurosa. Quizás puede extenderse a la espera de algún pequeño número $k > 1$ de repeticiones para obtener un estimador insesgado con una DE menor.

Comentario sobre los resultados limitados de la simulación de captura-recaptura y Langford (recogida inversa de cupones).

No es difícil simular el método de captura-recaptura para ver cómo funciona en un caso concreto. Además, la tabla proporcionada por @vadim123 hace que sea fácil de simular el método Langford para ese caso concreto.

Para que los dos métodos sean lo más comparables posible, supongamos que la longitud real de la lista de reproducción es 50.

En la captura-recaptura supongamos que buscamos coincidencias en dos muestras de cinco canciones, (es decir $c = r = 5$ ). En 100.000 iteraciones obtuvimos una estimación media del tamaño de la lista de reproducción de 28 con una DE de 9,5. La media más dos desviaciones estándar no alcanza el valor real de 50.

En el método Langford contamos los resultados únicos entre diez canciones. En 100.000 iteraciones obtenemos diez canciones únicas (y, por tanto, ninguna estimación) en unas 38.000 de las 100.000 iteraciones. Entre las iteraciones que produjeron estimaciones, la media el tamaño medio de la lista de reproducción estimada fue de 34, con una desviación estándar de 11,5. De nuevo subestimación grave de la longitud de la lista de reproducción cuando cuando tenemos estimaciones, y no obtenemos ninguna estimación útil más de un tercio de las veces.

Es justo decir que escuchar sólo 10 canciones no da resultados brillantes con ninguno de los dos métodos. Mi opinión es que el método Langford funciona mejor cuando el número de canciones observadas es mayor.

Addendum después de algunos comentarios: Una simulación con $N = 35$ (y los mismos tamaños de muestra) da una estimación media de unos 25 con SD 10 para la recaptura por captura; media de unos 31 con SD 13 y ninguna estimación aproximadamente una cuarta parte de las veces con el método Langford. La cuestión sigue siendo que ninguno de los dos métodos parece funcionar muy bien para números pequeños de cantos observados. En lo que a mí respecta, la pregunta sigue esperando una respuesta sencilla y más útil, si es que existe.