Arquivo mensais:março 2012

Cabras, Ferraris e probabilidades

Rookie

Ricardo: Hoje contaremos com um post de um convidado especial, e mais entendido que eu no assunto. Pedro Natal é um gaúcho iteano que atravessou comigo a Polytechnique e seguiu para ser mestre em matemática aplicada pela Universidade de Paris. Tem por vícios chá inglês, café forte e propor problemas matemáticos à turma quando nos reunimos em algum KFC. Sem mais, entrego-lhes uma leve discussão sobre cabras e probabilidades.

Embora o título logo acima possa levar a crer que discorreremos sobre uma peça de teatro do absurdo, o assunto principal deste texto é matemática. Mais especificamente: cabras, Ferraris e programas de auditório; não precisamos de mais que um conhecimento básico desses três itens para seguirmos. E, convenhamos, o que há de melhor para aguçar nossos sentidos probabilísticos do que histórias envolvendo Sílvio Santos, ruminantes e carros de corrida?

Suponha que você esteja num programa de auditório estilo Sílvio Santos, e que você deva escolher uma dentre três portas. Uma delas esconde uma Ferrari; as outras duas, simples cabras. Você escolhe, digamos, a de número 1. Nesse momento, antes de revelar o resultado da sua escolha, Sívio Santos $-$ que sabe onde está a Ferrari $-$ abre uma das outras duas portas e revela uma cabra. Ele então pergunta: “Você muda a sua escolha ou continua com a número 1?”.  Em outras palavras, existe alguma vantagem em trocar de porta?

Se essa é a primeira vez que você se depara com esse problema, eu sugiro honestamente que você aproveite para pensar nele antes de ler o próximo parágrafo. A resposta correta é mais interessante do que parece e está longe de ser trivial.

É possível que você tenha chegado à seguinte conclusão: como só restam duas portas, cada uma delas tem 1/2 de chance de conter a Ferrari, e logo não há vantagem em trocar de porta. Infelizmente, esse raciocínio não está correto. Sim, existe uma vantagem em trocar de porta. A probabilidade que a porta inicial contenha a Ferrari é 1/3, ou seja, a probabilidade de ganhar trocando de porta é de 2/3. Por quê? A maneira mais fácil de entendê-lo é com o seguinte desenho (que eu não tive vergonha de roubar da Wikipédia):

A figura da esquerda mostra que a probabilidade de você ter acertado na sua primeira escolha é de 1/3, ou seja, a probabilidade que a Ferrari esteja em uma das outras duas portas é de 2/3. Quando Sílvio revela a cabra, ele não altera as probabilidades calculadas anteriormente! Assim, como vemos na figura da direita, a probabilidade de encontrar a Ferrari trocando de porta é de 2/3.

Esse famosíssimo problema, conhecido como Problema de Monty Hall, gerou muita confusão e discussão nos EUA há pouco mais de 20 anos. Ele foi publicado por uma colunista chamada Marylin vos Savant na revista Parade em 1990, e desencadeou uma enxurrada de respostas furiosas da parte dos leitores que não aceitavam que a resposta fosse diferente de 1/2 (reza a lenda que, das 10 mil reclamações recebidas, mais de mil foram redigidas por pessoas com um PhD).

Mas o que há de errado afinal com o raciocínio que leva à conclusão de que não há vantagem em trocar de porta? Um pequeno detalhe: Sílvio Santos sabe o que há atrás das portas. O raciocínio seria correto se a porta a ser revelada fosse escolhida ao acaso, mas ela não é! Sílvio Santos nunca vai revelar a Ferrari para o jogador, e é essa assimetria que gera a assimetria probabilística do problema,

Como observado pelo (meu grande amigo) dono do blog Todas as configurações possíveis, existe ainda uma outra maneira intuitiva de se compreender a vantagem em mudar de escolha: se houvesse 1000 portas, você escolhesse uma, e Sílvio abrisse 998, revelando cabras em todas elas, você trocaria? Qual é, honestamente, a chance de você ter acertado de primeira?

Ao leitor que não ficou convencido com esses argumentos intuitivos: uma prova mais formal (mas menos astuciosa) envolvendo a famigerada fórmula de probabilidade condicional existe. Não por acaso, é exatamente o conceito de probabilidade condicional que está por trás da confusão que o Problema de Monty Hall gera na nossa intuição.

