Arquivos da categoria: Geek

Posts para iniciados em ciência que ainda não completaram seu treinamento Jedi. Estudantes em faculdades de exatas são o que tenho em mente nessas publicações.

Os aluguéis de Berlim

Geek Hardcore

Minha namorada está buscando um apartamento para alugar em Paris começando no mês de novembro, e a busca tem sido uma tragédia em diversos atos. Cubículos pequenos, muita competição, preços altos e até imobiliárias que mais parecem esquema de pirâmide que um estabelecimento sério têm acompanhado a jornada dessa física teórica nas últimas duas semanas. Quanto aos preços, ao menos há um fator positivo, uma lei recente baixada inspirada na solução que Berlim tenta implementar para resolver seu problema de aluguéis: um teto de preço baseado no valor médio das redondezas.

A lei diz que o valor de um aluguel não pode ser superior à média do bairro de uma diferença maior que 10%. Ou seja, se a média do bairro é 22 euros o metro quadrado, um aluguel não pode ser mais alto que 24,2 euros o metro quadrado. Simples assim. Essa é uma ideia bem divertida, que me fez considerar a seguinte questão: o problema da Berlim gananciosa.

Nessa nova Berlim, a lei é um pouco mais rígida. Uma pessoa não pode impor um aluguel maior que a média de seus vizinhos cuja diferença entre a média e o aluguel seja maior que 10%. A pergunta é: é possível que exista uma cidade com essa lei em que todas as pessoas cobram o maior aluguel possível pela lei? Ou seja, obrigando as pessoas a cobrarem exatamente 110% da média de seus vizinhos, é possível haver uma cidade em que todas as pessoas conseguem cobrar essa quantia?

Para bem definir o problema, vamos estabelecer hipóteses fundamentadas na realidade. A primeira: minha cidade é unidimensional, parecida com Cuernavaca, porque quero uma noção de vizinhança bem definida e porque D=1 é meu número favorito de dimensões. Segunda: casas na periferia não têm esperança de ganhar dinheiro no aluguel em relação aos vizinhos e possuem preço fixo. Isso vem do fato, inspirado em minha experiência parisiense, de que morar longe do centro só é bom se for na direção de Versailles, e olhe lá. Isso fixa as condições de contorno do problema. Dado um preço fixo nas casas da periferia, é possível que o resto da cidade cobre um aluguel superior em \alpha porcento à média de seus vizinhos?

A resposta, e já mando com spoilers, é: depende do \alpha. Há valores em que isso é possível, mas existe um limite para a extorsão de seus inquilinos se você precisa respeitar a regra dos \alpha porcento. Para entender o que acontece, vamos começar com o caso de uma cidade pequena, a cidade de Berlim de três habitantes, chamada B_3. Vejamos a cara dessa cidade.

Cidade de Berlim 3A regra geral das casas de Berlim gananciosa é:

 x_n = \frac{(1+\alpha)}{2}(x_{n+1}+x_{n-1}).

Seja (1+\alpha)/2=\lambda, para simplificar nossa vida. A única exigência da primeira cidade de Berlim que vamos estudar, B_3, é que x_2=\lambda (1+1)=2\lambda, então o valor de \lambda pode ser qualquer coisa, não há limites para a ganância de B_3

O caso de B_4, no entanto, é diferente. Vejamos como é essa cidade:

Cidade de Berlim 4Neste caso, os valores de x_2 e x_3 serão fixos pelo sistema

 \begin{cases} x_2=\lambda(1+x_3) \\ x_3 = \lambda(1+x_2) \end{cases} .

Vocês sabem que eu gosto de matrizes, então vamos colocar isso em notação de gente grande. Os aluguéis de B_4 serão definidos pelo sistema

 \left(\begin{matrix} 1 & -\lambda \\ -\lambda & 1 \end{matrix}\right)\left(\begin{matrix} x_2 \\ x_3 \end{matrix}\right) = \left(\begin{matrix} \lambda \\ \lambda \end{matrix}\right).

Esse é um sistema linear bem bonito, mas vocês devem se lembrar das aulas do ensino que diziam, com razão, que a vida fica mais cinza, o mundo perde a cor e você perde a vontade de cantar uma bela canção quando o determinante da matriz que define o sistema linear se anula. Quando isso acontece, não há mais solução possível para o sistema. E note que o determinante que nossa querida matriz é

 \det \left(\begin{matrix} 1 & -\lambda \\ -\lambda & 1 \end{matrix}\right) = 1-\lambda^2.

Ou seja, algo muito errado acontece quando \lambda=1, que acontece no mesmo momento em que \alpha=1. Não apenas o sistema não tem solução, não há mais valor de alguel possível para satisfazer tanta ganância, mas se você tentar impor um \lambda mais alto que um, não encontrará a solução que deseja. Se \lambda > 1, a solução do sistema apresentará valores negativos de x_2 e x_3, e acho que é seguro acrescentar como hipótese baseada na realidade que preços de aluguel devem ser positivos.

Assim, percebemos que com quatro casas o valor máximo que a lei pode impor para a extorsão dos inquilinos é de \lambda=1, o que equivale a \alpha=1, ou o máximo que podemos impor é que uma casa cobre o dobro da média dos vizinhos. Vejamos o que acontece quando a cidade é maior, visitemos B_5.

Cidade de Berlim 5Nesse caso o sistema linear que define os valores de x_2, x_3 e x_4 será

 \left(\begin{matrix} 1 & -\lambda & 0 \\ -\lambda & 1 & -\lambda \\ 0 & -\lambda & 1 \end{matrix}\right)\left(\begin{matrix} x_2 \\ x_3 \\ x_4 \end{matrix}\right) = \left(\begin{matrix} \lambda \\ 0 \\ \lambda \end{matrix}\right).

Vamos chamar a matriz que define esse sistema 3 x 3 de A_3. A partir de agora, a matriz que define o sistema n \times n será A_n. O determinante dela pode ser calculado com aquela técnica que você aprendeu no segundo colegial e errava toda vez que tentava fazer de cabeça sem usar aquela técnica das duas colunas fantasmas que você copia ao lado da última.

 \det A_3 =1-2\lambda^2

E o determinante se anula no valor \lambda = \sqrt{2}/2, o que equivale ao valor de \alpha=\sqrt{2}-1\approx 0.71, que é menor que um. É fácil perceber a tendência desse problema: quanto maior a cidade, menor é a taxa de ganho extra que podemos cobrar e ainda exigir que todos cobrem mais aluguel que seus vizinhos. O valor de \alpha diminui com o número de casas N da cidade! Mas… diminui como?

E aqui vou descrever como foi meu processo para resolver esse problema. Eu queria achar a relação entre o \alpha máximo e N, o tamanho da cidade. Eu sabia que \alpha seria decrescente em N, mas não sabia como. Seria \alpha proporcional a 1/N? Ou a 1/N^2? Ou talvez uma exponencial negativa de N? A exponencial eu podia ignorar, vi matrizes vezes demais no olhos e sei que esse tipo de problema terá uma relação polinomial, mas não vou excluir a possibilidade. Para resolver esse problema, a primeira coisa que fiz foi pensar como físico, ou seja, trigger warning aos que gostam de um raciocínio matemático rigoroso. Vamos pegar uma cidade muito grande, grande o suficiente para ignorar as bordas, e vamos voltar à equação principal do modelo:

 x_n = \frac{(1+\alpha)}{2}(x_{n+1}+x_{n-1}).

