Sorteios e Aniversários

No fim de semana passado eu participei do IV ENSL: o Encontro Nordestino de Software Livre, que nessa última edição foi realizado em Natal, no Rio Grande do Norte. Eu achei bastante apropriado, dado que Natal sempre foi um pólo de inovação tecnólogica! Citando alguns exemplos:

• Natal é a sede do Instituto de Neurociências do Miguel Nicolelis, pioneiro das interfaces cérebro-máquina e um dos maiores cientistas vivos.
• Alex Kipman, diretor de incubação da Microsoft, se inspirou na cidade para criar o Xbox Kinect (que, vocês devem lembrar, tinha o nome-código de Project Natal).
• Na década de 80, era onde estudava Tadeu Curinga da Silva, pioneiro dos videogames nacionais e autor do jogo Em Busca dos Tesouros, o melhor jogo da plataforma ZX-81.
• Além disso, Natal também é onde mora o Karlisson Bezerra, autor das tirinhas do Nerdson!

Embora o turismo nerd tenha sido excelente, eu fiquei um pouco frustrado de não ter aproveitado tanto o turismo tradicional. Eu consegui ir à praia e provar a deliciosa manteiga de garrafa, mas não deu tempo de fazer o típico passeio de buggy pelas dunas. Por outro lado, posso não ter feito o passeio de buggy, mas presenciei um outro tipo de bug!

Tradicionalmente, todo encontro de software livre termina com um sorteio de brindes. Como é um evento de programadores, naturalmente não se usou um saco plástico cheio de papéis com os nomes de cada um. Ao invés disso, o povo programou uma solução na hora mesmo, usando só três linhas de python:

import random
x = open("participantes.txt").readlines()
print x[random.randint(0, len(x))]

Como isso foi feito no modo interativo, então basta repetir a última linha para realizar um novo sorteio. Mas enquanto eles digitavam isso no telão, eu pensei: putz, esse código tem dois bugs. Você consegue achá-los?

Primeiro Bug

O primeiro bug, na real, não é do programa e sim da API do Python. Quando você projeta uma API, precisa ter muito cuidado para que as interfaces sejam consistentes, e o randint() é um dos raros casos onde o Python pisa no tomate.

O problema é que quase todas as definições de intervalo do Python usam intervalos semi-abertos, mas o randint usa um intervalo fechado (se você não lembra o que é um intervalo aberto ou fechado, pergunte ao professor Joe). Na notação de list slices, ou mesmo no range(), o último número não faz parte da lista; mas no randint() o último número conta.

Por isso, se você tentar sortear com randint(0, len(x)), ele pode sortear um número além do fim da lista, e você vai ter um erro do tipo list index out of range. Murphy sendo Murphy, é claro que isso aconteceu ao vivo lá no telão :)

Depois que uma API já está publicada e sendo usada, é muito difícil consertar um bug assim. Num mundo ideal você consertaria a interface, mas isso poderia quebrar todos os códigos legacy que a usam. Por isso, o melhor que dá pra fazer é depreciar a função original e propor uma interface nova, que no nosso caso é a randrange():

print x[random.randrange(0, len(x))]

Nesse problema em específico tem uma outra solução até mais elegante, que é usar o choice():

print random.choice(x)

Mas nenhuma dessas soluções conserta o outro bug do programa...

Segundo bug

Esse é mais sutil. No começo o programa estava funcionando bem, mas em um certo ponto, eis que o programa sorteia uma pessoa que já tinha sido sorteada antes! Eram mais ou menos 700 participantes, então a chance disso acontecer deveria ser bem pequena né? Mas algum tempo depois dessa pessoa, teve mais uma que foi sorteada duas vezes, e depois dessa ainda mais uma. Como pode um evento tão raro acontecer tantas vezes?

Marmelada não era, porque todo mundo viu o código, então o erro deve estar no gerador de números aleatórios do Python, certo? Surpreendentemente, a resposta é não! Esse é um caso clássico onde a nossa intuição falha. A análise ingênua é que a chance de um número ser sorteado duas vezes é 1/700 vezes 1/700, ou seja, 0.0002%. Mas esta é a análise correta do problema errado.