As histórias divertidas envolvendo probabilidade não acabam por aí. Num futuro artigo, que deve ser matematicamente (um pouquinho) mais complicado, falaremos sobre as peculiaridades da mistura de álcool, probabilidades condicionais, e cadeias de Markov!

Deixe um comentário

Epidemias, parte I

Hardcore

Trombei esses dias com um artigo de 2001 sobre propagação de vírus em humanos e sua comparação a vírus de internet. O estudo da disseminação de infecções é velho na física, diversos modelos de epidemias são estudados e muitos com resultados razoavelmente bons. Um ponto comum em modelos estudados pela epidemiologia é a noção de threshold, ou seja, o valor mínimo de eficiência que uma infecção deve ter para conseguir se propagar. Novamente, esse é um post hardcore, os corajosos sigam-me, vamos ver com cuidado como isso funciona.

Esse post ficou grande, então parti em dois. Nesse primeiro, comento o modelo de propagação de vírus em seres humanos, no próximo trato da internet.

Representamos indivíduos como pontos e o contato entre indivíduos como linhas em um grande grafo. Passamos a nos perguntar qual seria um modelo eficaz de grafo para modelizar as relações humanas. Certamente não conhecemos pessoas aleatoriamente na rua, costumamos conhecer melhor nossos vizinhos, familiares e colegas de trabalho, que por sua vez conhecem-se. Um jeito legal de modelizar essa ideia, que chamamos de grafo de small world, é tomar um anel de pontos, sendo cada ponto ligado a seus $ m$ vizinhos mais próximos. Em seguida, passamos “em revista” essas conexões da seguinte forma: cada ponto terá uma probabilidade $ p$ de desfazer uma conexão com um vizinho seu no sentido horário e associá-la a algum outro ponto aleatoriamente. A ideia do sentido horário é apenas para evitar mexer na mesma conexão duas vezes. Se $ p=1$, essa revista resulta em um grafo em forma de anel com conexões completamente aleatórias. Se $ p=0$, o grafo continuará no modelo do conhecimento apenas da vizinhança, mas, se $ p$ é pequeno, o grafo tornar-se-á um modelo muito próximo do que queremos: vizinhos possuem uma chance maior de se conhecerem do que conhecerem alguém do outro lado do grafo, mas de vez em quando algum vizinho seu conhece alguém lá longe, o que é bem coerente com a realidade e até permite aquelas coincidências do tipo “hoje meu avô almoçou com o pai de um professor meu”.

O resultado está bem representado nessa figura, onde os pontos são inicialmente ligados a seus $ 2m$ vizinhos mais próximos, com $ m=2$. É o famoso modelo de Watts-Strogatz, ou modelo de small-world:

Podemos, com esse modelo bonitinho, estudar a propagação de infecções entre seres humanos. Imaginemos um vírus que, a cada contato entre são e infectado, tenha uma probabilidade $ nu$ de contágio e, a cada “turno”, tenha uma probabilidade $ \delta$ de cura de um infectado. A chance de um ponto possuir $ k$ vínculos é $ P(k)= \frac{1}{\langle k\rangle}e^{-k/\langle k\rangle}$ nesse modelo, e $ \langle k\rangle=2m$. A equação estocástica dessa criança não é bonita, então vamos usar um mean field, calcular o que vai acontecer com a densidade média de infectados supondo que todos os pontos possuem o mesmo número de conexões, $ 2m$, naturalmente, e que todos estão ligados a um número de infectados igual ao valor médio de infectados, essas são as características de uma abordagem de campo médio. A densidade total de infectados, denotada $ \rho_t$ por ser uma função do tempo, é apenas o número total de infectados dividido pelo número total de pessoas. Diremos que a variação na densidade de infectados $ \rho_t$ (a fração da população infectada naquela “rodada”), que toma valores entre 0 e 1, perde a cada “rodada” o equivalente a $ \delta\rho_t$ (os que se curaram) e ganha o equivalente ao contato são-infectado, que é $ nu\langle k\rangle\rho_t(1-\rho_t)$, ou seja, chance de um contato ser são-infectado $ \rho_t(1-\rho_t)$ multiplicada pelo número médio de contatos $ \langle k\rangle$ e pela chance de esse contato transmitir a infecção $ \nu$. Dividindo a equação toda por $ \delta$ e sem precisar ir muito além de uma reparametrização no tempo, podemos escrever:

\[\frac{d}{dt}\rho_t=-\rho_t+\lambda\langle k\rangle\rho_t(1-\rho_t).\]

Com $ \lambda= \frac{\nu}{\delta}$ o valor que interessa para medir a eficácia de uma infecção. E essa equação, ainda que seja apenas uma teoria de campo médio, já nos dá bastante informação sobre o que está acontecendo. Você até pode pedir para o Wolfram Alpha resolver essa para você, eu não faria diferente, mas vale mais estudar algumas propriedades na mão. Chamamos densidade de persistência o valor de $ rho_t$ para o qual sua derivada temporal é zero. Se ela não é nula, temos uma infecção persistente em uma fração da população. Igualando a equação acima a zero, percebemos duas respostas possíveis: ou $ rho_t = 0$, ou $ \rho_t=1- \frac{1}{\lambda\langle k\rangle}$. Como a densidade de infectados não pode ser menor que 0, naturalmente, descobrimos que, se $ \lambda < \frac{1}{\langle k\rangle}$, então a única solução possível é $ \rho_t=0$, pois a segunda solução fica absurda. Mas, se a infecção é mais eficaz que o threshold $ \frac{1}{\langle k\rangle}$, teremos um crescimento da densidade de persistência que tende a 1 quando $ \lambda$ se aproxima do infinito.

Densidade de persistência com m=2.

E fica claro que o threshold, dependendo do inverso do número médio de contatos, que nesse modelo é proporcional ao número de vizinhos, nos dá uma informação esperada: quanto maior o número de vizinhos (contatos), menos eficaz uma doença deve ser para se propagar. Se uma doença é bem eficaz, podemos reduzir seu impacto com uma diminuição nos vizinhos, se está com gripe, não saia de casa.

Esse modelo é bem coerente com diversas observações de epidemias simples em populações. Por esse mecanismo de small-world, apenas doenças suficientemente poderosas, com eficácia $ \lambda$ maior que um determinado limite, podem se propagar pela população, possuem vida no longo prazo. A mudança de fase ocorre no threshold $ \lambda^\star= \frac{1}{\langle k\rangle}$ que, no gráfico acima, ocorre em $ \lambda = 0,25$. O próximo passo nesse modelo seria estudar um grafo em que pessoas podem morrer, nascer, tornar-se imunes, tomarem vacinas ou tornarem-se mais suscetíveis a doenças com o tempo.

Tudo isso é muito interessante, mas não consegue explicar a propagação de vírus na internet. Em um próximo post, veremos que, na internet, small-world não pode ser aplicado (afinal, todos conhecem o Google ou o Facebook) e a própria noção de threshold, por um fenômeno estatístico fascinante, desaparece.

2 respostas

Prova surpresa

Geek Hardcore Rookie

O post de hoje não é muito informativo, é mais perturbador, um probleminha de lógica para não deixar você dormir.

Um professor chega à aula e avisa sua classe que aplicará, no mês de abril, uma prova surpresa. Um aluno, que futuramente se tornaria matemático na área de lógica, pergunta o que o professor entende por surpresa. Estranhando a pergunta, o professor responde que uma prova surpresa é uma prova tal que, no início de cada dia do mês de abril, os alunos não podem deduzir ou saber que a prova será aplicada naquele dia. Triunfante, o aluno conclui que não haverá prova nenhuma, pois:

– Se a prova não for aplicada até o 30 de abril, então ela terá que necessariamente ser nesse dia e, no começo do dia, já não será surpresa. Então o 30 de abril não pode ser a data da prova.

– Se a prova não for aplicada até o 29 de abril, então ela terá que ser necessariamente nesse dia, pois o 30 está excluído. Mas, assim sendo, ela não será uma surpresa, então o dia 29 não pode ser o dia da prova.

– Se a prova não for aplicada até o 28 de abril, então ela terá que ser necessariamente nesse dia, pois o 30 e o 29 estão excluídos. Mas, assim sendo, ela não será uma surpresa, então o dia 28 não pode ser o dia da prova. E assim por diante, ele exclui todos os dias.