E podemos jogar um pedaço para lá e outro para cá para obter uma outra forma dessa equação de recorrência:

 \alpha (x_{n+1}+x_{n-1}) = x_{n+1}+x_{n-1}-2x_n.

O termo à direita é um velho amigo nosso, é uma segunda derivada discreta do aluguel. Nós brincamos com algo parecido em um dos primeiros posts desse blog, sobre a interpretação física do Laplaciano, e chegou a hora de usá-la. Eu tenho que dividir esse termo da direita por um diferencial ao quadrado para obter uma derivada, e esse diferencial é o tamanho de meu grid na derivada discreta. Em termos do modelo, eu defino que a posição de cada casa é dada pela variável l e a distância entre duas casas é dada por \Delta l^2. Dividindo ambos os lados da equação por \Delta l eu obtenho:

 \frac{\alpha}{\Delta l^2}(x_{n+1}+x_{n-1}) = \frac{x_{n+1}+x_{n-1}-2x_n}{\Delta l^2}.

O lado direito dessa equação, quando a cidade é bem grande e as casas são bem próximas, converge para \frac{d^2x}{dl^2}, enquanto o termo da esquerda pode ser simplificado lembrando que a soma dos vizinhos é \frac{2x_n}{(1+\alpha)}. Isso tudo resulta na seguinte equação diferencial:

 \sigma.x(l) = \frac{d^2x}{dl^2}.

Sendo

 \sigma = \frac{2\alpha}{(1+\alpha)dl^2}.

Eu sei que esse diferencial no denominador é revoltante a seu espírito matemático, mas não é mais minha responsabilidade zelar por seu coração sensível. Esse dl é a distância entre duas casas. Suponhamos que a cidade toda tenha tamanho 1, em unidades de tamanho de cidade, então a distância média entre duas casas é dl=1/N. Para que essa equação diferencial faça algum sentido, eu preciso que \sigma não seja nem zero, nem infinito, então, como exigência, eu preciso que \alpha diminua conforme dl diminui, ou seja, preciso que:

 \sigma=\frac{2\alpha}{(1+\alpha)dl^2}\sim 1\Rightarrow\alpha\sim\frac{1}{N^2}

Sendo esse \sim o símbolo oficial de “tem o mesmo comportamento assimptótico de”, mas costumamos ler como: “se comporta como”, “é mais ou menos parecido em algum limite que eu espero que você tenha entendido” ou “não exatamente, mas tipo quase lá”.

Então o valor máximo da extorsão deve decrescer com o quadrado do número de casas. O problema está razoavelmente resolvido, mas o algebrista dentro de mim grita por uma solução melhor que essa. Vamos ver como seria aquela matriz A_n para uma cidade bem grande. Teremos algo da forma:

 A_n = \left(\begin{matrix} 1 & -\lambda & 0 & 0 & \cdots & 0 \\ -\lambda & 1 & -\lambda & 0 & \cdots & 0 \\ 0 & -\lambda & 1 & -\lambda & \cdots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -\lambda & 1 \end{matrix}\right).

A_n é uma matriz tridiagonal com diagonal repleta de 1’s e co-diagonais preenchidas por -\lambda. Eu não apenas quero o determinante dessa criatura, eu quero encontrar as raízes do determinante e, mais especificamente, a primeira raiz que seja maior que \frac{1}{2}. Eu sei que \lambda=\frac{1}{2} equivale ao caso \alpha=0, onde todos aluguéis são iguais à média dos vizinhos e, pelas condições nas bordas, isso representaria o caso em que todos os aluguéis são iguais a 1. Valores de \lambda menores que meio representariam alguém cobrar um aluguel menor que a média dos vizinhos e, por mais que esse seja o sonho de minha namorada, não serão considerados. A primeira raiz do determinante que é maior que meio equivale ao primeiro valor de \lambda que torna o sistema impossível, valores acima disso tornam alguns aluguéis negativos e não me interessam. Eu quero saber como a primeira raiz do determinante acima de meio se aproxima de meio quando o tamanho da matriz aumenta, e isso não é um problema muito fácil.

O determinante de uma matriz tridiagonal tem fórmula, e nesse caso essa fórmula é:

 \det A_n=\det A_{n-1}-\lambda^2\det A_{n-2} .

Isso não me ajuda muito, aliás, quase me desespera. Isso significa que o determinante será um polinômio de grau cada vez mais alto em \lambda e eu conheço minhas limitações, resolver um polinômio de grau maior que quatro exatamente quase nunca é possível e eu começo a perder a esperança quando escrevo os primeiros cinco casos desse polinômio, eles não parecem ter nenhum padrão reconhecível e minha busca parece vã. Eu vou atrás das raízes desses polinômios, e lá as coisas começam a ficar interessantes.

No caso de A_2, encontramos \lambda=\pm 1 como raízes. Para A_3, temos as raízes \lambda=\pm\frac{\sqrt{2}}{2}. O determinante A_4 ainda tem raízes, é um polinômio de grau 4 que pode ser reduzido a um polinômio de grau 2 (a origem dessa redução é a simetria do problema, a segunda casa, por simetria, deve ter o mesmo valor da penúltima, por exemplo). As raízes são \lambda=\pm \frac{1\pm\sqrt{5}}{2}, que, aliás, são a razão áurea e sua inversa.

Espera… 1, \frac{\sqrt{2}}{2} e razão áurea… eu conheço esses valores. Eles são todos cossenos de alguém (ou quase)! Isso não pode ser coincidência. O determinante de A_n é um polinômio cujas raízes possuem uma ligação com cossenos. E quando eu percebi isso, fechei os punhos e soprei por entre os dentes cerrados a palavra Chebyshev

Eu e você nos lembramos da aula de Física-Matemática II, quando Domingos Marchetti mandou aquela lista de exercícios que pedia para provar propriedades dos polinômios de Chebyshev. Entre elas, o fato de que polinômios de Chebyshev possuem \cos(\frac{k\pi}{n+1}) como raízes. Se eu quero um polinômio com essas raízes, preciso torturar Chebyshev. E eu devia ter desconfiado, veja a relação de recorrência que gera esses polinômios. Seja T_n(x) o polinômio de Chebyshev (de segundo tipo) de grau n, teremos:

 T_{n}(x) = 2xT_{n-1}(x)-T_{n-2}(x)

E me diz se isso não é muito parecido com minha relação de recorrência dos determinantes de A_n! O determinante de A_n não é exatamente T_n(x), mas eu consigo ligar os dois com algumas manobras. O post já está longo e vou escrever direto a relação, é fácil chegar nela operando a relação de recorrência. Teremos

 \det A_n=(2\lambda)^nT_n\left(\frac{1}{2\lambda}\right).

Ou seja, se queremos as raízes do determinante de A_n, basta tomar o inverso das raízes do polinômio de Chebyshev! Sabemos que essas raízes são x_k=\cos(\frac{k\pi}{n+1}). Assim, as raízes de nosso determinante tridiagonal são dadas por:

 \lambda_k=\frac{1}{2\cos\left(\frac{k\pi}{n+1}\right)}

Sem surpresas, esses valores coincidem exatamente com 1, \frac{\sqrt{2}}{2} e razão áurea. Queremos a primeira raiz acima de meio, ela é dada quando calculamos o valor k=1. Dessa forma, o maior valor possível da Berlim gananciosa será

 \lambda_{\text{max}}=\frac{1}{2\cos\left(\frac{\pi}{n+1}\right)}\sim\frac{1}{2}+\frac{\pi^2}{4N^2},

