Problema del coleccionista de pegatinas

El recolector de miniaturas del problema o el recolector de cupones ( coupon collector en inglés) es un fenómeno estudiado en teoría de probabilidades y combinatoria . Un coleccionista busca tener todas las pegatinas de una serie pero en el momento de la compra se desconoce el número de la pegatina (como los juguetes en los paquetes de cereales por ejemplo): se trata por tanto de un dibujo con descuento . La pregunta es: ¿cuánto tienes que comprar para obtener la colección completa? El estudio de este problema y sus generalizaciones encuentra aplicaciones en particular en la ingeniería de telecomunicaciones .

En promedio, se necesitan alrededor de $n ln ( n )$ compras para una colección de $n$ miniaturas.

El problema del coleccionista de viñetas ya fue mencionado en 1812 por Pierre-Simon de Laplace en Teoría analítica de probabilidades , página 195, donde da, antes de Erdös y Rényi, la convergencia hacia la ley de Gumbel . También es mencionado por George Pólya , pero es notablemente mencionado por William Feller .

Definición formal y notaciones

Consideramos la variable aleatoria $T n$ que representa el número de miniaturas compradas antes de obtener las $n$ miniaturas de la colección. Podemos considerar que $T n$ es un tiempo : en cada paso de tiempo se compra una nueva miniatura. Sea $t i$ el tiempo adicional para obtener la i -ésima miniatura nueva, sabiendo que tenemos i -1. Así que tenemos . ${\ Displaystyle T_ {n} = \ sum _ {i = 1} ^ {n} t_ {i}}$

Cálculos de la expectativa y varianza del tiempo para finalizar la colección

Cuando tenemos i -1 miniaturas, la probabilidad de encontrar una nueva es $n - yo +1 / no$ . Por tanto, la variable $t i$ sigue una ley geométrica del parámetro $n - yo +1 / no$ . De ahí la esperanza:

{\ Displaystyle \ mathbb {E} (t_ {i}) = {\ frac {n} {n- (i-1)}}}

Esperanza

Por linealidad de expectativa:

{\ Displaystyle {\ begin {alineado} \ mathbb {E} (T_ {n}) & = \ mathbb {E} (t_ {1}) + \ mathbb {E} (t_ {2}) + \ cdots + \ mathbb {E} (t_ {n}) \\ & = {\ frac {n} {n}} + {\ frac {n} {n-1}} + \ cdots + {\ frac {n} {1} } \\ & = n \ cdot \ left ({\ frac {1} {1}} + {\ frac {1} {2}} + \ cdots + {\ frac {1} {n}} \ right) \ \ & = \, n \ cdot H_ {n}. \ end {alineado}}}

donde H n es el n- ésimo número armónico . Usando la expansión asintótica de H n , obtenemos:

{\ Displaystyle \ mathbb {E} (T_ {n}) = n \ cdot H_ {n} = n \ ln (n) + \ gamma n + {\ frac {1} {2}} + o (1), \ \ {\ text {para}} \ n \ a \ infty,}

donde es la constante de Euler-Mascheroni . ${\ Displaystyle \ gamma \ approx 0.5772156649}$

Diferencia

Utilizando la independencia de las variables $t i$ , obtenemos:

{\ Displaystyle {\ begin {alineado} \ operatorname {Var} (T_ {n}) & = \ operatorname {Var} (t_ {1}) + \ operatorname {Var} (t_ {2}) + \ cdots + \ nombre de operador {Var} (t_ {n}) \\ & \ leq {\ frac {n ^ {2}} {n ^ {2}}} + {\ frac {n ^ {2}} {(n-1) ^ {2}}} + \ cdots + {\ frac {n ^ {2}} {1 ^ {2}}} \\ & \ leq n ^ {2} \ cdot \ left ({\ frac {1} { 1 ^ {2}}} + {\ frac {1} {2 ^ {2}}} + \ cdots \ right) = {\ frac {\ pi ^ {2}} {6}} n ^ {2} < 2n ^ {2}, \ end {alineado}}}

donde la última igualdad proviene del cálculo de un valor de la función de Riemann zeta .

Estimaciones más precisas de la desviación.

Calculando la varianza podemos obtener la siguiente desigualdad usando la desigualdad de Bienaymé-Chebyshev :

{\ Displaystyle \ forall \ varepsilon> 0, \ mathbb {P} \ left (| T_ {n} -nH_ {n} | \ geq \ varepsilon \, n \ right) \ leq {\ frac {2} {\ varepsilon ^ {2}}}.}

También podemos mostrar el siguiente umbral, usando la desigualdad booleana ( límite de unión ):

{\ Displaystyle \ forall \ varepsilon> 0, \ \ lim _ {n \ rightarrow \ infty} \ mathbb {P} (T_ {n}> n \ ln (n) + \ varepsilon n) = 1-e ^ {- e ^ {- \ varepsilon}}.}