No dia 12, ele recebe a prova. Onde ele errou?

7 respostas

O problema da diretora do colégio

Geek

Venho por meio deste compartilhar um problema deveras interessante que requereu algumas horas do meu dia para a programação. Escrevi-o há algum tempo a um amigo cursando ciência da computação que, sendo garoto de programa, certamente saberia apreciar o que fiz, e sou carente desse tipo de apreciação. O problema que me foi proposto em meu curso de física estatística foi o da diretora do colégio.

Aconteceu uma vez comigo, recebi, acho que na sexta série, um papel para escrever os nomes dos coleguinhas com que gostaria de estar ano seguinte. Escrevi os dois nomes que queria (era uma criança sozinha e com poucos amigos), entreguei e no ano seguinte estava na sala deles. Ainda, as salas não mudaram muito, o que é razoável, já que as pessoas tendiam a querer ficar com quem já estavam, achei que a diretora havia atendido aos pedidos individualmente, mas hoje penso que não. Vamos tentar entender a razão de, se a diretora fosse realmente levar aqueles papéis a sério, ela teria que aprender um pouco mais de física e informática.

Imagine-se uma diretora de colégio, responsável por preparar as classes para o próximo ano letivo. Como você é boazinha, decide deixar os alunos escolherem com quem eles querem ficar no próximo ano, então dá a possibilidade de eles escreverem em um papel nomes dos coleguinhas que mais querem encontrar no ano seguinte. Mas sendo uma diretora justa, você pergunta aos professores quais alunos seria melhor que não ficassem na mesma turma, uma “lista negra” de duplas que seria melhor que ficassem separados. Com essas duas informações: a preferência dos alunos e a lista negra dos professores, como determinar qual distribuição ideal de alunos?

Esse não é um problema fácil. Podemos pensar em tratar o problema brutalmente: listar todas as possibilidades e verificar qual satisfaz melhor às condições das listas, tanto a de preferência quanto a de exclusão, mas isso, com um número pequeno de alunos, logo atinge limites astronômicos. O número de configurações possíveis de sala será $2^{\text{numero de alunos}}$, com 100 alunos você teria algo perto de $10^{30}$ configurações. Meu processador i5 só aguenta algo perto de 10MIPS, o que me dá o direito de realizar $10^7$ instruções por segundo e eu precisaria de pelo menos $10^{23}$ segundos para fazer qualquer coisa com essas configurações, isso é mais que a idade do universo. Essa conta provavelmente está bem errada, mas acredito no argumento de que, para listar todos os casos possíveis, terei que investir mais que uma tarde em cálculos. Precisamos pensar em um jeito mais malandro.

Primeiro, vamos pensar no quadro teórico do problema e como implementar de maneira adequada. Eu quero um jeito prático de saber quantas condições uma configuração de alunos satisfaz e quantas ele viola. Vou atribuir pesos iguais à preferência dos alunos e à lista dos professores, poderiam ser diferentes, mas sou preguiçoso. Seja n o número de alunos. Tomo um vetor $S_n$ com $n$ coordenadas que podem valer 1 ou -1. Se $S_i=1$, então o aluno $i$ está na sala A. Se $S_i=-1$, o aluno $i$ está na sala B.

Em seguida, defino a matriz $J_{ij}$, que é $n\times n$. Ela contém a seguinte informação: $J_{ij} = 1$ se o aluno $i$ quer ficar com o aluno $j$. $J_{ij} = -1$ se não é legal que o aluno $i$ fique com o aluno $j$ e $J_{ij}=0$ se eles são indiferentes entre si. Eu poderia ter privilegiado a opinião dos professores atribuindo um peso muito negativo ao invés de -1, mas vamos dar uma chance as alunos e atribuir pesos iguais às preferências dos alunos e dos professores. Isso vai servir para calcular o quanto de “felicidade” a configuração gera. Se dois alunos estão na mesma sala e queriam estar na mesma sala, a felicidade aumenta. Se eles não podem estar na mesma sala e estão em salas separadas, a felicidade aumenta. Se estão em salas diferentes e queriam estar juntos, ela diminui. Mas como computar isso? Basta calcular: $J_{ij}\cdot S_i\cdot S_j$.