onde expandi para grandes valores de N para ver o comportamento assimptótico de uma cidade grande. Como \lambda=\frac{1}{2}+\frac{\alpha}{2}, confirmamos que, para que esse sistema tenha soluções positivas, existe um limite máximo no lucro dos proprietários que diminui conforme o tamanho da cidade aumenta, e é dado por:

 \alpha<\frac{\pi^2}{2N^2}

Confirmando o que nossa intuição física já sabia naquele cálculo sem rigor acima, a dependência ocorre com o inverso do quadrado do número de habitantes na cidade unidimensional.

E no caso da cidade bidimensional? Não consegui resolver a matriz dessa, não houve Chebyshev que salvasse, mas o cálculo não rigoroso, que deu certo uma vez, parece indicar uma dependência no inverso de N, considerando uma cidade quadrada cujas bordas contém \sqrt{N} casas enfileiradas.

Eu imagino que esse problema tenha sido um pouco mais difícil que o problema médio que apresento aqui, mas é fascinante. Nunca antes eu tinha encontrado polinômios de Chebyshev in the wild, tampouco com uma motivação tão interessante. Vou guardar esse na manga, esperando algum dia algum aluno preguiçoso, como eu era, perguntar-me de que servem esses tais polinômios cujo nome eu tenho que dar ctrl-c ctrl-v para não errar.

E uma nota final: minha namorada encontrou um apartamento finalmente. Fica em uma cidade simpática ao sul de Paris, com acesso ao metrô, mas não tão perto, com alguns metros quadrados, mas não tantos. Foi difícil achar, então comemoramos; mas confesso que, se perguntasse um pouco pelos corredores do prédio, provavelmente ficaria estarrecido em descobrir que o \alpha desse lugar não respeita nenhum majorante.

Os ônibus de Cuernavaca

Geek

Para o post de hoje, vamos ao México. Ele será um pouco mais sofisticado que meus posts habituais, mas acho que esse blog sentia falta de uma matemática um pouquinho mais pesada. Vou tentar manter Geek, sem passar ao Hardcore, prometo que, lendo com paciência, é um assunto fascinante.

A cidade de Cuernava, um pouco ao sul da Cidade do México, é um lugar muito especial para a física estatística e para quem gosta de matrizes aleatórias. Com um pouco mais que 300.000 habitantes, essa cidade apresenta um urbanismo estranho: ela é construída entre duas grandes rodovias que levam à capital do país e, entre elas, possui uma grande avenida central. Suas demais ruas, como os ramos de uma folha, se espalham entre as rodovias ao redor da avenida. Nessa avenida principal passa a linha 4 de ônibus de Cuernavaca, foco de nosso maior interesse, que possui propriedades fascinantes.

A linha 4 não é regulada por um sistema unificado de transportes, cada condutor de ônibus em Cuernavaca é dono de seu ônibus, como se fosse apenas um táxi grande, e quer, certamente maximizar seus lucros. Se, no entanto, dois ônibus estiverem muito próximos, o que está logo atrás sofrerá prejuízo financeiro; para evitar essa situação, os motoristas de Cuernavaca chegam a pagar “olheiros” posicionados estrategicamente na avenida para contar ao motoristas há quanto tempo o outro ônibus passou para que, assim, eles possam acelerar ou diminuir o passo, evitando encontrar o ônibus seguinte e o anterior. Diminuir a velocidade demais também não é bom pois, não apenas isso seria um serviço profundamente mal-prestado, mas ele correria o risco de ser ultrapassado pelo ônibus que o precede.

Dois físicos visitaram Cuernavaca em 2000 e ficaram fascinados com as características desse sistema de transporte. Durante um mês, eles coletaram dados de chegada e saída dos ônibus da estação central da linha 4 de Cuernavaca. Seus resultados foram relatados em um intrigante artigo, reproduzo o gráfico:

cuernavaca

O valor que interessou os físicos foi: dada a chegada de um ônibus, quanto tempo o próximo demorava? Eles armazenaram esses dados em um belo histograma que, propriamente normalizado, resultou nos dados marcados com uma cruz no gráfico acima. As barras e a linha, que coincidem quase perfeitamente com os dados, são resultados teóricos de um modelo que os físicos suspeitaram ter a ver com o problema.

Se você tomar uma matriz hermitiana (A=A^\dagger) e colocar como entradas nela valores aleatórios tirados de uma distribuição gaussiana complexa, terá o que chamados de uma matriz do GUE, Gaussian Unitary Ensemble. Falei um pouco sobre matrizes gaussianas em um post anterior. Se as entradas da matriz são gaussianas, seus autovalores, como vocês devem suspeitar, possuem uma densidade de probabilidade bem diferente e, em particular, apresentam um fenômeno de repulsão logarítmica, ou seja, se os autovalores fossem partículas, elas se repeliriam com uma força que poderia ser interpretada como um potencial logarítmico na distância entre as partículas: V(x) \propto \log|x_i-x_j|. Em português, se você encontra um autovalor de uma matriz gaussiana em um ponto, é extremamente improvável encontrar outro muito perto dele. Se você estudar a estatística da distância entre os autovalores: tirar várias matrizes gaussianas aleatoriamente, diagonalizar, extrair autovalores, estudar a distância entre um autovalor e seu vizinho, fazer um histograma, normalizar corretamente e plotar em um gráfico, a teoria de matrizes aleatórias diz que você terá, quanto maior for a matriz, uma função cada vez mais próxima de \frac{32}{\pi} s^2 e^{-4s^2/\pi}.

Surpreendentemente, essa função é a linha plotada no gráfico acima, encaixando-se com perfeição nos dados. As barras são resultados de simulações feitas com matrizes gaussianas, colando mais uma vez com o resultado dos ônibus. O fato de os motoristas tomarem cuidado para não se aproximarem demais de seus vizinhos fazia o papel da repulsão logarítmica dos autovalores, e fazia com que os ônibus de Cuernavaca se comportassem como os autovalores de uma matriz gaussiana complexa.

O artigo segue com mais detalhes para comprovar seu argumento, mas aquilo não era o suficiente. Faltava criar um modelo para os ônibus que permitisse deduzir esse fato, que não é nada óbvio. Isso foi feito em um artigo seguinte, modelizando com carinho essa rede de transportes. Como queremos simplificar para compreender, o modelo pode não parecer muito realista; mas é isso que físico fazem: simplificam e tentam, na simplicidade, perceber a emergência de um fenômeno complexo e suas causas. Vamos aos ônibus.

Como o acelerar, desacelerar, parar, desabastecer-se e abastecer-se de passageiros é um processo complicado e imprevisível, precisamos simplificar drasticamente para que a matemática do modelo seja tratável. Ao invés de andar o caminho entre um ponto e outro, tomemos um modelo com duas hipóteses:

  • Os ônibus ficam parados um tempo aleatório em cada ponto. Passado esse tempo, são “teleportados” ao próximo ponto.
  • Dois ônibus jamais se encontram. Enquanto um está em um ponto, o próximo não pode teleportar a ele.

Com essas duas regras, podemos simular o comportamento desses ônibus em uma linha. Reproduzo o gráfico do artigo novamente:

buses_cuernavacaEsse modelo, depois de algumas contas complicadas, nos conduz ao que queríamos provar: a distância entre os ônibus será dada pela mesma fórmula da distância entre valores próprios de uma matriz gaussiana. Claro, fizemos o modelo para que isso desse certo, e ficamos felizes que, apesar de simples, ele reproduz elementos importantes da realidade.

Não é um caso isolado. Os ônibus de Cuernavaca são um exemplo curioso e interessante do fenômeno de universalidade em matrizes aleatórias. Em uma analogia, é como se em sistemas complexos houvesse uma versão do teoria central do limite para processos altamente correlacionados. Não foi por acaso que Wigner, Dyson e Mehta escolheram matrizes aleatórias como tentativa de modelizar a interação forte no núcleo atômico, eles desconfiavam, com razão, que um processo estatístico acontecia em sistemas com um número suficientemente elevado de elementos. Tal processo, como toda boa estatística, mata as flutuações aberrantes e preserva as características extensivas do modelo.

Ainda não solucionamos o mistério da universalidade. A teoria de matrizes aleatórias aparece em contextos demais, não conseguimos ainda desvendar a razão disso. Em caos quântico há conjecturas fundamentais a respeito, em teoria dos números também. Essa emergência pode ser coincidência, ou pode ser manifestações de um teorema central do limite para variáveis fortemente acopladas. Não sabemos ainda, mas buscamos. Meu trabalho atual é um pouco sobre isso, estudar como é a transição de um sistema fortemente correlacionado, como os ônibus de Cuernavaca, a um sistema de variáveis independentes, como os ônibus de São Paulo. Essa mudança de comportamento é profundamente interessante, ocorre em diversos fenômenos físicos e é mediada pelas mais variadas formas de interação. Mas um novo post sobre meu trabalho fica para outro dia.

No grande tomo The Oxford Handbook of Random Matrix Theory, Freeman Dyson escreve no prefácio, após comentar sobre os ônibus de Cuernavaca:

“O benefício do sistema autorregulatório dos ônibus à população é medido pela variável R, a razão entre o tempo de espera médio de um passageiro e o tempo médio entre os ônibus. O melhor valor possível de R é 0,5, quando a distância entre os ônibus é exatamente igual. Se os ônibus não são correlacionados, teremos R=1. Em Cuernavaca, como eles se comportam como autovalores de uma matriz gaussiana, temos R=3\pi / 16=0.589, muito mais perto da situação ideal que da situação independente. Não sou capaz de determinar se as aplicações de matrizes aleatórias no mercado financeiro, como as descritas no capítulo 40 deste livro por Bouchaud e Potters, geram algum benefício comparável. Quando um especialista em finanças me diz que algum pedaço de feitiçaria financeira certamente irá beneficiar a humanidade, sou levado a acreditar que um motorista de ônibus de Cuernavaca faria um trabalho melhor.”

 

Top na balada

Geek Rookie

No post de hoje, vamos resolver um problema grave, clássico e profundo: como escolher o melhor namorado ou namorada para casar, ou como escolher o melhor garoto ou garota na balada para levar para casa aquela noite. Não são problemas simples, mas, como a maior parte dos dilemas pessoais, usando frieza, crueldade e fechando os olhos para os reais problemas sociais envolvidos, podemos tirar conclusões bem interessantes. No post de hoje, vamos deduzir a estratégia para maximizar suas chances de, em uma noite, levar o melhor parceiro possível para seu quarto mostrar sua coleção de discos do Elvis.

Deixo apenas registrado que se você está buscando referências sérias nesse blog sobre como se dar bem em uma balada, deve estar realmente desesperado. Continuemos.

O problema se apresenta da seguinte forma: você pegará na noite de hoje um número N de pessoas. Dentre essas pessoas, você estabelece um ranking de qualidade, seu objetivo é levar a melhor delas para casa porque, convenhamos, você já passou da idade de ficar só dando beijinho em balada. Você encontra uma pessoa, corteja, afeiçoa-se e tem duas opções: ou escolhe essa para levar para casa, ou rejeita. O problema é claro: você corre o risco de estar rejeitando a melhor dentre as N. Supondo que você e a pessoa têm um pingo de dignidade, não poderá voltar atrás nessa decisão! Nessa lógica, qual a melhor estratégia para maximizar suas chances de escolher de fato a melhor dentre as N possíveis?

Se achou as contas a seguir chatas e complicadas, tudo bem, eu entendo; você pode pular para o final do post para descobrir a melhor estratégia.

A natureza do seu dilema é a informação incompleta. Cortejando a pessoa número n, você tem apenas o ranking dela em relação às que já viu, não tem a menor ideia de como ela se compara às que virão. A primeira pessoa sempre será a melhor até então (e a pior), não parece uma boa estratégia aceitar a primeira que aparece, porque a noite é longa e promete. Por outro lado, se você encontrar a melhor até então na penúltima pessoa, as chances são baixas de encontrar a melhor de todas na última, desprezar a melhor na penúltima parece também uma estratégia ruim. Entre uma recusa quase certeira da primeira e uma aceitação quase certa da penúltima, deve haver algum ponto intermediário em que a estratégia fica a melhor possível.

Vamos calcular esse ponto e determinar qual a melhor estratégia para o problema. Para isso, vamos primeiro modelizar o problema de forma precisa:

  • Você estima que cortejará N pessoas até o final da noite.
  • Uma vez rejeitando a pessoa, não pode voltar atrás.
  • Seu ganho é 1 se você escolher a melhor dentre as N pessoas e 0 se escolher qualquer outra.
  • Se chegar à última, leva a última. Em outras palavras, se a balada começou a miar e são seis da manhã, você leva para casa a pessoa que sobrou, sinto muito. Nisso, convenhamos que o modelo é bem preciso.

Confesso que o modelo tem um problema, a noção de tudo ou nada, de que seu ganho é zero ainda que você leve a segunda melhor, enquanto, convenhamos, não é algo tão ruim. Vamos imaginar que você é extremamente exigente e sentirá que a noite não valeu a pena porque, levando a segunda melhor, pensará apenas na primeira durante a noite toda.

Para resolver o problema, vamos definir duas variáveis. X_n(1) é o seu ganho esperado se na n-ésima pessoa entrevistada você encontrar a melhor até então; X_n(0) é seu ganho esperado caso a n-ésima entrevistada não seja a melhor vista até então. Em nosso modelo, claro, X_n(0)=0, você não espera ganhar nada levando alguém para casa que nem é o melhor dos primeiros n que você já viu, vale mais tentar outras pessoas e correr o risco de encontrar o melhor nos seguintes. Se você encontrar na n-ésima a melhor até então, o seu ganho é a chance de a melhor pessoa estar entre as n primeiras. Como a ordem em que você pega as pessoas é aleatória, essa chance é de n/N. Assim, X_n(0) = 0 e X_n(1)=n/N.

Em seguida, definimos o ganho esperado se descartamos a pessoa n-1 e passamos para a n, chamamos essa variável de Y_n. O seu ganho esperado descartando a pessoa n-1 depende do que você vai fazer encontrando a pessoa n. Se você decidir ficar com a pessoa n, seu ganho esperado saltando n-1 é o ganho esperado de n, ou seja, X_{n}. Se você decide saltar também a n, então seu ganho esperado será Y_{n+1}. Você vai tomar essa decisão baseando-se nesses valores, você deve se perguntar “Quem é maior: X_{n} ou o valor médio de Y_{n+1}?”. Comparando esses dois valores, você sabe qual será seu comportamento no próxima pessoa. A fórmula para Y_n será, portanto, definida de forma recursiva:

 Y_n = \max \{X_{n},\langle Y_{n+1} \rangle \}