La primera demostración conocida, a través del análisis de series generadoras, es la de Pierre-Simon de Laplace , página 195 de su tratado sobre probabilidades, edición de 1812. También citamos a menudo un artículo de Erdös y Rényi de 1960, donde los autores parecen para descubrir ocasionalmente la ley de Gumbel , que reaparece en su trabajo el mismo año, en el famoso teorema de la doble exponencial que especifica el umbral de conectividad de los gráficos aleatorios.

Generalizaciones

Hay varias formas de generalizar el problema.

El coleccionista tiene un hermano pequeño al que le da pegatinas duplicadas.
El coleccionista compra bolsillos de k etiquetas diferentes. Los coeficientes binomiales se muestran en las fórmulas.

Aplicaciones

La mayoría de las aplicaciones del problema del colector de pegatinas son sistemas en los que hay una serie de elementos para visitar y la política elegida es dibujar elementos al azar hasta que los haya visto todos (al menos con una buena probabilidad). A continuación se ofrecen algunos ejemplos.

Ciertos métodos para identificar las limitaciones interesantes en la optimización , consisten en realizar un cierto número de pruebas y en suponer que después de este examen hemos encontrado todas las limitaciones interesantes. El número de pruebas necesarias se determina a partir de los cálculos anteriores.

Algunos algoritmos de optimización necesitan un punto de partida, y este punto de partida influye en el resultado obtenido, por ejemplo en la búsqueda de un mínimo local . Al usar varios puntos de partida extraídos al azar, aumentamos la probabilidad de éxito al obtener nuevos mínimos locales, pero podemos obtener los mismos dos veces. Podemos trazar un paralelo con el colector de pegatinas para estimar el número de arranques necesarios.

Esta técnica también se usa para detectar fallas.

En el campo de la difusión de rumores en un gráfico, un modelo clásico es aquel en el que el rumor está presente en un nodo al inicio y en cada paso de tiempo cada nodo informado transmite la información a uno de sus vecinos aleatorios. El problema del coleccionista surge naturalmente en este contexto.

Notas y referencias

George Pólya: Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung, ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik, Band 10, Heft 1, 1930, S. 96–97
El trabajo de Feller donde se trata del problema es ( Feller 1991 ), y la observación la hacen por ejemplo ( Foata, Han y Lass 2001 ).
Ver Motwani y Raghavan 1995 .
Ver sobre este tema el artículo ( Foata, Han y Lass 2001 )
Consulte el artículo gratuito en línea ( Sardy y Velenik 2010 ), sobre Images des maths
Algunos ejemplos en esta sección provienen de ( Boneh y Hofri 1997 ).
( Boneh 1983 )

Bibliografía

Popularización y aspectos generales

Pierre-Simon de Laplace , Teoría analítica de probabilidades, 1812 sobre Gallica .
Sylvain Sardy e Yvan Velenik , " Pequeña colección de información útil para el coleccionista compulsivo ", Images des maths ,11 de agosto de 2010( leer en línea )

(en) Arnon Boneh y Micha Hofri , “ El problema del colector de cupones revisado: una revisión de problemas de ingeniería y métodos computacionales ” , Modelos estocásticos , Taylor y Francis , vol. 13, n o 1,1997, p. 39-66 ( DOI 10.1080 / 15326349708807412 , leer en línea )

(en) William Feller , Introducción a la teoría de la probabilidad y sus aplicaciones , vol. 2, Nueva York / Chichester / Brisbane, etc., Wiley ,1 st 01 1991, 2 nd ed. , 669 p. ( ISBN 0-471-25709-5 y 978-0471257097 ) , pág. 262-263.

(en) Rajeev Motwani y Prabhakar Raghavan , algoritmos aleatorios , Cambridge; Nueva York, Cambridge University Press ( repr. 1997, 2000) ( 1 st ed. 1995), 476 p. ( ISBN 9780521474658 ) , cap. 3.6 (“El problema del coleccionista de cupones”) , pág. 57-63

Artículos y libros de investigación

(en) Arnon Boneh , "Preduce - Un algoritmo probabilístico que identifica la redundancia mediante un generador de puntos factibles aleatorios (RFPG)" , en Redundancy in Mathematical Programming , Springer,1983, p. 108-134

(es) Aimo Torn y Antanas Zilinskas , Optimización global , Springer-Verlag ,1989

Dominique Foata , Guo-Niu Han y Bodo Lass , “ Números hiperarmónicos y los hermanos del coleccionista de viñetas ”, Seminario Lotharingien sobre Combinatoria , vol. 47,2001( leer en línea )

Ver también

Fuente de traducción

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Problema del coleccionista de cupones " ( consulte la lista de autores ) .