O Brasil é um país muito estranho. Uma das inúmeras bizarrices brasileiras é que temos tabus temporários. Por exemplo, homem se vestir de mulher é tabu (vai acabar com a família, fim dos tempos, etc), mas no carnaval pode! Da mesma maneira, adulto comprando álbum de figurinhas é tabu (precisa crescer, largar os brinquedos, etc.), mas em época de Copa pode!
Sempre que chega época de Copa eu fico espantado com a dedicação que meus amigos tem para completar o álbum com os jogadores. E pensando um pouco no fenômeno, me veio a dúvida: quanto dinheiro você precisa para terminar um álbum desses?
Resolvi fazer um experimento para tentar calcular esse valor. Mas, ao invés de usar o álbum da Copa, escolhi completar o álbum dos Vingadores, já que é um universo que eu tenho mais afinidade. Os valores originais são os seguintes:
Se você for uma pessoa sem imaginação, de cara já tem uma estratégia fácil para completar o álbum: é só pedir tudo pelo correio. Nesse caso, basta comprar o álbum e mais 180 figurinhas em 5 fretes, num total de R$110.90.
Tem como gastar menos que isso? Para descobrir, temos que analisar as figurinhas!
Para descobrir a distribuição das figurinhas, eu comprei ##t=106## pacotinhos (ou seja, ##n=106\times 4=424## figurinhas), e anotei o conteúdo de cada um deles (os dados originais estão no google docs). A primeira coisa que fiz foi traçar o histograma para ver o jeitão dos dados:
Pelo histograma dá para ver que faltam nove figurinhas para completar meu álbum (são os nove buracos no histograma). Por outro lado tem três figurinhas que repetiram 6 vezes, o que indica que possivelmente esse álbum não é honesto, já que algumas figurinhas são mais fáceis que outras.
Ou... talvez não? A intuição humana é notoriamente falha em intuir probabilidades, de repente essa impressão de que algumas figurinhas são mais fáceis é falsa. O jeito correto de decidir isso é fazendo um teste de hipótese. O teste em si é simples, mas eu vou fazer em câmera lenta caso alguém nunca tenha visto.
Para começar, precisamos de uma hipótese nula ##H_0## e um nível de significância ##\alpha##.
Nossa hipótese nula ##H_0## é que as figurinhas tem distribuição uniforme e são independentes. O teste vai nos falar se esse hipótese precisa ser rejeitada. O nível de significância nós podemos escolher, mas escolher o ##\alpha## é uma arte: você precisa levar em conta o número de amostras, e as taxas aceitáveis de falsos positivos e falsos negativos. Usualmente, ##\alpha##=5% funciona bem.
Qual o significado desses parâmetros? Fica simples de entender com um exemplo: suponha que todas as 424 figurinhas que eu comprei vieram repetidas. Em uma distribuição é uniforme, isso não é impossível, mas é extremamente improvável: a chance é de 1 em ##180^{424}\sim 1.7\times 10^{956}##. Esse valor é maior que o número de átomos no universo (muito maior!), então a chance de ter acontecido ao acaso é quase nula.
Se eu tirasse 424 figurinhas repetidas, eu teria bastante convicção de que as figurinhas não são uniformes. Quando fazemos um teste de hipótese, é essa ideia que estamos tentando capturar: os dados que coletamos são tão raros que não poderiam ter acontecido na prática? A chance de terem acontecido ao acaso é menor que ##\alpha##=5%? Se for, então talvez a hipótese ##H_0## seja falsa.
Existem vários testes de hipótese possíveis. Como queremos checar se nossas amostras seguem uma distribuição dada (uniforme), então o teste mais natural a se fazer é o teste do ##\chi^2## (pronuncia-se quiquadrado), que serve justamente para verificar se duas distribuições são iguais.
Você começa o teste do ##\chi^2## separando suas amostras em categorias. No nosso caso, o mais natural seria fazer cada figurinha ser uma categoria, mas isso não vai funcionar. O motivo é que o teste do ##\chi^2##, estritamente falando, só funciona com infinitas amostras. Como é impossível coletar infinitas amostras, nós assumimos que o resultado não muda muito de "infinitas amostras" para "muitas amostras".
Mas quantas amostras são "muitas amostras"? Em geral, a regra usada é que ##np>5##, onde ##n## é o número de amostras e ##p## é a menor probabilidade de uma amostra estar em uma categoria. Vamos fazer as contas: se cada figurinha é uma amostra, e as 180 figurinhas são uniformes, então ##p=1/180##. Como tenho ##n=424## figurinhas, então ##np=424/180\sim 2.35##. Oops, 2.35 é menor que 5, então 180 categorias é muito.
Sempre que chega época de Copa eu fico espantado com a dedicação que meus amigos tem para completar o álbum com os jogadores. E pensando um pouco no fenômeno, me veio a dúvida: quanto dinheiro você precisa para terminar um álbum desses?
Resolvi fazer um experimento para tentar calcular esse valor. Mas, ao invés de usar o álbum da Copa, escolhi completar o álbum dos Vingadores, já que é um universo que eu tenho mais afinidade. Os valores originais são os seguintes:
- O álbum em si custa R$ 6.90, e você precisa de 180 figurinhas para completar.
- Cada pacotinho com 4 figurinhas custa R$ 1.20.
- Existe um kit com 15 pacotinhos que você pode comprar com desconto por R$ 13.90. Mas é difícil de achar: eu só encontrei na loja Geek na av. Paulista.
- Por fim, você sempre pode pedir figurinhas avulsas no site da editora (nesse caso você pode comprar até 40 figurinhas com preço individual de R$ 0.30, mais o frete de R$ 10.00).
Se você for uma pessoa sem imaginação, de cara já tem uma estratégia fácil para completar o álbum: é só pedir tudo pelo correio. Nesse caso, basta comprar o álbum e mais 180 figurinhas em 5 fretes, num total de R$110.90.
Tem como gastar menos que isso? Para descobrir, temos que analisar as figurinhas!
A Distribuição das Figurinhas
Para descobrir a distribuição das figurinhas, eu comprei ##t=106## pacotinhos (ou seja, ##n=106\times 4=424## figurinhas), e anotei o conteúdo de cada um deles (os dados originais estão no google docs). A primeira coisa que fiz foi traçar o histograma para ver o jeitão dos dados:
Ou... talvez não? A intuição humana é notoriamente falha em intuir probabilidades, de repente essa impressão de que algumas figurinhas são mais fáceis é falsa. O jeito correto de decidir isso é fazendo um teste de hipótese. O teste em si é simples, mas eu vou fazer em câmera lenta caso alguém nunca tenha visto.
Para começar, precisamos de uma hipótese nula ##H_0## e um nível de significância ##\alpha##.
Nossa hipótese nula ##H_0## é que as figurinhas tem distribuição uniforme e são independentes. O teste vai nos falar se esse hipótese precisa ser rejeitada. O nível de significância nós podemos escolher, mas escolher o ##\alpha## é uma arte: você precisa levar em conta o número de amostras, e as taxas aceitáveis de falsos positivos e falsos negativos. Usualmente, ##\alpha##=5% funciona bem.
Qual o significado desses parâmetros? Fica simples de entender com um exemplo: suponha que todas as 424 figurinhas que eu comprei vieram repetidas. Em uma distribuição é uniforme, isso não é impossível, mas é extremamente improvável: a chance é de 1 em ##180^{424}\sim 1.7\times 10^{956}##. Esse valor é maior que o número de átomos no universo (muito maior!), então a chance de ter acontecido ao acaso é quase nula.
Se eu tirasse 424 figurinhas repetidas, eu teria bastante convicção de que as figurinhas não são uniformes. Quando fazemos um teste de hipótese, é essa ideia que estamos tentando capturar: os dados que coletamos são tão raros que não poderiam ter acontecido na prática? A chance de terem acontecido ao acaso é menor que ##\alpha##=5%? Se for, então talvez a hipótese ##H_0## seja falsa.
Existem vários testes de hipótese possíveis. Como queremos checar se nossas amostras seguem uma distribuição dada (uniforme), então o teste mais natural a se fazer é o teste do ##\chi^2## (pronuncia-se quiquadrado), que serve justamente para verificar se duas distribuições são iguais.
Você começa o teste do ##\chi^2## separando suas amostras em categorias. No nosso caso, o mais natural seria fazer cada figurinha ser uma categoria, mas isso não vai funcionar. O motivo é que o teste do ##\chi^2##, estritamente falando, só funciona com infinitas amostras. Como é impossível coletar infinitas amostras, nós assumimos que o resultado não muda muito de "infinitas amostras" para "muitas amostras".
Mas quantas amostras são "muitas amostras"? Em geral, a regra usada é que ##np>5##, onde ##n## é o número de amostras e ##p## é a menor probabilidade de uma amostra estar em uma categoria. Vamos fazer as contas: se cada figurinha é uma amostra, e as 180 figurinhas são uniformes, então ##p=1/180##. Como tenho ##n=424## figurinhas, então ##np=424/180\sim 2.35##. Oops, 2.35 é menor que 5, então 180 categorias é muito.
Vamos reduzir então. Eu vou escolher ##c=5## categorias, porque 180 divide certinho por 5. Cada categoria vai ter ##180/5=36## figurinhas, logo ##p=1/36## e ##np=424/36\sim 11.77##, agora sim! O histograma com cinco categorias é assim:
Agora nós vamos tabelar nossas amostras. A linha Observado mostra quantas amostras nós coletamos em cada categoria, a linha Esperado mostra quantas amostras uma distribuição ideal teria (no caso uniforme, todas são iguais a ##n/c=424/5=84.8##):
| Categoria 1 | Categoria 2 | Categoria 3 | Categoria 4 | Categoria 5 | |
|---|---|---|---|---|---|
| Observado | 75 | 90 | 80 | 95 | 84 |
| Esperado | 84.8 | 84.8 | 84.8 | 84.8 | 84.8 |
Podemos calcular o ##\chi^2## agora. A intuição do teste é simples, vamos calcular qual o quadrado da diferença entre o observado e o esperado, e normalizar. Se esse número for muito grande, então tem algo errado. Calculando pela fórmula, temos:
$$\chi^2=\sum\frac{(Y_i-E_i)^2}{E_i}\sim 2.957$$
Esse valor, 2.957 é grande ou é pequeno? Para decidir isso precisamos primeiro calcular quantos graus de liberdade tem esse modelo. O número de graus de liberdade é o número de parâmetros que estamos estimando. Como nossa tabela tem 5 categorias, então o número de graus de liberdade é 4.
Opa! Se são 5 categorias, não tinha que ser 5 graus de liberdade? É verdade que estamos tentando estimar ##Y_1##, ##Y_2##, ##Y_3##, ##Y_4## e ##Y_5##. Mas nós sabemos que a soma de todos eles é ##n##, então se tivermos os quatro primeiros, o quinto é só calcular!
Em tempos idos esse era o momento em que você precisava sacar do bolso uma tabela de ##\chi^2## (como curiosidade, coloquei online a tabela que eu usava na Poli). Mas hoje em dia você pode ir direto no Mathematica para descobrir o valor de ##\chi^2## com ##\alpha##=5% e quatro graus de liberdade:
Como 2.957 é menor que 9.488, então não podemos rejeitar a hipótese de que as figurinhas são uniformes e independentes, e concluímos que sim, as figurinhas provavelmente são honestas.
Alguns de vocês irão chiar, eu sei. "Mas veja, algumas figurinhas saíram repetidas seis vezes, outras não apareceram nenhuma vez! Não tem como isso ser uniforme, claramente tem figurinhas que são mais fáceis!".
Bem, se você ainda estiver na dúvida, você pode comprar mais pacotinhos para deixar o teste mais robusto. Ao invés disso, eu vou usar só as figurinhas que eu tenho para ir direto na raiz da dúvida: afinal de contas, é normal tirar muitas figurinhas repetidas?
A intuição nos diz que, em uma distribuição uniforme, todas as figurinhas tem que aparecer mais ou menos com a mesma frequência. Só que esse é mais um caso onde a intuição é falha! Quem lê o blog há mais tempo deve lembrar de um post sobre o paradoxo do aniversário, que diz exatamente isso: mesmo em distribuições uniformes, a chance de colisões é muito alta.
Podemos usar esse fato para tentar um novo teste de hipótese. Dessa vez, vamos contar quantas repetidas nós temos para cada figurinha, e separá-las por número de repetições. O histograma da quantidade de figurinhas repetidas fica assim:
O histograma foi traçado da quantidade de figurinhas repetidas:
O álbum tem 180 figurinhas, então a soma da segunda linha vale 180. Do total de figurinhas, nove delas não apareceram, três apareceram 6 vezes, e a maioria apareceu entre 1 e 3 vezes.
O formato do histograma parece familiar né? Se nós soubéssemos qual a é a fórmula exata para o número de figurinhas repetidas em uma distribuição uniforme, poderíamos usar o teste do ##\chi^2## para ver se a hipótese ainda se mantém. Só que agora não tem jeito, para descobrir a fórmula precisamos fazer as contas. Pule a caixa azul se você tem medo de combinatória:
Não foi à toa que aquele histograma das figurinhas repetidas parecia familiar, elas seguem uma distribuição de Poisson! Em retrospecto até faz sentido. Se a distribuição das figurinhas é uniforme, então em um longo período de tempo, cada figurinha deve ter uma taxa de aparição constante (igual a ##\lambda=n/m##). Se a taxa é constante ao longo do tempo, então a quantidade de figurinhas em um pequeno intervalo tem que seguir a distribuição de Poisson.
Agora falta pouco para conseguir usar o teste do ##\chi^2## nas repetidas. Precisamos primeiro separar as amostras em categorias. O natural seria usar uma categoria por quantidade de repetidas, mas em teoria, um cara muito azarado poderia ter 424 figurinhas repetidas, e nesse caso o produto ##np## seria muito, muito menor que 5. Vamos então aglutinar todas as categorias de 6 repetidas em diante em um grupo só. A tabela fica assim:
Agora podemos calcular o ##\chi^2## medido e o teórico, lembrando que temos 6 graus de liberdade e ##\alpha## valendo 5%: $$\chi^2=\sum\frac{(Y_i-E_i)^2}{E_i}\sim 11.5275$$
No pŕoximo post, vamos finalmente calcular qual o minimo de dinheiro que você precisa gastar para completar o álbum. Stay tuned!
$$\chi^2=\sum\frac{(Y_i-E_i)^2}{E_i}\sim 2.957$$
Esse valor, 2.957 é grande ou é pequeno? Para decidir isso precisamos primeiro calcular quantos graus de liberdade tem esse modelo. O número de graus de liberdade é o número de parâmetros que estamos estimando. Como nossa tabela tem 5 categorias, então o número de graus de liberdade é 4.
Opa! Se são 5 categorias, não tinha que ser 5 graus de liberdade? É verdade que estamos tentando estimar ##Y_1##, ##Y_2##, ##Y_3##, ##Y_4## e ##Y_5##. Mas nós sabemos que a soma de todos eles é ##n##, então se tivermos os quatro primeiros, o quinto é só calcular!
Em tempos idos esse era o momento em que você precisava sacar do bolso uma tabela de ##\chi^2## (como curiosidade, coloquei online a tabela que eu usava na Poli). Mas hoje em dia você pode ir direto no Mathematica para descobrir o valor de ##\chi^2## com ##\alpha##=5% e quatro graus de liberdade:
InverseCDF[ChiSquareDistribution[4], 1 - 0.05] >> 9.48773
Como 2.957 é menor que 9.488, então não podemos rejeitar a hipótese de que as figurinhas são uniformes e independentes, e concluímos que sim, as figurinhas provavelmente são honestas.
Alguns de vocês irão chiar, eu sei. "Mas veja, algumas figurinhas saíram repetidas seis vezes, outras não apareceram nenhuma vez! Não tem como isso ser uniforme, claramente tem figurinhas que são mais fáceis!".
Bem, se você ainda estiver na dúvida, você pode comprar mais pacotinhos para deixar o teste mais robusto. Ao invés disso, eu vou usar só as figurinhas que eu tenho para ir direto na raiz da dúvida: afinal de contas, é normal tirar muitas figurinhas repetidas?
A Análise das Repetidas
A intuição nos diz que, em uma distribuição uniforme, todas as figurinhas tem que aparecer mais ou menos com a mesma frequência. Só que esse é mais um caso onde a intuição é falha! Quem lê o blog há mais tempo deve lembrar de um post sobre o paradoxo do aniversário, que diz exatamente isso: mesmo em distribuições uniformes, a chance de colisões é muito alta.
Podemos usar esse fato para tentar um novo teste de hipótese. Dessa vez, vamos contar quantas repetidas nós temos para cada figurinha, e separá-las por número de repetições. O histograma da quantidade de figurinhas repetidas fica assim:
O histograma foi traçado da quantidade de figurinhas repetidas:
| Quantidade de repetições | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Figurinhas | 9 | 41 | 50 | 48 | 24 | 5 | 3 |
O formato do histograma parece familiar né? Se nós soubéssemos qual a é a fórmula exata para o número de figurinhas repetidas em uma distribuição uniforme, poderíamos usar o teste do ##\chi^2## para ver se a hipótese ainda se mantém. Só que agora não tem jeito, para descobrir a fórmula precisamos fazer as contas. Pule a caixa azul se você tem medo de combinatória:
O truque para usar combinatória analítica numerada (labelled) é sempre tentar achar um isomorfismo entre o seu problema e uma lista de inteiros. Para o nosso caso, imagine o seguinte experimento: temos ##n## bolinhas numeradas de ##1## a ##n##, e temos também ##m## caixinhas, cada caixa representando uma figurinha. A bolinha representa a ordem em que eu comprei a figurinha. Se eu atirar as bolinhas em caixas aleatórias, tenho um problema isomórfico a comprar figurinhas aleatórias.
Por exemplo: se a bolinha 5 cair na caixa 32, então significa que a quinta figurinha que eu comprei foi a de número 32. Se no fim do experimento a caixa 32 tiver seis bolinhas, então eu tenho a figurinha 32 repetida seis vezes.
No nosso experimento, as caixinhas são diferentes umas das outras, então vamos usar o operador ##\text{SEQ}_m(z)## para modelar as caixinhas. A ordem das bolinhas dentro da caixinha não importa (tanto faz se dissermos que a caixa 32 tem as bolinhas 3, 5, 9, 10 e 15; ou se tiver as bolinhas 9, 5, 3, 15, e 10, é a mesma coisa). Então dentro das caixinhas, usaremos o operador ##\text{SET}(z)##. O experimento completo é ##\text{SEQ}_m(\text{SET}(z))##.
Digamos que estamos interessados em saber quantas caixinhas vão terminar com ##s## bolinhas. Um jeito de medir isso é colocar um marcador nas caixinhas com ##s## elementos. Para isso, nós tiramos as das caixinhas os conjuntos de ##s## elementos, e colocamos eles de volta com o marcador, digamos que o marcador seja ##u##. Então o experimento para medir ##s## repetidas é ##\text{SEQ}_m(\text{SET}(z)-\text{SET}_s(z)+u \text{SET}_s(z))##.
Os experimentos vão mapear para funções geradoras exponenciais de duas variáveis. Das tabelas de combinatória analítica:
$$\begin{align*}
\text{SEQ}_m(z) &= z^m \\
\text{SET}(z) &= e^z \\
\text{SET}_s(z) &= \frac{z^s}{s!}\\
\text{SEQ}_m(\text{SET}(z)-\text{SET}_s(z)+u \text{SET}_s(z)) &=
\left(e^z-\frac{z^s}{s!}+u \frac{z^s}{s!}\right)^m \\
&= \left(e^z+ (u-1) \frac{z^s}{s!}\right)^m
\end{align*}$$
Se abrirmos essa função geradora em série, então o coeficiente do termo ##z^n u^k## indica quantas combinações possíveis de ##n## bolinhas vão ter ##k## caixinhas com ##s## bolinhas repetidas (como a função geradora é exponencial, você precisa multiplicar o coeficiente por ##n!## para ter o valor real). Se chamarmos esse coeficiente de ##R_s(n, k)##, então temos:
$$\sum_{n}\sum_{k}R_s(n,k) z^n u^k = \left(e^z+ (u-1) \frac{z^s}{s!}\right)^m $$
Vamos listar com cuidado o que temos. ##n! R_s(n,k)## é número de combinações possíveis com ##k## caixinhas contendo exatamente ##s## bolinhas. Logo, de todas as combinações possíveis de ##n## bolinhas, existem ##\sum k n! R_s(n,k)## caixinhas com ##s## bolinhas.
Por outro lado, o número total de combinações de ##n## bolinhas em ##m## caixinhas é ##m^n##. Como cada combinação dessas tem ##m## caixinhas, então o número total de caixinhas que podem ser preenchidas em todas as combinações é ##m^{n+1}##.
Juntando as duas contagens, a probabilidade de um caixinha tem ##s## bolinhas em ##n## arremessos é:
$$p_s(n)=\sum_{k>0}\frac{k \;n!}{m^{n+1}}R_s(n, k)$$
Mas olha só! Nós podemos conseguir essa somatória derivando a função geradora em relação a ##u##, e depois setando ##u=1##.
$$\left.\frac{\partial}{\partial u}\sum_{n}\sum_{k}R_s(n,k) z^n u^k \right|_{u=1}=\sum_n \sum_{k}k R_s(n,k) z^n$$
Agora é só fazer as contas:
$$\begin{align*}p_s(n)
&=\sum_k \frac{n!}{m^{n+1}}k R_s(n, k) \\
&=\frac{n!}{m^{n+1}} [z^n] \left.\frac{\partial}{\partial u}\sum_{n}\sum_{k}R_s(n,k) z^n u^k \right|_{u=1}\\
&=\frac{n!}{m^{n+1}} [z^n] \left.\frac{\partial}{\partial u}\left(e^z+ (u-1) \frac{z^s}{s!}\right)^m \right|_{u=1}\\
&=\frac{n!}{m^{n+1}} [z^n] \left. m\left(e^z+ (u-1) \frac{z^s}{s!}\right)^{m-1} \frac{z^s}{s!} \right|_{u=1}\\
&=\frac{n!}{m^{n+1}} [z^n] m\left(e^z\right)^{m-1} \frac{z^s}{s!} \\
&=\frac{n!}{s!\;m^n} [z^n]z^s e^{z(m-1)}\\
\end{align*}$$
&=\frac{n!}{s!\;m^{n}} [z^n]z^s\sum_{k\ge 0}\frac{(z(m-1))^k}{k!} \\ &=\frac{n!}{s!\;m^{n}} [z^n]\sum_{k\ge 0}\frac{z^{k+s}(m-1)^k}{k!} \\ &=\frac{n!}{s!\;m^{n}} [z^n]\sum_{p\ge s}\frac{z^p(m-1)^{p-s}}{(p-s)!} \\ &=\frac{n!}{s!\;m^{n}}\; \frac{(m-1)^{n-s}}{(n-s)!} \\ &=\frac{n!}{s!(n-s)!}\; \frac{(m-1)^{n-s}}{m^{n}} \\ &={{n}\choose{s}}\frac{(m-1)^{n-s}}{m^{n}} \\ \end{align*}$$
Essa é a solução exata, em forma fechada, que queríamos! Mas tem uma massagem que podemos fazer que vai ajudar a entender por que essa fórmula é assim. Em geral ##n## é bem maior que ##m##, então vamos reescrever ##m## de modo que ##n=\lambda m##, e calcular o limite quando ##n## é muito grande: $$\begin{align*}\lim_{n\to\infty}p_s(n) &=\lim_{n\to\infty}\frac{n!}{s!(n-s)!}\; \frac{(n/\lambda-1)^{n-s}}{(n/\lambda)^{n}} \\ &=\lim_{n\to\infty}\frac{n!}{s!(n-s)!}\; \left(\frac{n-\lambda}{\lambda}\right)^{n-s} \left(\frac{\lambda}{n}\right)^{n}\\ &=\lim_{n\to\infty}\frac{n!}{s!(n-s)!}\; \lambda^{s} \left(\frac{n-\lambda}{n}\right)^{n-s}\left(\frac{1}{n}\right)^{s} \\ &=\lim_{n\to\infty}\frac{n!\;\lambda^{s}}{s!(n-s)!\;n^{s}}\; \left(1-\frac{\lambda}{n}\right)^{n-s}\\ &=\lim_{n\to\infty}\left(\frac{\lambda^{s}}{s!}\right) \left(\frac{n!}{(n-s)!\;n^s}\right) \left(1-\frac{\lambda}{n}\right)^{n} \left(1-\frac{\lambda}{n}\right)^{-s} \\ \end{align*}$$ O limite do produto é o produto dos limites, desde que todos existam e sejam finitos, então vamos conferir um por um. O primeiro termo é constante, easy. No segundo, o numerador é um polinômio de grau ##n##, o denominador é um polinômio de grau ##n##, então a fração é constante e vale 1, já que os coeficientes iniciais ambos valem 1. O terceiro é a definição de ##e^{-\lambda}##. No quarto a segunda fração vai para zero, então o total tende a 1. Combinando tudo: $$\lim_{n\to\infty}p_s(n)= e^{-\lambda}\frac{\lambda^s}{s!}$$ Ahá, é uma distribuição de Poisson!
Por exemplo: se a bolinha 5 cair na caixa 32, então significa que a quinta figurinha que eu comprei foi a de número 32. Se no fim do experimento a caixa 32 tiver seis bolinhas, então eu tenho a figurinha 32 repetida seis vezes.
No nosso experimento, as caixinhas são diferentes umas das outras, então vamos usar o operador ##\text{SEQ}_m(z)## para modelar as caixinhas. A ordem das bolinhas dentro da caixinha não importa (tanto faz se dissermos que a caixa 32 tem as bolinhas 3, 5, 9, 10 e 15; ou se tiver as bolinhas 9, 5, 3, 15, e 10, é a mesma coisa). Então dentro das caixinhas, usaremos o operador ##\text{SET}(z)##. O experimento completo é ##\text{SEQ}_m(\text{SET}(z))##.
Digamos que estamos interessados em saber quantas caixinhas vão terminar com ##s## bolinhas. Um jeito de medir isso é colocar um marcador nas caixinhas com ##s## elementos. Para isso, nós tiramos as das caixinhas os conjuntos de ##s## elementos, e colocamos eles de volta com o marcador, digamos que o marcador seja ##u##. Então o experimento para medir ##s## repetidas é ##\text{SEQ}_m(\text{SET}(z)-\text{SET}_s(z)+u \text{SET}_s(z))##.
Os experimentos vão mapear para funções geradoras exponenciais de duas variáveis. Das tabelas de combinatória analítica:
$$\begin{align*}
\text{SEQ}_m(z) &= z^m \\
\text{SET}(z) &= e^z \\
\text{SET}_s(z) &= \frac{z^s}{s!}\\
\text{SEQ}_m(\text{SET}(z)-\text{SET}_s(z)+u \text{SET}_s(z)) &=
\left(e^z-\frac{z^s}{s!}+u \frac{z^s}{s!}\right)^m \\
&= \left(e^z+ (u-1) \frac{z^s}{s!}\right)^m
\end{align*}$$
Se abrirmos essa função geradora em série, então o coeficiente do termo ##z^n u^k## indica quantas combinações possíveis de ##n## bolinhas vão ter ##k## caixinhas com ##s## bolinhas repetidas (como a função geradora é exponencial, você precisa multiplicar o coeficiente por ##n!## para ter o valor real). Se chamarmos esse coeficiente de ##R_s(n, k)##, então temos:
$$\sum_{n}\sum_{k}R_s(n,k) z^n u^k = \left(e^z+ (u-1) \frac{z^s}{s!}\right)^m $$
Vamos listar com cuidado o que temos. ##n! R_s(n,k)## é número de combinações possíveis com ##k## caixinhas contendo exatamente ##s## bolinhas. Logo, de todas as combinações possíveis de ##n## bolinhas, existem ##\sum k n! R_s(n,k)## caixinhas com ##s## bolinhas.
Por outro lado, o número total de combinações de ##n## bolinhas em ##m## caixinhas é ##m^n##. Como cada combinação dessas tem ##m## caixinhas, então o número total de caixinhas que podem ser preenchidas em todas as combinações é ##m^{n+1}##.
Juntando as duas contagens, a probabilidade de um caixinha tem ##s## bolinhas em ##n## arremessos é:
$$p_s(n)=\sum_{k>0}\frac{k \;n!}{m^{n+1}}R_s(n, k)$$
Mas olha só! Nós podemos conseguir essa somatória derivando a função geradora em relação a ##u##, e depois setando ##u=1##.
$$\left.\frac{\partial}{\partial u}\sum_{n}\sum_{k}R_s(n,k) z^n u^k \right|_{u=1}=\sum_n \sum_{k}k R_s(n,k) z^n$$
Agora é só fazer as contas:
$$\begin{align*}p_s(n)
&=\sum_k \frac{n!}{m^{n+1}}k R_s(n, k) \\
&=\frac{n!}{m^{n+1}} [z^n] \left.\frac{\partial}{\partial u}\sum_{n}\sum_{k}R_s(n,k) z^n u^k \right|_{u=1}\\
&=\frac{n!}{m^{n+1}} [z^n] \left.\frac{\partial}{\partial u}\left(e^z+ (u-1) \frac{z^s}{s!}\right)^m \right|_{u=1}\\
&=\frac{n!}{m^{n+1}} [z^n] \left. m\left(e^z+ (u-1) \frac{z^s}{s!}\right)^{m-1} \frac{z^s}{s!} \right|_{u=1}\\
&=\frac{n!}{m^{n+1}} [z^n] m\left(e^z\right)^{m-1} \frac{z^s}{s!} \\
&=\frac{n!}{s!\;m^n} [z^n]z^s e^{z(m-1)}\\
\end{align*}$$
Abrindo a exponencial em série:
$$\begin{align*}p_s(n)&=\frac{n!}{s!\;m^{n}} [z^n]z^s\sum_{k\ge 0}\frac{(z(m-1))^k}{k!} \\ &=\frac{n!}{s!\;m^{n}} [z^n]\sum_{k\ge 0}\frac{z^{k+s}(m-1)^k}{k!} \\ &=\frac{n!}{s!\;m^{n}} [z^n]\sum_{p\ge s}\frac{z^p(m-1)^{p-s}}{(p-s)!} \\ &=\frac{n!}{s!\;m^{n}}\; \frac{(m-1)^{n-s}}{(n-s)!} \\ &=\frac{n!}{s!(n-s)!}\; \frac{(m-1)^{n-s}}{m^{n}} \\ &={{n}\choose{s}}\frac{(m-1)^{n-s}}{m^{n}} \\ \end{align*}$$
Essa é a solução exata, em forma fechada, que queríamos! Mas tem uma massagem que podemos fazer que vai ajudar a entender por que essa fórmula é assim. Em geral ##n## é bem maior que ##m##, então vamos reescrever ##m## de modo que ##n=\lambda m##, e calcular o limite quando ##n## é muito grande: $$\begin{align*}\lim_{n\to\infty}p_s(n) &=\lim_{n\to\infty}\frac{n!}{s!(n-s)!}\; \frac{(n/\lambda-1)^{n-s}}{(n/\lambda)^{n}} \\ &=\lim_{n\to\infty}\frac{n!}{s!(n-s)!}\; \left(\frac{n-\lambda}{\lambda}\right)^{n-s} \left(\frac{\lambda}{n}\right)^{n}\\ &=\lim_{n\to\infty}\frac{n!}{s!(n-s)!}\; \lambda^{s} \left(\frac{n-\lambda}{n}\right)^{n-s}\left(\frac{1}{n}\right)^{s} \\ &=\lim_{n\to\infty}\frac{n!\;\lambda^{s}}{s!(n-s)!\;n^{s}}\; \left(1-\frac{\lambda}{n}\right)^{n-s}\\ &=\lim_{n\to\infty}\left(\frac{\lambda^{s}}{s!}\right) \left(\frac{n!}{(n-s)!\;n^s}\right) \left(1-\frac{\lambda}{n}\right)^{n} \left(1-\frac{\lambda}{n}\right)^{-s} \\ \end{align*}$$ O limite do produto é o produto dos limites, desde que todos existam e sejam finitos, então vamos conferir um por um. O primeiro termo é constante, easy. No segundo, o numerador é um polinômio de grau ##n##, o denominador é um polinômio de grau ##n##, então a fração é constante e vale 1, já que os coeficientes iniciais ambos valem 1. O terceiro é a definição de ##e^{-\lambda}##. No quarto a segunda fração vai para zero, então o total tende a 1. Combinando tudo: $$\lim_{n\to\infty}p_s(n)= e^{-\lambda}\frac{\lambda^s}{s!}$$ Ahá, é uma distribuição de Poisson!
Não foi à toa que aquele histograma das figurinhas repetidas parecia familiar, elas seguem uma distribuição de Poisson! Em retrospecto até faz sentido. Se a distribuição das figurinhas é uniforme, então em um longo período de tempo, cada figurinha deve ter uma taxa de aparição constante (igual a ##\lambda=n/m##). Se a taxa é constante ao longo do tempo, então a quantidade de figurinhas em um pequeno intervalo tem que seguir a distribuição de Poisson.
Agora falta pouco para conseguir usar o teste do ##\chi^2## nas repetidas. Precisamos primeiro separar as amostras em categorias. O natural seria usar uma categoria por quantidade de repetidas, mas em teoria, um cara muito azarado poderia ter 424 figurinhas repetidas, e nesse caso o produto ##np## seria muito, muito menor que 5. Vamos então aglutinar todas as categorias de 6 repetidas em diante em um grupo só. A tabela fica assim:
| Quantidade de repetições | 0 | 1 | 2 | 3 | 4 | 5 | 6 ou mais |
|---|---|---|---|---|---|---|---|
| Figurinhas, medido | 9 | 41 | 50 | 48 | 24 | 5 | 3 |
| Figurinhas, teórico | 17.1 | 40.2 | 47.4 | 37.2 | 21.9 | 10.3 | 5.9 |
Agora podemos calcular o ##\chi^2## medido e o teórico, lembrando que temos 6 graus de liberdade e ##\alpha## valendo 5%: $$\chi^2=\sum\frac{(Y_i-E_i)^2}{E_i}\sim 11.5275$$
InverseCDF[ChiSquareDistribution[6], 1 - 0.05] >> 12.59Conclusão: como 11.53 é menor que 12.59, então novamente não podemos rejeitar a hipótese de que as figurinhas são uniformes e independentes, e concluímos que sim, as figurinhas provavelmente são honestas. É verdade que tem muitas repetidas, mas o número de repetidas está dentro do esperado.
Quanto gastar para completar?
No pŕoximo post, vamos finalmente calcular qual o minimo de dinheiro que você precisa gastar para completar o álbum. Stay tuned!