Se eu tivesse feito só dois sorteios, entre 700 participantes, e perguntasse qual era a chance do Ricbit ganhar nos dois, aí sim a chance seria 0.0002%. Mas o nosso problema é diferente. Nós temos um número p=700 de participantes, e vamos fazer s=70 sorteios (de olho eu acho que foram uns 70 sorteios: tinha brinde pra caramba no evento, e alguns sorteados eram descartados porque não estavam na sala).

O enunciado correto então é: qual o valor esperado do número de pessoas que é sorteada duas vezes? Esse valor é bem mais alto do que a intuição imagina!

Vamos calcular passo a passo quanto dá isso. Primeiro, vamos calcular qual é a probabilidade do Ricbit ser sorteado no primeiro evento. Isso é fácil né, a chance é 1/p. A chance oposta, ou seja, do Ricbit não ser sorteado no primeiro evento, é de (1-1/p). Continuando, a chance do Ricbit não ser sorteado em nenhum evento, é a abaixo:



Qual é a chance do Ricbit ser sorteado no primeiro evento e não ser sorteado em nenhum outro? Pelo mesmo raciocínio acima, ela é:



E qual a chance do Ricbit ser sorteado uma única vez durante toda a série de sorteios? Ora, é a chance de ser sorteado só no primeiro sorteio, mais a chance de ser sorteado só no segundo, e assim por diante. Como essas chances são todas iguais, então a chance do Ricbit ser sorteado uma única vez é:



Uma outra maneira de pensar a fórmula acima é que ela representa a chance de ser sorteado uma única vez numa posição qualquer, vezes o número de posições possíveis.

Agora chegamos onde queríamos, qual a chance do Ricbit ser sorteado exatamente duas vezes na série toda? Analogamente, é a chance de ser sorteado duas vezes, multiplicada pelo número de combinações possíveis dos dois sorteios ao longo da série. Logo, ela vale:



Por fim, qual o valor esperado do número de repetições? Uma repetição é quando uma pessoa é sorteada duas vezes: então basta, para cada pessoa, somar a probabilidade de ser sorteado duas vezes. Daí, o valor esperado final é:



Substituindo os parâmetros, descobrimos que o valor esperado é 3.1, o que realmente é bem próximo das três repetições que eu presenciei (nos cálculos eu desprezei sorteios triplos, quádruplos, etc, porque esses são realmente raros). Eu fiz uma simulação de Monte Carlo para quem só acredita vendo:

Simulação de Monte Carlo em Python

Na verdade, esse resultado contra-intuitivo é bem conhecido na literatura, o povo chama de Paradoxo do Aniversário. Numa festa com 30 pessoas, qual a chance de haver duas pessoas com o mesmo aniversário? A intuição é que isso deve ser raro, mas a probabilidade, na verdade, é de 70%. A argumentação é exatamente a mesma anterior, e, de fato, se você usar a nossa fórmula com s=30 e p=365, vai descobrir que o valor esperado é 1.1. Ou seja, em média, festas com 30 pessoas costumam ter um par de pessoas com o mesmo aniversário.

Se você trabalha com computação, então isso tem uma aplicação prática. A chance de repetição em um sorteio é exatamente a mesma chance de uma colisão em uma hash table, assumindo que sua função de hash tem distribuição uniforme. Por isso, quando você for dimensionar o tamanho de uma hash, pode usar nossa fórmula para saber o número esperado de colisões (por exemplo, em 70 inserções numa hash de tamanho 700, você vai ter em média 3 colisões).

E como resolver o problema original do sorteio? Basta tirar da lista os números que já foram sorteados! Uma implementação curta em python é a abaixo:

import random
x = open("participantes.txt").readlines()
random.shuffle(x)

print x.pop()

Ao invés de sortear nomes de maneira independente, você simplesmente faz uma permutação aleatória da lista com o shuffle() e vai tirando os elementos de um em um usando o pop(). Esse programa é bem curto e não tem os problemas do original. Mas, no fim das contas, se o programa original não tivesse nenhum bug, o sorteio não teria sido engraçado como foi :)

Se você é veterano do FISL, considere no ano que vem ir também ao ENSL. O povo é divertido, a comida local é excelente, e nada supera ir a uma praia do Nordeste entre uma palestra e outra :)