Onde \langle x \rangle é a média de x, escrita desse jeito com o único objetivo de fazer os estatísticos lendo esse texto terem um pequeno derrame de nervoso.

Esse cálculo recursivo encorpora bem o dilema descrito acima. Perto das últimas escolhas, X_n fica grande se você encontra a melhor pessoa até então e Y_n fica pequeno. No início, contudo, X_n é pequeno e vale mais apostar no futuro do que estacionar no começo. Para que a fórmula recursiva faça sentido, ela precisa ter um ponto de partida. Nisso usamos a última hipótese, o ganho esperado pulando a última casa é o mesmo que o da última casa, ou seja, pular a última não adianta, você leva a última opção se chegar nela: X_N=Y_N. Usando a fórmula acima, e com algum malabarismo que não cabe aqui, você consegue deduzir a expressão de Y_n:

 Y_n = \frac{n}{N}\sum_{k=n}^{N-1} \frac{1}{k}

Assim, começa a valer a pena escolher uma pessoa a partir do momento em que X_n > Y_n, ou seja, quando estamos na k-ésima pessoa e 1>\sum_{k=n}^{N-1} \frac{1}{k}. A partir desse valor, seu ganho esperado ficando com a melhor pessoa encontrada até agora é maior que o ganho esperado no futuro pulando essa pessoa; logo, é estatisticamente mais interessante levar essa para casa.

Claro que encontrar esse valor de k não é simples, tem que somar fração e isso é chato, tem umas partes que envolvem MMC e isso me dá fadiga. Melhor que somar essas frações seria usar uma boa aproximação para essa soma, que eu conheço bem, é a série harmônica \sum_k \frac{1}{k}. Como você deve se lembrar de sua infância, essa soma de 0 a n pode ser aproximada, para grandes valores de n, por \ln n . Assim, a soma de n até N-1 deve ser \ln (N-1)-\ln(n) = \ln\left(\frac{N-1}{n}\right). Como usamos a hipótese de valores grandes de N, podemos escrever isso como \ln\left(\frac{N}{n}\right). Assim, devemos parar de pular candidatos quando encontramos o melhor a partir do n-ésimo, sendo n o número tal que \ln\left(\frac{N}{n}\right)<1, ou seja, n = \frac{N}{e}, onde e é o número de Euler e=2,71828\ldots .

Percebemos que essa conta nos diz para pularmos os primeiros \frac{N}{e} pretendentes e, após esses, ficar com o primeiro que for melhor que todos os anteriores. Note que \frac{1}{e}\approx 0.37. Em outras palavras, a estratégia optimal para encontrar o melhor pretendente da balada para levar para casa é a seguinte: estabeleça um número de pessoas para pegar na balada. Rejeite necessariamente os primeiros 37% delas. Cole na primeira pessoa que aparecer que for melhor que todas as anteriores e leve esta para casa.

O mesmo vale para namorados ou namoradas durante sua juventude. Se quer maximizar suas chances de casar com a melhor opção, estabeleça uma estimativa do número de pessoas com que vai namorar durante sua vida, termine com os primeiros 37% e case com a primeira que aparecer que for melhor que todas as anteriores.

Vamos ver quão bem isso funciona. Para isso, vamos contar a história de Pedro.

Pedro é um garoto que costuma ir a três baladas diferentes. Ele está atrás de garotas, e quer levar a melhor delas para casa. As baladas são diferentes, e a qualidade dos frequentadores tem uma distribuição variada para cada balada. Vejamos quais são elas, usando descrições do site cidadedesaopaulo.com:

  1.  A The History, localizada na Vila Olímpia, tem piso que muda de cor e agrada tanto àqueles que já curtiram os hits dos tempos da brilhantina quanto às novas gerações. Possui um público pouco variado e previsível, a qualidade dos frequentadores será dada por uma distribuição gaussiana.
  2. Localizado no Baixo Augusta, o Beco 203 é reduto dos moderninhos e alternativos que curtem um rock mais soft e festas em que o som é tocado através de fones de ouvido. Atraindo um público mais variado, a distribuição da qualidade de seus frequentadores será dada pela distribuição uniforme.
  3. A Lab, localizada na Rua Augusta, possui em sua programação dias dedicados à música eletrônica. Com um público ligeiramente variado, mas não muito, a qualidade de seus frequentadores está mais concentrada nas piores notas que nas melhores e será modelada pela distribuição exponencial.

Pedro é uma máquina e se dispõe inicialmente a pegar 100 garotas. Ele vai vezes o suficiente às baladas para poder testar diferentes estratégias, e está disposto a tentar todas as possibilidades. A experiência é a seguinte: um dia ele leva a primeira que encontrar para casa. No dia seguinte, ele rejeita a primeira e leva a primeira melhor que as anteriores para casa. Em seguida, rejeita as duas primeiras e leva a primeira melhor que as anteriores que encontrar para casa. Fazendo isso até a centésima vezes o suficiente, ele consegue estimar a taxa de sucesso de cada estratégia. Uma noite é bem sucedida se a que ele levou para casa era a melhor dentre as 100 possíveis. São bastantes opções, vejamos qual a taxa de sucesso de cada uma das estratégias.

top_na_baladaÉ facil acreditar que o valor ideal para a estratégia é 37, ou seja, rejeitar os primeiros 37% e aceitar a primeira opção melhor que todas as anteriores. Note como esse valor independe de como a qualidade das pretendentes está distribuída, seja uniforme ou extremamente concentrada em torno da média, a eficácia de cada estratégia é a mesma.

Falando um pouco mais sério, esse pequeno problema estatístico revela uma matemática internalizada em diversas decisões em nosso cotidiano, a ideia de “assentar”, de escolher uma opção para ser a definitiva. Quando você é jovem, seus namoros são em média curtos, explosivos, cheios de emoções e problemas, a idade vai trazendo mais estabilidade e em um ponto da vida você encontra aquela que acha ser a pessoa certa. Você experimentou o suficiente para identificar uma pessoa melhor que as anteriores e entender que a melhor estratégia é juntar os chinelos com esta; porque, conhecendo as alternativas, você prefere não arriscar e entende que é pouco provável encontrar algo tão melhor nas futuras opções. Casamento é sobre amor, sobre almas gêmeas, some encontrar a pessoa prometida e amada; mas quando você começa a beirar os trinta anos a realidade bate na porta e a estatística, aliada a sua experiência, fala mais alto.

E se você me perguntar se sigo essa estratégia, não vou poder responder. O modelo tem várias hipóteses, várias delas são boas, a maior parte se aplica a minha situação, mas um grande valor de N, certamente, não é o caso.

A matemática das massas

Geek

