Quando eu era criança pequena lá na década de 80, eu tinha um brinquedo de tanque de guerra. Ele chamava Panzer, e era fabricado pela brinquedos Mimo. Para a época era bem divertido: tinha controle remoto, e, além de andar, ainda disparava mísseis!
Mas eu não percebia a ironia do brinquedo. O Panzer não era só um brinquedo, ele existiu de verdade. Na vida real, o Panzer era uma máquina nazista de destruição. A série Panzer de tanques alemães foi responsável pela morte direta de incontáveis aliados. Ver um Panzer surgindo no horizonte era como ver a morte vindo em sua direção. Era um mimo esse Panzer.
Por outro lado, o Panzer era forte, mas não era invencível. Os aliados tinham armas capazes de deter o Panzer, o problema era descobrir quantas dessas armas eles deveriam levar para o front. Poucas semanas antes do Dia D, os alemães começaram a usar o novo modelo Panzer V, e os aliados não tinham como estimar quantas armas levar sem saber quantos Panzer V os inimigos fabricaram.
Foi então que os aliados usaram a arma definitiva contra o Panzer: a Matemática! Usando um truque muito esperto, eles estimaram que os alemães estavam fabricando 270 Panzers por mês. Depois que a guerra acabou, eles foram nos arquivos alemães conferir os números, e na verdade estavam fazendo 276 Panzers por mês. A estimativa foi muito boa!
O truque dos aliados se baseava em um erro dos alemães e em uma hipótese estatística. O erro dos alemães era que os tanques tinham número de série sequencial. Quando saíam da fabrica, eram numerados como 1, 2, 3, e assim por diante. Ao fazer isso, eles deixaram uma brecha para os hackers aliados.
Suponha que você capturou um Panzer alemão, e o serial dele era 14. Você consegue estimar quantos tanques eles produziram baseado só nesse número? No caso geral não, mas você pode fazer uma hipótese simplificadora, que é supor que o tanque que você capturou é aleatório (ou seja, os alemães estavam distribuindo igualmente os tanques por toda a Europa).
Com essa hipótese a intuição é clara. Vamos supor, hipoteticamente, que os alemães fizeram 200 tanques. Qual chance de você capturar um tanque de serial menor ou igual a 14 nessa situação? É 14/200 né? E se os alemães fizeram só 20 tanques? Aí a chance é 14/20, dez vezes maior que 14/200. Com a hipótese de tanque aleatório, é mais provável que os alemães tenham feito 20 tanques do que 200 tanques.
Você pode formalizar esse argumento usando o teorema de Bayes, e calcular o valor esperado do número de tanques. Vamos fazer as contas na caixa azul:
A fórmula final é super simples, mas ela funciona mesmo na prática? Podemos testá-la fazendo uma simulação numérica. Para isso, eu fiz dez mil simulações. Em cada uma eu sorteio o número de tanques fabricados, e escolho aleatoriamente 3 deles. Aí eu calculo a estimativa pela fórmula, e normalizo o erro. O código está no github, e o histograma resultante é o abaixo. A normalização é tal que o valor 0 é uma estimativa totalmente correta:
Mas eu não percebia a ironia do brinquedo. O Panzer não era só um brinquedo, ele existiu de verdade. Na vida real, o Panzer era uma máquina nazista de destruição. A série Panzer de tanques alemães foi responsável pela morte direta de incontáveis aliados. Ver um Panzer surgindo no horizonte era como ver a morte vindo em sua direção. Era um mimo esse Panzer.
Por outro lado, o Panzer era forte, mas não era invencível. Os aliados tinham armas capazes de deter o Panzer, o problema era descobrir quantas dessas armas eles deveriam levar para o front. Poucas semanas antes do Dia D, os alemães começaram a usar o novo modelo Panzer V, e os aliados não tinham como estimar quantas armas levar sem saber quantos Panzer V os inimigos fabricaram.
Foi então que os aliados usaram a arma definitiva contra o Panzer: a Matemática! Usando um truque muito esperto, eles estimaram que os alemães estavam fabricando 270 Panzers por mês. Depois que a guerra acabou, eles foram nos arquivos alemães conferir os números, e na verdade estavam fazendo 276 Panzers por mês. A estimativa foi muito boa!
A Quantidade de Tanques
O truque dos aliados se baseava em um erro dos alemães e em uma hipótese estatística. O erro dos alemães era que os tanques tinham número de série sequencial. Quando saíam da fabrica, eram numerados como 1, 2, 3, e assim por diante. Ao fazer isso, eles deixaram uma brecha para os hackers aliados.
Suponha que você capturou um Panzer alemão, e o serial dele era 14. Você consegue estimar quantos tanques eles produziram baseado só nesse número? No caso geral não, mas você pode fazer uma hipótese simplificadora, que é supor que o tanque que você capturou é aleatório (ou seja, os alemães estavam distribuindo igualmente os tanques por toda a Europa).
Com essa hipótese a intuição é clara. Vamos supor, hipoteticamente, que os alemães fizeram 200 tanques. Qual chance de você capturar um tanque de serial menor ou igual a 14 nessa situação? É 14/200 né? E se os alemães fizeram só 20 tanques? Aí a chance é 14/20, dez vezes maior que 14/200. Com a hipótese de tanque aleatório, é mais provável que os alemães tenham feito 20 tanques do que 200 tanques.
Você pode formalizar esse argumento usando o teorema de Bayes, e calcular o valor esperado do número de tanques. Vamos fazer as contas na caixa azul:
Suponha que conseguimos capturar k tanques. Dentre esses k tanques, o maior serial encontrado tem o valor m. Com essas informações, vamos calcular qual é o valor esperado do número de tanques produzidos, que vamos chamar de n. Podemos abrir esse valor esperado pela definição:
$$E[n\;|\;m,k] = \sum_{n} n \; p(n\; |\; m,k)$$
O problema então é achar a probabilidade condicional de n, dados m e k. Nós ainda não sabemos quanto vale essa probabilidade, mas podemos abri-la usando o teorema de Bayes:
$$p(n\;|\;m,k)=\frac{p(m,k\;|\;n)\;p(n)}{p(m,k)}$$
Essas três probabilidades nós conseguimos calcular! A primeira delas, p(m,k|n), sai por combinatória. Dado um vetor de tamanho n, de quantas maneiras conseguimos escolher k elementos, de modo que o maior deles seja m?
Um dos elementos precisa necessariamente ser o m, então só precisamos calcular a posição dos outros k-1 restantes. E eles precisam ser menores que m, então só podem estar nas m-1 posições menores que m. Por isso, essa quantidade vale binomial(m-1, k-1). Note, entretanto, que isso só vale quando n>=m, caso contrário a probabilidade é zero (não tem como o máximo ser m se o vetor tem um tamanho menor que m).
Para calcular a probabilidade desejada, temos que achar de quantas maneiras podemos escolher k elementos dentre n, sem considerar a restrição do maior deles ser m. Mas isso é o próprio binomial(n, k). Então, a probabilidade é:
$$p(m,k\;|\;n) = \frac{\displaystyle{m-1\choose k-1}} {\displaystyle{n\choose k}}[n\ge m]$$
Vamos agora para a segunda, p(n). Eu não tenho nenhuma informação sobre quantos tanques foram produzidos, então não sei qual é a probabilidade de ter n tanques. Mas eu posso chutar que a distribuição é uniforme. A chance de ter 15 tanques, ou de ter 500 tanques, a priori, deve ser a mesma. Por isso, vamos fazer p(n) ser uma constante independente de n:
$$p(n)=c$$
A última, p(m,k), é a probabilidade do máximo ser m em k escolhas, independente do valor de n. Para isso, podemos usar a lei da probabilidade total:
$$p(m,k) = \sum_n p(m,k\;|\;n) \;p(n)$$
Essas duas já sabemos calcular! É só substituir:
$$\begin{align*} p(m,k) &= \sum_n p(m,k\;|\;n) \;p(n) \\ &= \sum_n \frac{{m-1\choose k-1}} {{n\choose k}}[n\ge m]\;c\\ &= \sum_{n\ge m} c {m-1\choose k-1} {n\choose k}^{-1}\\ &= c {m-1 \choose k-1} \sum_{n\ge m} {n\choose k}^{-1}\\ \end{align*} $$
A somatória tem uma forma fechada, que você pode achar com o algoritmo de Gosper:
$$\sum_{n=m}^{\infty}{n\choose k}^{-1}=\frac{m}{k-1}{m\choose k}^{-1}$$
Substituindo:
$$\begin{align*} p(m,k) &= c {m-1 \choose k-1} \sum_{n\ge m} {n\choose k}^{-1}\\ &= c {m-1 \choose k-1} \times \frac{m}{k-1}{m\choose k}^{-1} \\ &= \frac{cm}{k-1} {m-1 \choose k-1} {m\choose k}^{-1} \\ \end{align*} $$
Agora podemos voltar e substituir as três probalidades na fórmula de Bayes:
$$ \begin{align*} p(n\;|\;m,k)&=\frac{p(m,k\;|\;n)\;p(n)}{p(m,k)} \\ &= \frac{\displaystyle{m-1\choose k-1}{n\choose k}^{-1}[n\ge m]\times c} {\displaystyle\frac{cm}{k-1}{m-1\choose k-1}{m\choose k}^{-1}}\\ &= \frac{k-1}{m}{m\choose k}{n\choose k}^{-1}[n\ge m] \end{align*}$$
Por fim, podemos substituir na fórmula do valor esperado:
$$\begin{align*} E[n\;|\;m,k] &= \sum_{n} n \; p(n\; |\; m,k)\\ &= \sum_n n \frac{k-1}{m}{m\choose k}{n\choose k}^{-1}[n\ge m]\\ &= \frac{k-1}{m}{m\choose k}\sum_{n\ge m} n {n\choose k}^{-1}\\ \end{align*}$$
Essa somatória também tem uma forma fechada por Gosper:
$$ \sum_{n=m}^{\infty} n{n\choose k}^{-1}=\frac{m(m-1)}{k-2}{m\choose k}^{-1}$$
Chegamos então na substituição final:
$$\begin{align*} E[n\;|\;m,k] &= \frac{k-1}{m}{m\choose k}\sum_{n\ge m} n {n\choose k}^{-1}\\ &= \frac{k-1}{m}{m\choose k}\times\frac{m(m-1)}{k-2}{m\choose k}^{-1} \\ &= \frac{(k-1)(m-1)}{k-2} \\ \end{align*}$$
$$E[n\;|\;m,k] = \sum_{n} n \; p(n\; |\; m,k)$$
O problema então é achar a probabilidade condicional de n, dados m e k. Nós ainda não sabemos quanto vale essa probabilidade, mas podemos abri-la usando o teorema de Bayes:
$$p(n\;|\;m,k)=\frac{p(m,k\;|\;n)\;p(n)}{p(m,k)}$$
Essas três probabilidades nós conseguimos calcular! A primeira delas, p(m,k|n), sai por combinatória. Dado um vetor de tamanho n, de quantas maneiras conseguimos escolher k elementos, de modo que o maior deles seja m?
Um dos elementos precisa necessariamente ser o m, então só precisamos calcular a posição dos outros k-1 restantes. E eles precisam ser menores que m, então só podem estar nas m-1 posições menores que m. Por isso, essa quantidade vale binomial(m-1, k-1). Note, entretanto, que isso só vale quando n>=m, caso contrário a probabilidade é zero (não tem como o máximo ser m se o vetor tem um tamanho menor que m).
Para calcular a probabilidade desejada, temos que achar de quantas maneiras podemos escolher k elementos dentre n, sem considerar a restrição do maior deles ser m. Mas isso é o próprio binomial(n, k). Então, a probabilidade é:
$$p(m,k\;|\;n) = \frac{\displaystyle{m-1\choose k-1}} {\displaystyle{n\choose k}}[n\ge m]$$
Vamos agora para a segunda, p(n). Eu não tenho nenhuma informação sobre quantos tanques foram produzidos, então não sei qual é a probabilidade de ter n tanques. Mas eu posso chutar que a distribuição é uniforme. A chance de ter 15 tanques, ou de ter 500 tanques, a priori, deve ser a mesma. Por isso, vamos fazer p(n) ser uma constante independente de n:
$$p(n)=c$$
A última, p(m,k), é a probabilidade do máximo ser m em k escolhas, independente do valor de n. Para isso, podemos usar a lei da probabilidade total:
$$p(m,k) = \sum_n p(m,k\;|\;n) \;p(n)$$
Essas duas já sabemos calcular! É só substituir:
$$\begin{align*} p(m,k) &= \sum_n p(m,k\;|\;n) \;p(n) \\ &= \sum_n \frac{{m-1\choose k-1}} {{n\choose k}}[n\ge m]\;c\\ &= \sum_{n\ge m} c {m-1\choose k-1} {n\choose k}^{-1}\\ &= c {m-1 \choose k-1} \sum_{n\ge m} {n\choose k}^{-1}\\ \end{align*} $$
A somatória tem uma forma fechada, que você pode achar com o algoritmo de Gosper:
$$\sum_{n=m}^{\infty}{n\choose k}^{-1}=\frac{m}{k-1}{m\choose k}^{-1}$$
Substituindo:
$$\begin{align*} p(m,k) &= c {m-1 \choose k-1} \sum_{n\ge m} {n\choose k}^{-1}\\ &= c {m-1 \choose k-1} \times \frac{m}{k-1}{m\choose k}^{-1} \\ &= \frac{cm}{k-1} {m-1 \choose k-1} {m\choose k}^{-1} \\ \end{align*} $$
Agora podemos voltar e substituir as três probalidades na fórmula de Bayes:
$$ \begin{align*} p(n\;|\;m,k)&=\frac{p(m,k\;|\;n)\;p(n)}{p(m,k)} \\ &= \frac{\displaystyle{m-1\choose k-1}{n\choose k}^{-1}[n\ge m]\times c} {\displaystyle\frac{cm}{k-1}{m-1\choose k-1}{m\choose k}^{-1}}\\ &= \frac{k-1}{m}{m\choose k}{n\choose k}^{-1}[n\ge m] \end{align*}$$
Por fim, podemos substituir na fórmula do valor esperado:
$$\begin{align*} E[n\;|\;m,k] &= \sum_{n} n \; p(n\; |\; m,k)\\ &= \sum_n n \frac{k-1}{m}{m\choose k}{n\choose k}^{-1}[n\ge m]\\ &= \frac{k-1}{m}{m\choose k}\sum_{n\ge m} n {n\choose k}^{-1}\\ \end{align*}$$
Essa somatória também tem uma forma fechada por Gosper:
$$ \sum_{n=m}^{\infty} n{n\choose k}^{-1}=\frac{m(m-1)}{k-2}{m\choose k}^{-1}$$
Chegamos então na substituição final:
$$\begin{align*} E[n\;|\;m,k] &= \frac{k-1}{m}{m\choose k}\sum_{n\ge m} n {n\choose k}^{-1}\\ &= \frac{k-1}{m}{m\choose k}\times\frac{m(m-1)}{k-2}{m\choose k}^{-1} \\ &= \frac{(k-1)(m-1)}{k-2} \\ \end{align*}$$
A Estimativa na Prática
A fórmula final é super simples, mas ela funciona mesmo na prática? Podemos testá-la fazendo uma simulação numérica. Para isso, eu fiz dez mil simulações. Em cada uma eu sorteio o número de tanques fabricados, e escolho aleatoriamente 3 deles. Aí eu calculo a estimativa pela fórmula, e normalizo o erro. O código está no github, e o histograma resultante é o abaixo. A normalização é tal que o valor 0 é uma estimativa totalmente correta:
A estimativa não ficou muito boa não! Ao invés de ter uma gaussiana em torno do zero, o estimador tem um bias muito forte para os negativos. Felizmente, esse problema só acontece porque capturamos apenas 3 tanques. Se, ao invés disso, tivéssemos capturado 30 tanques, então o histograma seria bem melhor. Compare o histograma de 30 tanques sobreposto ao de 3 tanques:
Bem melhor né? Agora quase todas as estimativas estão bem próximas do zero. Esse método é bastante sensível ao número de tanques capturados. Os aliados sabiam disso, por isso que a estimativa deles foi tão boa (estimaram 270 tanques/mês, quando o valor real era 276). Sabe quantos tanques eles capturaram para fazer essa estimativa? Só dois tanques!
Claro que tem um truque. A estimativa com dois tanques é muito ruim, mas eles notaram que os alemães colocavam serial em todas as peças do tanque. Em especial, cada tanque tinha 48 rodas, cada uma com um serial único. Por isso, eles conseguiram usar a fórmula com k=96, o que deu a precisão alta que queriam. E no fim a matemática ganhou a guerra :)
Nenhum comentário:
Postar um comentário