No problema clássico do colecionador de cupons , é sabido que o tempo necessário para concluir um conjunto de cupons escolhidos aleatoriamente satisfaz , e .
Esse limite superior é melhor que o dado pela desigualdade de Chebyshev, que seria aproximadamente .
Minha pergunta é: existe um limite inferior melhor que Chebyshev correspondente para ? (por exemplo, algo como )?
Respostas:
Estou fornecendo isso como uma segunda resposta, pois a análise é completamente elementar e fornece exatamente o resultado desejado.
Proposição Parac>0 e n≥1 ,
A ideia por trás da prova é simples:
Prova
Para qualquer e qualquer , temos que s > 0 P ( T < t ) = P ( e - s T > e - s t ) ≤ e s t E e - s Tt s>0
Como e são independentes, podemos escrever t i E de e - s T = n Π i = 1 E de e - s t iT=∑iTi Ti
Agora, como é geométrico, digamos com probabilidade de sucesso , um cálculo simples mostra p i E e - s T i = p iTi pi
O para o nosso problema é , , , etc. Portanto, p 1 = 1 p 2 = 1 - 1 / n p 3 = 1 - 2 / n n ∏ i = 1 E e - s T i = n ∏ i = 1 i / npi p1=1 p2=1−1/n p3=1−2/n
Vamos escolher e por algum . Então e , produzindo t = n log n - c n c > 0 e s t = n e - c e s = o e 1 / n ≥ 1 + 1 / n n Π i = 1 i / ns=1/n t=nlogn−cn c>0
Juntando isso, obtemos que
como desejado.
fonte
Embora o @cardinal já tenha dado uma resposta que fornece exatamente o limite que eu estava procurando, encontrei um argumento semelhante ao estilo Chernoff que pode fornecer um limite mais forte:
Proposição : (isso é mais forte para )
Prova :
Como na resposta do @ cardinal, podemos usar o fato de que é uma soma de variáveis aleatórias geométricas independentes com probabilidades de sucesso . Daqui resulta que e .T TEu pEu= 1 - i / n E[ TEu] = 1 / pEu E[ T] = ∑ni = 1E[ TEu] = n ∑ni = 11Eu≥ n logn
Defina agora novas variáveis e . Podemos então escreverSEu: = TEu- E[ TEu] S: = ∑EuSEu
Calculando as médias, temos
Portanto, como , podemos escrever∑Eup- 2Eu= n2∑n - 1i = 11Eu2≤ n2π2/ 6
Minimizando , finalmente obtemoss > 0
fonte
Nota importante : Decidi remover a prova que dei originalmente nesta resposta. Foi mais longo, mais computacional, usou martelos maiores e provou um resultado mais fraco em comparação com a outra prova que eu dei. Ao redor, uma abordagem inferior (na minha opinião). Se você estiver realmente interessado, suponho que você possa ver as edições.
Os resultados assintóticos que citei originalmente e que ainda são encontrados abaixo nesta resposta mostram que, como , podemos fazer um pouco melhor do que o limite provado na outra resposta, que vale para todos os .n → ∞ n
Os seguintes resultados assintóticos são válidos
e
A constante e os limites são tomados como . Observe que, embora estejam separados em dois resultados, eles são praticamente o mesmo resultado, pois não é obrigado a ser não-negativo nos dois casos. n → ∞ cc∈R n→∞ c
Veja, por exemplo, Motwani e Raghavan, Randomized Algorithms , pp. 60--63 para uma prova.
Além disso : David gentilmente fornece uma prova de seu limite superior declarado nos comentários a esta resposta.
fonte
Benjamin Doerr fornece (no capítulo "Analisando heurísticas de pesquisa randomizada: ferramentas da teoria das probabilidades" no livro "Teoria das heurísticas de pesquisa randomizada", consulte o link para um PDF on-line) uma prova bastante simples de
Proposição Seja o tempo de parada do processo de coleta de cupons. Então .T Pr[T≤(1−ϵ)(n−1)lnn]≤e−nϵ
Isso parece dar os assintóticos desejados (da segunda resposta do @ cardeal), mas com a vantagem de ser verdadeiro para todos os e .n ϵ
Aqui está um esboço de prova.
Esboço de prova: Seja o evento em que o ésimo cupom é coletado nos primeiros sorteios. Assim, . O fato principal é que os estão correlacionados negativamente, para qualquer , . Intuitivamente, isso é bastante claro, pois saber que o ésimo cupom nos primeiros draws tornaria menos provável que o -ésimo cupom também fosse sorteado nos primeiros draws. i t Pr [Xi i t Pr[Xi=1]=(1−1/n)t Xi I⊆[n] Pr[∀i∈I,Xi=1]≤∏i∈IPr[Xi=1] i t j t
Pode-se provar a afirmação, mas ampliando o conjunto em 1 a cada etapa. Em seguida, ele reduz a mostrar que , para . Equivalentemente, calculando a média, reduz-se a mostrar que . Doerr apenas fornece um argumento intuitivo para isso. Uma avenida para uma prova é a seguinte. Pode-se observar que, condicionado ao cupom que vem depois de todos os cupons em , que a probabilidade de sacar um novo cupom de depois de sacar até agora é agora , em vez do anteriorI Pr[∀i∈I,Xi=1|Xj=1]≤Pr[∀i∈I,Xi=1] j∉I j I I k | I | - kPr[∀i∈I,Xi=1|Xj=0]≥Pr[∀i∈I,Xi=1] j I I k | I| -k|I|−kn−1 jeu|I|−kn . Assim, decompondo o tempo para coletar todos os cupons como uma soma de variáveis aleatórias geométricas, podemos ver que o condicionamento no código vindo depois que aumenta as probabilidades de sucesso e, portanto, fazer o condicionamento apenas aumenta a probabilidade de coletar os cupons mais cedo ( por dominância estocástica: cada variável aleatória geométrica é aumentada, em termos de dominância estocástica, pelo condicionamento, e essa dominância pode ser aplicada à soma).j I
Dada essa correlação negativa, segue-se que , que fornece a limite desejado com . t = ( 1 - ϵ ) ( n - 1 ) ln nPr[T≤(1−ϵ)(n−1)lnn]≤(1−(1−1/n)t)n t=(1−ϵ)(n−1)lnn
fonte