A quantidade de dinheiro envolvida em eventos esportivos sempre me assombrou. Ignorando a massa de recursos investida da estrutura e preparação de tais eventos, os prêmios em dinheiro aos que conseguem correr mais rápido, chutar mais certeiro ou apostar dinheiro de forma mais inteligente estão na casa dos milhões. A Forbes faz uma lista anual, sendo o décimo colocado o vencedor de quatro milhões de dólares. Essa lista, no entanto, está desatualizada; é preciso colocar um novo candidato: DotA, um jogo eletrônico, oferece em julho um prêmio de 5 milhões de dólares ao primeiro colocado, com 10 milhões ao todo a serem distribuídos aos primeiros lugares. Como é possível um videogame superar Cricket nessa lista? Ou, ainda, como é possível cada integrante do time vencedor de DotA receber mais que os jogadores de baseball vencedores da World Series? Esse prêmio, como muitos financiamentos dos últimos dois anos, não vem de uma única pessoa ou empresa; ele é resultado de um longo e extremamente bem elaborado crowdfunding, um projeto financiado por milhões de indivíduos.

Deixo de fora da discussão o aspecto econômico ou preditivo desse fenômeno, não me arrisco a escrever um daqueles artigos de “10 maneiras de fazer seu crowdfunding dar certo!”. Gosto dos gráficos e da evolução desses financiamentos. Vejamos alguns:

1. Stop/Eject, projeto de fotografia de Neil Oseman

stop-eject2. Star Citizen

starcitizenIgnorem a linha vermelha, a azul é o financiamento!

3. Dota 2, The International 2014

dota2_20144. Dota 2, The International 2013

dota2_20135. Robot Dragonfly

robot_dragonflyEsses gráficos são bem diferentes e a esperança de explicar tudo com o mesmo modelo parece vã. Vou tentar construir um modelo matemático suficientemente simples para explicar a forma desses gráficos, e discutir os problemas do modelo. Vamos usar a técnica da teoria de cordas, criar uma teoria com tantos parâmetros livres que podemos plotar um coelhinho nos dados se quisermos.

Antes de continuar, precisamos combinar uma coisa. Todo modelo está errado, todo modelo é imperfeito e todo modelo é uma compromisso entre simplicidade e exatidão. Eu certamente deixarei de levar vários aspectos desse complicado fenômeno social em conta, e o trabalho do físico é exatamente esse: criar um modelo suficientemente simples para ser tratado e que considere os aspectos fundamentais do fenômeno.

O modelo que escolho para descrever crowdfunding é o modelo de Ising a temperatura nula. O nome é pomposo, mas o modelo é simples, levando em conta tanto a publicidade emitida pela fonte central do crowdfunding como a influência de seus amiguinhos para você dar ou não dinheiro ao projeto.

Nesse modelo, vamos construir uma rede quadrada de indivíduos, representando a sociedade alvo do crowdfunding. Cada pessoa é afetada por seus quatro vizinhos, seus amigos, da seguinte forma:

Cada indivíduo i possui uma vontade de compra, um hype, representado pela letra h_i. Representamos cada indivíduo com uma coordenada \sigma_i, que vale zero se ele não contribuiu e 1 se contribuiu. Em meu modelo, se o hype é positivo, a pessoa contribui com o projeto. O hype é a soma de três fatores:

  • Marketing da empresa e vantagens do produto, representados pela letra B.
  • Influência dos amigos, representada pela letra \sigma_i.
  • Resistência pessoal à compra, representada pela letra R_i.

Assim, o hype sentido por cada pessoa será

 h_i = \sum_{i\sim j} \sigma_j +B ? R_i,

onde i\sim j significa “i é vizinho de j”.

O raciocínio é o seguinte. Cada pessoa apresenta uma resistência R_i, uma variável aleatória tirada de alguma distribuição. A empresa aplica um “campo de marketing” constante em todos, aumentando ligeiramente o hype. Algumas pessoas possuem o R_i baixo, então contribuem com o projeto com pouco marketing. Essas pessoas influenciam as que estão a sua volta, que aumentam seu hype contribuindo com o projeto. Se a soma do marketing B com a influência dos amigos for maior que a resistência R_i à compra, ele é mais um que contribui com o projeto.

Esse tipo de cálculo é muito difícil de fazer na mão, melhor deixar a computadores. Vamos ver o que acontece em cada iteração desse sistema. Tomemos 10.000 voluntários em uma rede 100×100. Começamos com uma distribuição de rejeição uniforme entre 0 e 5. Coloquemos um marketing inicial de 0.25. Com isso, aproximadamente 5% dos indivíduos vão contribuir com o projeto apenas com o marketing inicial. Após esse surto inicial, outros serão convencidos pela presença de seus vizinhos. O resultado é o seguinte

crowdfoundingPercebemos um crescimento inicial elevado seguido de saturação, o que é esperado. Você convence os amigos que pode até sobrarem apenas aqueles cuja rejeição é maior que o marketing aliado à influência dos amigos. Para conquistas mais adeptos, é necessário melhorar o produto ou o marketing. Vejam gráficos 3 e 5. Ambos representam drasticamente uma quebra no padrão, algo aconteceu nesses projetos. No primeiro, o campeonato de Dota, houve uma mudança na recompensa dada aos que contribuíram; em nosso modelo, isso significa um aumento de B. No Dragonfly houve uma divulgação em um jornal de grande porte, o que também é representado por um aumento de B. Vejamos o que acontece no gráfico anterior quando aplicamos B=0.25 até o instante 20 e passamos para B=0.28, um pouquinho mais elevado, após 20.

dota_2E fico feliz, porque o modelo parece funcionar.

Como explicar os outros gráficos? Noto que essa estrutura de crescimento com saturação aparece em todos os exemplos, pequenos acréscimos no valor de B são capazes de explicar as variadas curvas. Em outras palavras, com boa vontade podemos explicar todos os exemplos como “corcundas” e “saltinhos”; representados pela figura anterior.

E que resultados analíticos podemos extrair desse modelo? Infelizmente poucos, o modelo de Ising com entradas aleatórias é um monstro do ponto de vista matemático, algo perto do que chamamos de vidros de spin. Esse é um assunto sempre quente na física estatística, a quantidade de coisa para fazer é alta e a dificuldade dos problemas torna muitos problemas fáceis de explicar quase impossíveis de se resolver.

Percebemos uma saturação, queremos calcular o valor dessa saturação. Infelizmente essa resposta não é simples, veja o que acontece quando eu rodo meu código várias vezes, com as mesmas variáveis do primeiro gráfico.

crowdfunding_2Deu para perceber que a própria saturação é uma variável aleatória. A razão dessa grande diferença na saturação de contribuintes com os exatos mesmos parâmetros tem origem geométrica. Como eu atribuo uma rejeição aleatória uniforme nos indivíduos, eu corro o risco de criar “ilhas de rejeição”, regiões na grade 100×100 cercada por gente que não contribuiria com o projeto por nada nesse mundo. Essas pessoas, se unidas, podem impedir que indivíduos que com apenas um ou dois amigos entrariam na dança, mas, cercados de negatividade, decidem não o fazer.

É possível ao menos saber a média dessa variável? Honestamente, não sei, defiro a alguém que saiba mais de vidros de spin, não é minha área. Tentei uma abordagem de campo médio, mas minha resposta é quase o dobro do que acho numericamente, o que não de todo inesperado. A abordagem de campo médio é equivalente a considerar todo mundo conectado a todo mundo, enquanto aqui cada um é conectado a quatro. No campo médio eu driblo os problemas geométricos, as ilhas de rejeição, e percebo que elas são fundamentais para explicar os resultados.

