Você já capturou todos os pokémons do Pokémon GO? Eu ainda não consegui, e também não conheço ninguém que tenha conseguido. O motivo é simples: para cada Pikachu que você encontrar, vai passar por um centena de Zubats antes! Fica difícil pegar todos quando alguns são tão raros!
A pergunta natural agora é: se eu quiser insistir e continuar jogando até pegar todos, quanto tempo vai levar? Ou, de outro modo, qual é o
número esperado de capturas até completar a coleção? Esse problema é difícil de resolver no caso geral, mas fica mais simples usando
Combinatória Analítica!
Combinatória Analítica Numerada
No
último post do blog eu mostrei como funciona a Combinatória Analítica, mostrando uma aplicação de cálculo com sequências de
cara ou
coroa. Mas essa foi só metade da história! Aquele tipo de cálculo só funciona quando os objetos contados são indistinguíveis (um resultado
cara não é diferente de outro resultado
cara).
Se você quiser lidar com objetos que são todos diferentes entre si, então você precisa de outra abordagem. Por exemplo, quantas permutações de ##n## elementos existem? Nesse caso, os elementos precisam ser todos diferentes. Quando ##n=3##, existem ##6## permutações:
$$ \enclose{circle}{1} \enclose{circle}{2} \enclose{circle}{3} \longrightarrow
\begin{cases}
\enclose{circle}{1} \enclose{circle}{2} \enclose{circle}{3} \\
\enclose{circle}{1} \enclose{circle}{3} \enclose{circle}{2} \\
\enclose{circle}{2} \enclose{circle}{1} \enclose{circle}{3} \\
\enclose{circle}{2} \enclose{circle}{3} \enclose{circle}{1} \\
\enclose{circle}{3} \enclose{circle}{1} \enclose{circle}{2} \\
\enclose{circle}{3} \enclose{circle}{2} \enclose{circle}{1} \\
\end{cases}$$
Para esse tipo de cálculo nós precisamos da
Combinatória Analítica Numerada. Existem duas diferenças principais entre as versões numeradas e não-numeradas da teoria. A primeira que é, ao invés de usar funções geradoras normais, na versão numerada nós usamos
funções geradoras exponenciais (EGF), que são definidas como abaixo:
$$EGF(F[n]) = \sum_{n\ge 0}{F[n]\frac{z^n}{n!}}$$
Quando a ordem dos objetos é importante, os resultados tendem a crescer muito rapidamente, então dividir por ##n!## termo a termo ajuda as funções a ficarem bem comportadas.
A outra diferença é em um dos operadores básicos. A adição continua representando a união de conjuntos, mas a multiplicação, que antes era concatenação, fica um pouco diferente. No caso numerado, você não pode simplesmente concatenar, porque os números precisam ser sempre de ##1## a ##n##, e a concatenação simples te deixaria com duplicatas:
$$ \enclose{circle}{1} \enclose{circle}{2} \star \enclose{circle}{2} \enclose{circle}{1} =\; ?$$
A solução é renomear as bolinhas após concatenar, mas você precisa renomear de todas as maneiras possíveis que deixem a ordem dentro dos subconjuntos originais intacta:
$$ \enclose{circle}{1} \enclose{circle}{2} \star \enclose{circle}{2} \enclose{circle}{1} =
\begin{cases}
\enclose{circle}{1} \enclose{circle}{2} \; \enclose{circle}{4} \enclose{circle}{3} \\
\enclose{circle}{1} \enclose{circle}{3} \; \enclose{circle}{4} \enclose{circle}{2} \\
\enclose{circle}{1} \enclose{circle}{4} \; \enclose{circle}{3} \enclose{circle}{2} \\
\enclose{circle}{2} \enclose{circle}{3} \; \enclose{circle}{4} \enclose{circle}{1} \\
\enclose{circle}{2} \enclose{circle}{4} \; \enclose{circle}{3} \enclose{circle}{1} \\
\enclose{circle}{3} \enclose{circle}{4} \; \enclose{circle}{2} \enclose{circle}{1} \\
\end{cases}$$
Com isso já conseguimos definir as permutações. Elas são formadas do conjunto vazio, ou de um elemento concatenado e renomeado com uma permutação:
$$P=\varepsilon + z\star P$$
Traduzimos direto para a EGF:
$$P=1 +z P\implies P=\frac{1}{1-z}$$
E extraímos os coeficientes por comparação com a definição de EGF:
$$\begin{align*}
\sum_{n\ge 0}P[n]\frac{z^n}{n!} &= \frac{1}{1-z} \\
\sum_{n\ge 0}\frac{P[n]}{n!}z^n &= \sum_{n\ge 0}1\times z^n \\
\frac{P[n]}{n!} &= 1 \\
P[n] &= n!
\end{align*}$$
A quantidade de permutações de tamanho ##n## é ##n!##, então o método funciona!
O operador SEQ
Também podemos definir o operador ##SEQ##, que enumera todas as sequências possíveis de um conjunto:
$$SEQ(B[z]) = \frac{1}{1-B[z]}$$
Note que as permutações também podem ser vistas como as sequências renomeadas de zero ou mais átomos, então a definição acima dá o mesmo resultado.
Outra definição útil é ##SEQ_k##, que enumera apenas as sequências com ##k## elementos:
$$SEQ_k(B[z]) = (B[z])^k$$
O operador SET
Todas as funções acima são para construções onde a ordem é importante. Quando a ordem não importa, você sempre pode voltar para a Combinatória Analítica Não-Numerada. Mas e se o seu problema envolver os dois tipos ao mesmo tempo?
Nesse caso, a solução é o operador ##SET##. Ele é um operador numerado que define um conjunto onde a ordem não importa. A definição é a abaixo:
$$SET(B[z]) = e^{B[z]}$$
Por exemplo, quantas sequências possíveis de números de ##1## a ##n## existem, se a ordem não for importante? Isso é dado por:
$$SET(z) = e^z$$
Agora basta abrir a exponencial em série de Taylor e comparar com a definição de EGF:
$$\begin{align*}
\sum_{n\ge 0}F[n]\frac{z^n}{n!} &= e^z \\
\sum_{n\ge 0}\frac{F[n]}{n!}z^n &= \sum_{n\ge 0}\frac{1}{n!}z^n \\
\frac{F[n]}{n!} &= \frac{1}{n!} \\
F[n] &= 1
\end{align*}$$
Ou seja, quando a ordem não é importante, só existe uma única sequência de ##1## a ##n## que usa todos os números de ##1## a ##n##. Faz sentido né.
(É por causa desse caso que a EGF chama função geradora exponencial. A EGF de uma sequência de ##1##s é a função exponencial.)
Pokémons uniformes
Com as ferramentas em mãos, já conseguimos modelar o problema do Pokémon GO! Mas, antes de começar o problema real, vale a pena estudar um caso mais simples. Vamos supor que os pokémons são uniformes e resolver esse caso mais fácil primeiro, depois a gente generaliza para o caso onde alguns pokémons são mais raros que outros.
O truque para usar Combinatória Analítica Numerada é achar uma maneira de enxergar seu problema como uma sequência de ##1## de ##n##. No nosso caso podemos fazer da seguinte maneira: para cada pokémon nós temos uma caixinha, e cada vez que achamos um pokémon na rua, nós colocamos dentro da caixinha uma bola com um número indicando a ordem em que ele foi encontrado.
Por exemplo, suponha que andávamos pela rua e fizemos 6 capturas, nessa ordem: Bulbassauro, Squirtle, Bulbassauro de novo, Charmander, Squirtle de novo, Bulbassauro de novo. As caixinhas ficariam assim:
 | ##\enclose{box}{\enclose{circle}{1} \,\enclose{circle}{3}\, \enclose{circle}{6}}## |
 | ##\enclose{box}{\enclose{circle}{2}\, \enclose{circle}{5} }## |
 | ##\enclose{box}{\enclose{circle}{4}} ## |
Se nenhuma caixinha está vazia, então em algum ponto nós pegamos todos os pokémons (nesse caso, foi na quarta captura). Então, para ##n## capturas, se calcularmos a quantidade de configurações em que nenhuma caixinha está vazia, dividida pela quantidade de configurações totais, nós vamos ter a probabilidade de que a coleção foi completada com ##n## capturas ou menos.
Vamos lá. Se nós temos ##k## pokémons e ##n## capturas, então a quantidade de configurações totais é ##k^n## (é só atribuir uma pokémon a cada captura).
Para a quantidade de configurações em que nenhuma caixinha está vazia, precisamos modelar o problema com os operadores que descrevemos antes. Os pokémons são diferentes entre si, e a ordem importa, então vamos usar o operador ##SEQ##. A ordem das bolinhas dentro da caixinha não importa (afinal, ##\enclose{circle}{1} \enclose{circle}{3} \enclose{circle}{6}## é a mesma coisa que ##\enclose{circle}{3} \enclose{circle}{6} \enclose{circle}{1}## nesse contexto: a ordem das capturas é determinada pelos números nas bolinhas, não pela posição delas). Então vamos usar o operador ##SET##. E não podemos esquecer de que nenhuma caixinha pode ser vazia. Então a construção combinatória que descreve o problema é:
$$C=SEQ_k(SET(z)-\varepsilon)$$
..ou seja, uma sequência de ##k## conjuntos não-vazios. A função geradora é, portanto:
$$C[z]=(e^z-1)^k$$
Note que, se nós já temos a função geradora, então a parte combinatória do problema já acabou. Daqui em diante é só abrir a caixa azul e fazer as contas!
Nós queremos calcular o valor esperado do número de capturas até completar a coleção. Pela definição, isso é:
$$E[X]=\sum_{n\ge 0}n P(X=n)$$
Onde ##P(X=n)## é a probabilidade de que nós completamos a coleção na captura ##n##. Mas nós não temos isso! O que temos é ##P(x\le n)##, a probabilidade de completamos a coleção com pelo menos ##n## capturas. Felizmente não tem problema, porque dá para converter um no outro:
$$\begin{align*}
E[X]
&= \sum_{n\ge 0} n P(X=n) \\
&= \sum_{n\ge 0} \sum_{i\lt n} P(X=n) \\
&= \sum_{n\ge 0} \sum_{i\ge 0} P(X=n) [i\lt n] \\
&= \sum_{i\ge 0} \sum_{n\ge 0} P(X=n) [n\gt i] \\
&= \sum_{i\ge 0} \sum_{n\gt i} P(X=n) \\
&= \sum_{i\ge 0} P(X\gt i) \\
&= \sum_{i\ge 0} 1-P(X\le i) \\
\end{align*}$$
Esse truque funciona sempre que a distribuição é discreta, porque podemos abrir a probabilidade:
$$P(X>n)=P(X=n+1)+P(X=n+2)+\cdots$$
Vamos substituir agora. A nossa probabilidade para ##X\le n## é a divisão da quantidade de configurações com caixinhas não-vazias (que é o coeficiente ##z^n## da função geradora, vezes ##n!## porque é uma função geradora exponencial) pela quantidade total (que é ##k^n##):
$$P(X\le n)=\frac{n^k}{k^n}$$
Logo a expectativa é:
$$\begin{align*}
E[X]
&=\sum_{n\ge 0} 1-P(X\gt n) \\
&=\sum_{n\ge 0} 1-\frac{n^k}{k^n} \\
&=\sum_{n\ge 0} 1-n^k
\end{align*}$$
Esse último passo usou uma propriedade de escala das funções geradoras. Se uma sequência ##f(n)## tem função geradora ##F(z)##, então:
$$\begin{align*}
\sum_{n\ge 0}f(n)z^n &= F(z) \\
\sum_{n\ge 0}k^n f(n)z^n &= \sum_{n\ge 0}f(n)(kz)^n = F(kz)
\end{align*}$$
Voltando: nós vimos que a função geradora exponencial da sequência constante de ##1##s é ##e^z##, então dá pra jogar para dentro:
$$\sum_{n\ge 0} 1-n^k = \sum_{n\ge 0} n![z^n]\left(e^z -\left(e^{z/k}-1\right)^k\right)$$
Para prosseguir agora tem um truque muito bom, que funciona assim: se você tem uma função geradora ##F(z)##
bem comportada, então vale que:
$$\sum_{n\ge 0}n![z^n]F(z)=\int_0^\infty e^{-t}F(t)\,dt$$
Parece meio mágico, mas é só consequência da forma integral do fatorial:
$$n!=\int_0^\infty t^n e^{-t}\,dt$$
Se nós chamarmos os coeficientes da função geradora de ##f_n##, então:
$$\begin{align*}
\sum_{n\ge 0}n![z^n]F(z)
&=\sum_{n\ge 0}n! f_n = \sum_{n\ge 0} f_n n! \\
&=\sum_{n\ge 0}f_n\left(\int_0^\infty t^ne^{-t}\,dt\right) \\
&=\int_0^\infty \left(\sum_{n\ge 0}f_n t^n e^{-t}\right)\,dt\\
&=\int_0^\infty e^{-t}\left(\sum_{n\ge 0}f_n t^n \right)\,dt\\
&=\int_0^\infty e^{-t}F(t)\,dt\\
\end{align*}$$
Aplicando ao nosso caso:
$$\begin{align*}
\sum_{n\ge 0} n![z^n]\left(e^z -\left(e^{z/k}-1\right)^k\right)
&= \int_0^\infty e^{-t} \left(e^t -\left(e^{t/k}-1\right)^k\right) \,dt \\
&= \int_0^\infty \left(1 -e^{-t}\left(e^{t/k}-1\right)^k\right) \,dt \\
&= \int_0^\infty \left(1 -\left(e^{-t/k}\right)^k\left(e^{t/k}-1\right)^k\right) \,dt \\
&= \int_0^\infty \left(1 -\left(1-e^{-t/k}\right)^k\right) \,dt \\
\end{align*}$$
Nesse ponto já daria para jogar num solver numérico e calcular a solução. Mas essa integral tem uma forma fechada! Para calcular, basta fazer a mudança de variável abaixo:
$$\begin{align*}
v &= 1-e^{-t/k} \\
1-v &= e^{-t/k} \\
e^{t/k} &= \frac{1}{1-v}
\end{align*}$$
Agora deriva para achar quanto vale ##dt##:
$$\begin{align*}
\frac{dv}{dt} &= \frac{e^{-t/k}}{k} \\
dt &= k \, e^{t/k}\, dv \\
dt &= \frac{k}{1-v} dv
\end{align*}$$
Arruma os intervalos:
$$\begin{align*}
t=0 &\implies v=1-e^0=1-1=0 \\
t=\infty &\implies v=1-e^{-\infty}=1-0=1
\end{align*}$$
E por fim soca tudo na integral:
$$\begin{align*}
\int_0^\infty \left(1 -\left(1-e^{-t/k}\right)^k\right) \,dt
&= \int_0^1 \left(1 -v^k\right) \frac{k}{1-v} \,dv \\
&= k\int_0^1 \frac{1-v^k}{1-v} \,dv \\
&= k\int_0^1 (1+v+v^2+\cdots+v^{k-1}) \,dv \\
&= k \left[v+\frac{v^2}{2}+\frac{v^3}{3}+\cdots+\frac{v^k}{k} \right]_0^1 \\
&= k \left[1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{k} \right] \\
&= k H[k] \\
\end{align*}$$
Esse é o resultado final. O número esperado de capturas até você completar sua coleção de pokémons é ##k## vezes o
harmônico de ##k##!
Qual seria o número esperado de capturas então? O jogo tem 151 pokémons, mas desses tem seis que ainda não podem ser pegos: Ditto, Articuno, Zapdos, Moltres, Mewtwo e Mew. Para pegar os 145 restantes, você precisaria de ##145\times H(145)\sim 806## capturas.
Mas isso só vale se os pokémons fossem uniformes! Como alguns são mais raros que outros, precisamos melhorar nossa estimativa.
Pokémons raros
A grande vantagem da Combinatória Analítica é que ela generaliza muito fácil. O problema de completar uma coleção com elementos não-uniformes é bem difícil com técnicas tradicionais, mas aqui fica simples: basta trocar os átomos ##Z_i## por ##p_iZ_i##, onde ##p_i## é a probabilidade de ocorrência dele.
Por que isso funciona? Suponha que você tem três pokémons, de probabilidades ##p_1=1/6##, ##p_2=1/3## e ##p_3=1/2##. Ao invés de fazer ##SEQ_3(SET(z)-\varepsilon)##, como no caso uniforme, você pode fazer:
$$(SET(Z_1)-\varepsilon)\star (SET(Z_2+Z_2)-\varepsilon)\star (SET(Z_3+Z_3+Z_3)-\varepsilon)$$
Isso vai dar um resultado seis vezes maior que o esperado, mas na proporção correta. Se você jogar esse valor ##1/6## para dentro, a conta fica:
$$\begin{align*}
&(SET(\frac{Z_1}{6})-\varepsilon)\star (SET(\frac{2Z_2}{6})-\varepsilon)\star (SET(\frac{3Z_3}{6})-\varepsilon)=\\
&(SET(p_1Z_1)-\varepsilon)\star (SET(p_2Z_2)-\varepsilon)\star (SET(p_3Z_3)-\varepsilon)
\end{align*}$$
Exatamente como mencionamos! Isso mostra que o resultado é válido para qualquer probabilidade racional, e você pode fazer um sanduíche se quiser reais também.
Daqui em diante as contas são as mesmas do caso uniforme, mudando somente o interior da integral:
$$\begin{align*}
E[X]
&=\int_0^\infty\left( 1-\left(1-e^{-p_1t}\right)\left(1-e^{-p_2t}\right)\cdots\left(1-e^{-p_kt}\right) \right)\,dt\\
&=\int_0^\infty\left( 1- \prod_{1\le i\le k}\left(1-e^{-p_i t}\right) \right)\,dt\\
\end{align*}$$
Infelizmente essa integral não tem forma fechada, precisa ser calculada numericamente mesmo. Usando uma tabela com as
probabilidades estimadas de cada pokémon, eu calculei a integral, e o resultado é que você precisaria de 51568 capturas para completar sua coleção!
Como de costume, eu fiz uma simulação para conferir os valores. Os scripts
estão no github, e os resultados são:
Distribuição
uniforme, valor teórico
805.8, computacional
805.1
Distribuição
não-uniforme, valor teórico
51568, computacional
50931
Os resultados bateram como previsto! Vale a pena também estimar o tempo: se você pegar um pokémon a cada 3 minutos, então para fazer 51568 capturas você precisaria jogar por
107 dias seguidos, sem parar para dormir!
Na prática você pode completar em menos tempo que isso usando outros recursos do jogo, como evoluções e ovos, mas não tem muito segredo, para ser um mestre pokémon você precisa se dedicar bastante :)
PS: Como quase não tem literatura em português sobre o tema, as traduções ainda não são padrão. Eu traduzi Labelled Analytic Combinatorics como Combinatória Analítica Numerada, porque não achei nenhuma outra tradução que não fosse feia demais.
