Problema del coleccionista de cupones

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Gráfica del número de cupones n contra el número esperado de pruebas (es decir, el tiempo) necesario para tener una colección completa de ellos, E (T )

En probabilidad y estadística, el problema del coleccionista de cupones describe los concursos del tipo «colecciona todos los cupones y gana». Se trata de la siguiente pregunta:

Cierta marca de cereales contiene un cupón en cada caja. Si hay distintos tipos de cupones, ¿cuál es la probabilidad de que se necesitarán más de cajas para coleccionar todos los cupones? De forma alternativa: dados cupones, ¿cuántas muestras aleatorias con reemplazo se pueden esperar para poder seleccionar cada tipo de cupón al menos una vez?

El análisis matemático del problema revela que el valor esperado de pruebas necesarias crece a razón de .[Nota 1]​ Por ejemplo, cuando la respuesta es aproximadamente 225[Nota 2]​ pruebas en promedio para coleccionar todos los 50 cupones.


Solución[editar]

Cálculo del valor esperado[editar]

Sea el tiempo el número de pruebas necesarias para coleccionar todos los cupones, y sea el tiempo para coleccionar el -ésimo cupón después de que se tienen cupones en la colección. Entonces . Se puede pensar en y como variables aleatorias. Se debe observar que la probabilidad de añadir un cupón nuevo es . Por lo tanto, tiene una distribución geométrica con valor esperado . Por la linealidad de la esperanza se tiene:

Aquí, es el -ésimo número armónico. Usando la asíntota de los números armónicos, se obtiene:

donde es la Constante de Euler–Mascheroni.

Aquí es posible usar la desigualdad de Márkov para establecer límites a la probabilidad deseada:

Se puede ver que la anterior puede ser modificada levemente para el case en el que ya se tienen algunos de los cupones. sea el número de cupones ya coleccionados, entonces:

Se aprecia que cuando se obtiene el resultado original.

Cálculo de la varianza[editar]

Usando la independencia de las variables aleatorias se obtienen:

ya que (véase problema de Basilea).

Ahora es posible usar la desigualdad de Chebyshev para establecer la cota:


Estimaciones de cola[editar]

Es posible establecer una cota superior diferente a partir de la siguiente observación. Sea el evento en el que el -ésimo cupón no fue seleccionado en las primeras pruebas. Entonces:

Por lo tanto, como , se tiene .

Extensiones y generalizaciones[editar]

  • Donald J. Newman y Lawrence Shepp mostraron una generalización del problema cuando se necesitan coleccionar copias de cada cupón. Sea la primera vez que se coleccionan copias de cada cupón. Demostraron que la expectativa en este caso satisface:
En este caso, es un valor fijo. Cuando se obtiene la fórmula anterior para el valor esperado.
  • Una generalización común, también demostrada por Erdős y Rényi:
  • En el caso general de una ditribución de probabilidad no uniforme, de acuerdo aPhilippe Flajolet,[1]
Esto es igual a:
donde denota el número de cupones que deben ser coleccionados, y la probabilidad de tener cualquier cupón en el conjunto de cupones.

Véase también[editar]

Notas[editar]

  1. Aquí y a lo largo del artículo, "log" se refiere al logaritmo natural y no logaritmo en ninguna otra base. El uso de se refiere a la Notación O grande usada para describir cotas.
  2. El valor esperado de pruebas para coleccionar todos los 50 cupones es La aproximación para este valor esperado nos da, en este caso .

Referencias[editar]

  1. Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), «Birthday paradox, coupon collectors, caching algorithms and self-organizing search», Discrete Applied Mathematics 39 (3): 207-229, doi:10.1016/0166-218x(92)90177-c  Parámetro desconocido |citeseerx= ignorado (ayuda).

Enlaces externos[editar]