Não tenho pretensões preditivas com esse modelo, foi só uma diversão de final de semana. Precisava colocar algum conteúdo desde que eu tomei férias após o último post sobre política, aquelas animações foram duras e a recepção de vocês fez valer a pena. Não sei se continuarei postando sobre política, posto o que achar interessante, talvez as eleições me animem. Por enquanto vou criando modelos para explicar gráficos bonitos, preenchendo com isso meus finais de semana. E, claro, com Dota.

Na saída da Peugeot

Geek

Certa vez, um amigo me contava de sua saída do trabalho, na sede da Peugeot. Todo dia, ele era confrontado com a escolha entre dois ônibus para chegar a seu destino, cada um saindo de um ponto diferente de sua empresa, mas ambos passando por sua casa. O primeiro, mais moderno, confortável, equipado e vazio, passava uma vez a cada quinze minutos. O segundo, mais rampeiro e cheio, passava a cada cinco minutos. No dilema entre conforto e pressa, meu amigo estabeleceu um critério: olharia o ponto do ônibus moderno e, se já houvesse alguém esperando, julgaria que valia a pena esperar, pois um tempo razoável já haveria se passado. Se não houvesse ninguém, voltaria nos sacolejos do outro ônibus.

Ao comentar seu critério com um colega de profissão, foi-lhe dito que era absurdo, pois a pessoa poderia ter acabado de chegar, que esse critério era o mesmo que nada. Ele propôs o problema a nosso grupo de amigos, e eu instintivamente achei um bom critério, se não pelo bom senso da explicação, por um instinto físico de considerar que haver uma pessoa representava ganho de informação, como se a entropia tivesse diminuído em relação à situação “eu não sei nada sobre o ônibus”, que é o caso original. Mas sem falar de entropia ou o que o valha, eu precisava provar meu ponto, e precisava conversar um pouco sobre como pessoas esperam um ônibus.

Esse post deveria ser simples e rápido, acabou saindo do controle, peço desculpas antecipadas pelo malabarismo de probabilidades, assuntos e variáveis, não consegui fazer mais simples; juro que tentei.

Imaginemos um ponto de ônibus ideal em que passa um ônibus a cada T minutos. No caso de meu amigo, T=15 minutos. Suporei que a chance de um passageiro chegar ao ponto para esperar é sempre a mesma em todos os instantes durante esse tempo T, ou seja, estou desconsiderando efeitos que possam aumentar ou diminuir drasticamente a chegada de pessoas durante a espera de um ônibus, esse modelo não funciona bem para as 18h da empresa. Suponha que, a cada leva, o ônibus recebe em média \lambda pessoas. Não sei os valores para o caso de meu amigo, mas eu noto que esse número é importante. Se o ônibus recebe a cada quinze minutos em média 10 pessoas, não é trivial saber exatamente o que haver uma pessoa esperando quer dizer; contudo, se ele recebe 50, haver apenas uma indica que ele acabou de passar.

Então temos que a cada T minutos, em média, juntam-se \lambda pessoas no ponto. Suponho que o fluxo de pessoas para o ponto seja constante, e me pergunto: qual a chance do ônibus receber \lambda-1 pessoas? Ou \lambda+1? Ou \lambda/2? Tais perguntas não são simples, mas são todas respondidas pelo que chamamos de distribuição de Poisson.

Tenho um intervalo de T minutos entre um ônibus e outro, sei que as pessoas podem chegar a qualquer momento durante esses minutos. Minha única informação é que a média de pessoas que chegam ao final de T minutos é \lambda. Para estudar essa estatística, vou usar um truque matemático para modelizar a situação como um processo binomial. O truque é dividir meu intervalo de 15 minutos em 900 intervalos de um segundo. A escolha do segundo é para fins didáticos, o correto seria escolher dividir 15 minutos no maior número de intervalos possíveis, cada um com uma duração cada vez menor. Vou supor que o ônibus encontra, em média, \lambda=20 pessoas no ponto. Assim, posso dizer que a chance de uma pessoa chegar em um dado segundo é 20/900. A razão para essa divisão em 900 segundos é que essa afirmação só é possível se duas pessoas não puderem chegar no exato mesmo segundo. Se eu tivesse escolhido dividir meu intervalo em minutos, não faria sentido dizer que a chance de uma pessoa chegar em um minuto é 20/15, essa chance é maior que um! Seria como cometer o erro de dizer que, se a chance de tirar cara ao tirar uma moeda é de 50%, então em três lançamentos a chance é de 150%!

Essa divisão nos intervalos bem pequenos serve para eu transformar a chegada de pessoas no ônibus em um processo de zeros e uns. Cada segundo receberá um número, 0 se nenhuma pessoa chegou nesse segundo, 1 se alguém chegou nesse segundo. A cada segundo, portanto, estará associada uma probabilidade p de chegar uma pessoa. O que sabemos é que, se o número de segundos é N, então Np=\lambda, o número médio de pessoas será a probabilidade de uma chegar em um segundo vezes o número total de segundos. Isso só é possível porque a chegadas das pessoas não possui correlação e porque ninguém pode chegar no mesmo segundo que outra pessoa.

Para calcular a probabilidade, ao final de N segundos, de se obter k pessoas no ponto, preciso pensar que aqueles N segundos ganharam um número k de uns e um número N-k de zeros. Ou seja, se quero saber a chance de 10 pessoas chegarem no ponto no final de 900 segundos, terei que dentre esses 900 segundos 10 deles receberam pessoas e 890 não receberam. A probabilidade de 10 segundos específicos receberem pessoas é de p^{10}(1-p)^{890}, pois aqueles dez devem receber e os 890 restantes devem não receber pessoas. Mas como não sei quais segundos receberam, devo considerar todas as combinações possíveis de segundos que receberam essas pessoas, devo multiplicar esse valor por \binom{900}{10}. A probabilidade p pode ser determinada dividindo o número médio de pessoas 20 pelos 900 segundos, e teremos a probabilidade de encontrar 10 pessoas no ponto de ônibus: P(k=10)=\binom{900}{10}\left(2/90\right)^{10}\left(1-2/90\right)^{890}, um valor um pouco maior que 0,55%.

Esse raciocínio, contudo, tem problemas. Em primeiro lugar, eu deveria, por honestidade intelectual, dividir o intervalo em bem mais que 900 segundos, deveria usar 900.000 milissegundos para garantir que ninguém mesmo chegará no mesmo intervalo e poder usar essas contas com segurança. Mas se os cálculos já ficaram feios com 900, afinal, o binomial envolve fatoriais desse valor, imagine fazer contas com 900.000 fatorial! Esse caminho é impraticável, e por isso Simeon-Denis Poisson vem a nosso socorro. Através de uma aproximação malandra1, Poisson nos diz que:

 \binom{N}{k}\left(p\right)^{k}\left(1-p\right)^{N-k}\underbrace{\longrightarrow}_{N\to \infty} \frac{(Np)^k}{k!}e^{-Np}

O que é muito oportuno, porque sabemos que Np é a média de pessoas que está no ponto após os quinze minutos, ela é igual a \lambda! Essa aproximação é cada vez melhor se o número de divisões do intervalo de tempo é maior, e eu quero mesmo é que isso seja grande, quanto maior for, menor é a chance de duas pessoas chegarem no mesmo intervalo de tempo. Então eu mando N logo para infinito e digo que que a probabilidade de se encontrar k pessoas no ponto de ônibus depois de quinze minutos (lembro que T=15 nesse caso) é:

P(k|T)=\frac{\lambda^k}{k!}e^{-\lambda},

