Problema de colecionador de adesivos

O coletor de miniaturas do problema ou o coletor de cupons ( coletor de cupons em inglês) é um fenômeno estudado em teoria da probabilidade e combinatória . Um colecionador procura ter todos os adesivos de uma série, mas na hora da compra o número do adesivo é desconhecido (como os brinquedos em pacotes de cereais por exemplo): é, portanto, um desenho com desconto . A questão é: quanto você precisa comprar para ter a coleção completa? O estudo deste problema e suas generalizações encontram aplicações em particular na engenharia de telecomunicações .

Em média, são necessárias cerca de $n ln ( n )$ compras para uma coleção de $n$ miniaturas.

O problema do colecionador de vinhetas já foi mencionado em 1812 por Pierre-Simon de Laplace em Teoria analítica das probabilidades , página 195, onde ele dá, antes de Erdös e Rényi, a convergência para a lei de Gumbel . Ele também é mencionado por George Pólya , mas é notavelmente mencionado por William Feller .

Definição formal e notações

Consideramos a variável aleatória $T n$ que representa o número de miniaturas adquiridas antes de obter as $n$ miniaturas da coleção. Podemos considerar que $T n$ é um tempo : a cada passo de tempo, uma nova miniatura é comprada. Seja $t i$ o tempo adicional para obter a i -ésima nova miniatura, sabendo que temos i -1. Então nós temos . ${\ displaystyle T_ {n} = \ sum _ {i = 1} ^ {n} t_ {i}}$

Cálculos da expectativa e variação do tempo para finalizar a coleta

Quando temos i -1 miniaturas, a probabilidade de encontrar uma nova é $n - i +1 / não$ . A variável $t i,$ portanto, segue uma lei geométrica de parâmetro $n - i +1 / não$ . Daí a esperança:

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

Ter esperança

Por linearidade de expectativa:

{\ displaystyle {\ begin {alinhados} \ 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 {alinhado}}}

onde H n é o n- ésimo número harmônico . Usando a expansão assintótica de H n , obtemos:

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

onde está a constante de Euler-Mascheroni . ${\ displaystyle \ gamma \ approx 0,5772156649}$

Variância

Usando a independência das variáveis $t i$ , obtemos:

{\ displaystyle {\ begin {alinhado} \ operatorname {Var} (T_ {n}) & = \ operatorname {Var} (t_ {1}) + \ operatorname {Var} (t_ {2}) + \ cdots + \ operatorname {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 {alinhado}}}

onde a última igualdade vem do cálculo de um valor da função zeta de Riemann .

Estimativas mais precisas do desvio

Ao calcular a variância, podemos obter a seguinte desigualdade usando a desigualdade de Bienaymé-Chebyshev :

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

Também podemos mostrar o seguinte limite, usando a desigualdade booleana ( limite de união ):

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

A primeira demonstração conhecida, por meio da análise de séries geradoras, é a de Pierre-Simon de Laplace , página 195 de seu tratado sobre probabilidades, edição de 1812. Também citamos com frequência um artigo de Erdös e Rényi de 1960, onde os autores parecem para descobrir ocasionalmente a lei de Gumbel , que reaparece em seu trabalho no mesmo ano, no famoso teorema exponencial duplo que especifica o limite de conectividade de grafos aleatórios.

Generalizações

Existem várias maneiras de generalizar o problema.

O colecionador tem um irmão mais novo a quem dá adesivos duplicados.
O colecionador compra bolsos com k adesivos diferentes. Os coeficientes binomiais são então mostrados nas fórmulas.

Formulários

A maioria das aplicações do problema do coletor de adesivos são sistemas onde há uma série de itens a serem visitados e a política escolhida é desenhar itens aleatoriamente até que você os tenha visto todos (pelo menos com uma boa probabilidade). Alguns exemplos são fornecidos a seguir.

Certos métodos para identificar as restrições interessantes na otimização , consistem em realizar um certo número de testes e supor que após esse exame encontramos todas as restrições interessantes. O número de testes necessários é determinado a partir dos cálculos acima.

Alguns algoritmos de otimização precisam de um ponto de partida, e esse ponto de partida influencia o resultado obtido, por exemplo, na busca por um mínimo local . Usando vários pontos de partida sorteados aleatoriamente, aumentamos a probabilidade de sucesso procurando por novos mínimos locais, mas podemos obter o mesmo duas vezes. Podemos traçar um paralelo com o coletor de adesivos para estimar o número de partidas necessárias.

Essa técnica também é usada para detectar falhas.

No campo da propagação do rumor em gráfico, um modelo clássico é aquele em que o rumor está presente em um nodo no início e a cada passo de tempo cada nodo informado transmite a informação para um de seus vizinhos aleatórios. O problema do colecionador surge naturalmente neste contexto.

Notas e referências

George Pólya: Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung, ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik, Band 10, Heft 1, 1930, S. 96–97
O trabalho de Feller onde se trata do problema é ( Feller 1991 ), e a observação é feita, por exemplo, por ( Foata, Han e Lass 2001 ).
Ver Motwani e Raghavan 1995 .
Veja sobre este assunto o artigo ( Foata, Han e Lass 2001 )
Veja o artigo online gratuito ( Sardy e Velenik 2010 ), em Images des maths
Alguns exemplos nesta seção vêm de ( Boneh e Hofri 1997 ).
( Boneh 1983 )

Bibliografia

Popularização e aspectos gerais

Pierre-Simon de Laplace , teoria analítica das probabilidades, 1812 em Gallica .
Sylvain Sardy e Yvan Velenik , " Pequena coleção de informações úteis para colecionador compulsivo ", Images des maths ,11 de agosto de 2010( leia online )

(pt) Arnon Boneh e Micha Hofri , “ O problema do coletor de cupons revisitado - uma pesquisa de problemas de engenharia e métodos computacionais ” , Stochastic Models , Taylor e Francis , vol. 13, n o 1,1997, p. 39-66 ( DOI 10.1080 / 15326349708807412 , leia online )

(pt) William Feller , Uma Introdução à Teoria da Probabilidade e suas Aplicações , vol. 2, New York / Chichester / Brisbane etc., Wiley ,1 ° de janeiro de 1991, 2 nd ed. , 669 p. ( ISBN 0-471-25709-5 e 978-0471257097 ) , p. 262-263.

(pt) Rajeev Motwani e Prabhakar Raghavan , Randomized Algorithms , Cambridge; Nova York, Cambridge University Press ( repr. 1997, 2000) ( 1 st ed. 1995), 476 p. ( ISBN 9780521474658 ) , cap. 3.6 (“O problema do coletor de cupons”) , p. 57-63

Artigos e livros de pesquisa

(pt) Arnon Boneh , "Preduce - Um algoritmo probabilístico que identifica redundância por um gerador de ponto viável aleatório (RFPG)" , em Redundancy in Mathematical Programming , Springer,1983, p. 108-134

(pt) Aimo Torn e Antanas Zilinskas , otimização global , Springer-Verlag ,1989

Dominique Foata , Guo-Niu Han e Bodo Lass , “ Números hiper-harmônicos e os irmãos do colecionador de vinhetas ”, Lotharingien Seminar on Combinatorics , vol. 47,2001( leia online )

Veja também

Fonte de tradução

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Problema do colecionador de cupons " ( veja a lista de autores ) .