Se eles estão na mesma sala, o produto $ S_i\cdot S_j$ será 1 e, se querem estar na mesma sala, $J_{ij}$ será 1, então o resultado será 1. Se não podem e estão na mesma sala, o resultado será -1. Se não estão na mesma sala, o produto $S_i\cdot S_j$ é -1. Deu para entender que esse produto representa bem a “felicidade” gerada pelo estudo de um par de alunos. Precisamos, então somar $J_{ij}\cdot S_i\cdot S_j$ para todos os $i$’s e $ j$’s e isso dará a felicidade da configuração.

Mais uma vez, isso exige produtos e somas com $2^n$ configurações possíveis, é absolutamente impossível resolver esse problema na força bruta para mais de 50 alunos. Para tal, precisamos de um método mais eficiente, e eu escolho Monte Carlo.

O método de Monte Carlo é um dos mais poderosos e usados na física estatística para resolver esse tipo de problema impossível. Tomamos uma configuração inicial de classes aleatória (um vetor $S$ aleatório) e procedemos da seguinte forma:

  • Trocamos um aluno de sala (tiramos $i$ aleatório e fazemos $S_i\to -S_i$)
  • Checamos a felicidade da nova configuração.
  • Se aumentou, ele fica nessa sala nova.
  • Se diminuiu, ele volta para a primeira sala.

Você ficaria impressionado em saber que, com 50 alunos, eu consigo a configuração certa de $S$ em menos de 1000 iterações. Claro, tomei um $J$ agradável o suficiente para que eu soubesse qual a configuração certa e esse $J$ em particular provavelmente facilitou minha vida. Tomei a sala em panelinha: metade dela quer ficar entre si e não pode ficar com a outra metade. Eu esperava um S da forma $(1,1,\ldots ,1,-1,-1,\ldots ,-1)$, e o tenho rapidamente com esse algoritmo.

Sabendo um pouco mais de física, eu poderia te contar que os átomos possuem uma propriedade chamada spin, que pode apontar para cima (1) ou para baixo (-1). Em uma rede cristalina, os spins interagem e são capazes de definir muita coisa, como, por exemplo, se a rede será um imã ou não. O que acontece é que os spins sempre atingem uma configuração que minimiza a energia da rede, e essa energia é calculada se o material é antiferromagnético (os spins gostam de ficam em direções opostas) ou ferromagnético (eles preferem se alinhar). Em algumas redes, você até mistura esses dois tipos e calcular a magnetização total (o conjunto de todos os spins) pode parecer um inferno.

Mas a energia total é calculada da seguinte forma: você multiplica os spins para saber se estão alinhados ou não, se estão, o produto será positivo, se estão invertidos, o produto será negativo. E então você multiplica pelo fator $J_{ij}$, que vale 1 se o material é ferromagnético ou -1 se é antiferromagnético (ou 0 se os spins estão longe e não interagem). A energia total será a soma para todos os i’s e j’s de $J_{ij}\cdot S_i\cdot S_j$ onde $S_i$ é o spin da partícula $i$. A magnetização do sistema será a configuração de spins que minimiza essa energia. Ora, é difícil não ver que a magnetização de um material misto entre dia e ferromagnetismo é o exato mesmo problema que uma diretora de escola enfrenta ao escolher quais alunos ficarão em qual sala.

Esse método, Monte Carlo, parece quase milagroso, mas possui um problema grave. Não é o caso da matriz $J$ que escolhi, que é extremamente agradável, mas com algum outro $ J$ eu poderia ter um sério problema. Eu poderia atingir uma configuração em que trocar qualquer aluno de sala causaria uma queda na felicidade, mas que, se eu trocasse dois ou três, poderia ter um ganho. Esse tipo de situação é um “mínimo local” da felicidade, um defeito sério em Monte Carlo, que não pode escapar de um mínimo local e atingir a verdadeira configuração ideal de salas, pois ele só aceita ganhos reais e imediatos. Como podemos nos livrar disso? Ah, precisamos de uma adaptação de Monte Carlo, chamada “Algoritmo de Metrópolis”, mas isso fica para outro dia, a diretora da minha sétima série, pelo que escrevi, já terá bastante trabalho pela frente.

1 resposta