onde \lambda é a média de pessoas que encontro no ponto de ônibus no final dos quinze minutos de espera, essa é conhecida como a distribuição de Poisson. Saberei, com isso, a probabilidade de encontrar um número k de pessoas ao final de cada espera de 15 minutos:

poisson_dist_20

Isso ainda não resolve meu problema, mas ajuda bastante, como veremos. Sei qual a probabilidade de encontrar k pessoas após 15 minutos, pergunto então: qual a probabilidade de encontrar k pessoas após t minutos? Se com os 15 minutos bastou usar a distribuição de Poisson com parâmetro igual à média de pessoas que chegam em 15 minutos, com os t minutos bastaria usar a mesma distribuição, trocando a média dos 15 pela média dos t. Como a taxa de chegada dos passageiros no ponto é constante, a média evolui linearmente de 0 a \lambda, ou seja, a média \lambda(t) de passageiros no ponto em um tempo t é \frac{\lambda}{T}t=\mu t, onde \mu é a taxa de chegada das pessoas. A probabilidade de encontrar k pessoas no ponto no instante t será:

 P(k|t) = \frac{(\mu.t)^k}{k!}e^{-\mu t}

Essa distribuição dependente do tempo é conhecida como processo de Poisson, e descreve muito bem a chegada de pessoas em um ponto de ônibus. Temos agora exatamente a probabilidade de encontrar um número qualquer de pessoas em um instante qualquer de espera, queremos saber, então, se aquele critério de meu amigo presta a alguma coisa. Para isso, precisamos conversar um pouco sobre probabilidade condicional, e sobre como calcular probabilidades quando já sabemos algo sobre o processo.

O que quero é a chance de terem se passado t minutos uma vez que há k pessoas no ponto. Vou chamar essa chance de P(t|k). O que tenho até agora é a probabilidade de encontrar k pessoas uma vez que se passaram t minutos, ou seja, tenho P(k|t). Essas probabilidades parecem similares, mas possuem sentidos completamente diferentes; uma é a chance de chover se há nuvens, outra é a chance de haver nuvens se chove. Se quero de uma obter a outra, preciso usar o teorema de Bayes:

P(t|k) = \frac{P(k|t) P(t)}{P(k)},

onde P(k) é a probabilidade de encontrar k pessoas no ponto sem qualquer informação sobre o horário, e P(t) é a probabilidade de estarmos no instante t.

Há um problema grave na definição de P(t), pois a chance real de estarmos no instante t é nula, porque t é um número real e a chance de estarmos exatamente às 13h43m10s325ms901μs… é zero, não é possível atribuir a probabilidade de se obter um número real no meio da reta real. Mas podemos pensar na chance de estar entre dois horários, entre o primeiro e o segundo minuto, por exemplo. E essa chance, naturalmente é igual para todos os minutos, não temos razão para, chegando ao ponto de ônibus, supor que ele passou faz 3 minutos, ou 5, sem olhar para os passageiros que estão no ponto. Meu amigo, aliás, quer saber se há alguma diferença entre P(t|k) (probabilidade de estar em t sabendo k) e P(t) (probabilidade de estar em t sem saber nada sobre k). Se o tempo total possível de espera é de T, a chance de estarmos em um intervalo de tempo de tamanho \Delta t é igual para todo intervalo: \frac{\Delta t}{T}. Para o propósito de nosso problema, vale a pena pegar intervalos muito pequenos de tempo. Ao escrevermos P(t) queremos, na verdade, dizer “probabilidade de estar em um intervalo de tempo dt muito pequeno centrado em t”, ou seja, P(t)=\frac{dt}{T}.

Calcular P(k), por outro lado, não é tão simples. Devemos pegar a chance de encontrar k pessoas no ponto no instante t ( P(k|T) ), multiplicar pela chance de estar em t ( P(t) ) e somar em todos os t’s possíveis. Essa é a única maneira de calcular a chance de ter k sem saber nada sobre t, é somar a chance de estar em qualquer t possível. Matematicamente, isso é fazer a integral: \int_0^T P(k|T)\frac{dt}{T}. Trabalhando um pouco, chegamos a:

 \int_0^T \frac{(\mu.t)^k}{k!}e^{-\mu t}\frac{dt}{T} = 1-\frac{\Gamma(1+k,T\mu)}{T\mu k!}

Chamamos essa função estranha do lado direito de função Gamma incompleta, ela é apenas um jeito elegante de escrever \Gamma(s,x) = \int_x^{\infty} t^{s-1}\,e^{-t}\,{\rm d}t, uma integral que não sabemos fazer, mas que numericamente sai com tranquilidade.

Depois de muito malabarismo, chegamos à resposta mais completa ao dilema de meu amigo. Dadas as seguintes hipóteses:

  • O ônibus passa uma vez a cada T minutos.
  • O ônibus encontra, a cada vez, em média, \lambda pessoas esperando no ponto.
  • A taxa de chegada de pessoas no ponto de ônibus é constante, igual a \mu=\lambda/T.
  • Ninguém corre para pegar o ônibus (hipótese que provavelmente torna o modelo inútil).

Então a densidade de probabilidade P(t|k) é:

 P(t|k) =\frac{P(k|t)P(t)}{P(k)}=\frac{\frac{(\mu.t)^k}{k!}e^{-\mu t}\frac{1}{T}}{1-\frac{\Gamma(1+k,T\mu)}{T\mu k!}},

Essa é a densidade de probabilidade. Para descobrir qual a chance de que o último ônibus tenha passado há \tau minutos, você deve integrar essa expressão de 0 a \tau. Felizmente temos o Mathematica para isso. Assim, ao encontrar k pessoas no ponto, a chance de que o ônibus tenha passado há pelo menos \tau minutos é:

 P(\tau)=\int_0^\tau P(t|k)dt=\int_0^\tau \frac{P(k|t)P(t)}{P(k)}=\frac{\int_0^\tau\frac{(\mu.t)^k}{k!}e^{-\mu t}\frac{dt}{T}}{1-\frac{\Gamma(1+k,T\mu)}{T\mu k!}}=\frac{\Gamma(1+k,\tau\mu)-\Gamma(1+k,T\mu)}{1-\Gamma(1+k,T\mu)}

Tomemos valores realistas. Sabemos que T=15. Vamos supor que a cada chegada, em média, o ônibus encontra N=6 pessoas. Para que meu amigo fique feliz com o post, apresento o resultado para encontrando duas pessoas (k=2), uma pessoa (k=1), não vendo ninguém no ponto (k=0) e não sabendo absolutamente nada sobre o ponto (k=?), essa é a probabilidade de que o ônibus tenha passado há pelo menos \tau minutos:

poisson_bus_stopÉ claro que a chance é alta de que o ônibus tenha passado há ao menos um minuto, bem como é bem difícil que ele tenha passado há 14 minutos ou mais. Com isso, fechamos o problema. Percebemos alguns aspectos importantes do critério de meu amigo. Primeiro, ele não é equivalente a não saber nada sobre o ponto, as distribuições são bem diferentes. Segundo, observar uma única pessoa, sendo a média de embarque seis, indica que é mais provável que o ônibus tenha passado faz quatro minutos ou menos, você conta ainda com uma espera de uns bons onze minutos. Pelo número de pessoas que encontra no ponto, é capaz de, negociando com sua espera, decidir se se rende ao desconforto ou se volta paciente e confortavelmente para sua casa.

  1. conhecida como aproximação de Stirling []