Arquivo da tag: Sistemas Complexos

Posts sobre sistemas complexos e complexidade em física.

Artur Ávila, o domador do caos

Rookie

A cada quatro anos, no congresso internacional de matemática, são anunciados os ganhadores do que é considerado o maior prêmio da matemática, a medalha Fields. É um prêmio especial, entregue só a matemáticos de menos de quarenta anos, extremamente prestigioso e justo. Esse ano houve algo diferente, pois um dos ganhadores, Artur Ávila, é brasileiro.

Somos perto de duzentos milhões de habitantes, não temos um prêmio nobel de ciência. As razões são muitas e não cabem aqui, nem as conheço todas e o debate é bom e interessante, mas fica para outro dia. No caso da física, eu asseguro; se algum brasileiro ganhar um nobel no curto prazo, pouco ou nada de sua pesquisa terá sido no Brasil. São comuns casos de cientistas cuja formação é toda feita em outro país e, ao receber um prêmio, seu país natal comemora como final de Copa do Mundo. Não sou contra, é uma pequena hipocrisia que pode gerar um interesse na área e pode estimular talentos mais jovens, mas não é realidade. Com Artur Ávila, no entanto, não é o caso; Ávila é brasileiro com formação brasileira que trabalha no Brasil. Isso diz muito sobre a matemática no Brasil, sobre o IMPA (instituto em que o Ávila trabalha) e merece todo o elogio e admiração que esse pobre blog pode emitir.

Mas você não veio aqui para ler sobre o Ávila, isso você vai encontrar na Folha, no G1 ou um portal de notícias. Vou tentar explicar um pouco a base da pesquisa do Ávila, que é a teoria de sistemas dinâmicos. Não se anime, ainda com esse post você não vai conseguir ler um artigo do Ávila, eu mesmo os leio como alguém que acabou de fazer seu primeiro semestre de curso de inglês lê Shakespeare, devagar, sofrido e consultando o dicionário a cada linha.

Não que seu texto seja arcano ou confuso, pelo contrário, matemática boa é reconhecida pela clareza e precisão. O problema é falta de base e de hábito. Matemática é uma área do conhecimento extremamente vertical, temos que passar pelo térreo, primeiro, segundo e todos os andares seguintes para chegarmos ao topo. O que vou apresentar aqui é o térreo dos sistemas dinâmicos, e talvez uma parte da área de serviço.

Um sistema dinâmico é uma regra que associa estados passados a estados futuros. Lembra-se daqueles desafios lógicos em que você tem uma sequência de números e tem que descobrir a regra que os gera, para descobrir o próximo? Algo como 1, 1, 2, 3, 5 e você deve adivinhar que o próximo é 8. Neste caso, temos a regra $x_{n+1} = x_{n}+x_{n-1}$, chamada regra de Fibonacci. Uma regra associando estados passados (o $x_{n}$ e o $x_{n-1}$, que são o estado anterior e o antes do anterior) a estados futuros ($x_{n+1}$), pois podemos continuar para obter todos os seguintes. Claro que não estamos restritos a isso, podemos definir muitas regras e até estabelecer regras em espaços que não são discretos e bonitinhos como o do exemplo.

Com isso, dá para perceber que muita coisa é um sistema dinâmico. A grande exigência é que a regra deve ser determinística, ou seja, começando em um ponto o sistema deve caminhar em uma direção específica. Se voltar ao ponto de partida, o sistema deve percorrer percorrer o mesmo caminho, ou efetuar uma órbita, como gostamos de chamar.

Ávila se aprofundou em fenômenos que envolvem fractalidade, caos e outras coisas um pouco mais complicadas. Um exemplo interessante dos dois primeiros em sistemas dinâmicos é a equação logística, algo de definição bem simples e resultados complicados. Assim como nós antes tínhamos uma sequência definida com a regra de Fibonacci, vamos pensar em outra regra: $x_{n+1} = r.x_n(1-x_n)$, onde $r$ é um número entre 1 e 4. Parece simples, e nem parece muito diferente da outra, mas dependendo do valor de $r$ você vai descobrir que essa a sequência gerada sai do controle rapidamente.

Vejamos o que acontece quando começamos no valor $x_0=0,\! 1$ e com $r=1,\! 2$. Primeiro calculamos o próximo passo: $x_1 = r.x_0(1-x_0)$ $=1,\! 2.0,\! 1(1-0,\! 1) = 0,\! 108$. Para calcular o próximo passo, continuamos com a regra: $x_2=r.x_1(1-x_1)$ $=1,\! 2.0,\! 108(1-0,\! 108)= 0,\! 1156032$. Não vou escrever linha por linha, mas um gráfico revela o futuro dessa conta, ela converge para um valor específico.

avila_1Com esse gráfico você pode achar que esse sistema é tranquilo, que outros valores vão também convergir, que tudo caminha para um valor bonito e estável. Nada podia estar mais longe da verdade. Veja o que acontece quando trocamos $r$ por $3,\! 1$.

avila_2Com esse valor de $r$, o sistema não converge para um valor, mas para dois valores. Esse comportamento não é lá muito normal, mas piora, veja o que acontece quando colocamos $r=3,\! 5$.

avila_3Nesse caso, o sistema converge para quatro valores. Conforme aumentamos o valor de $r$, o sistema fica cada vez mais instável e converge para cada vez mais valores diferentes. Chega um ponto que podemos nos perguntar: converge mesmo? Não seriam tantos valores que a própria noção de convergência já perde o sentido?

Esse sistema dinâmico converge para um valor apenas quando $r$ está entre 1 e 3. Para um $r$ entre 3 e 3,45, ele converge para dois. Quando $r$ está entre 3,45 e 3,544, o valor de $x_n$ pipoca entre quatro possibilidades e entre 3.54 e 3.56 teremos oito possibilidades. Não apenas esses valores aumentam exponencialmente, o intervalo de $r$ em que eles acontecem fica cada vez menor. Refletido a respeito, o primeiro intervalo é quase cinco vezes maior que o segundo, enquanto o segundo também é quase cinco vezes maior que o terceiro. Essa relação entre os intervalos, se fizermos uma sequência com ela, converge para um valor, chamado constante de Feigenbaum. Quando chegamos a $r=3,7$, na verdade bem antes disso, torna-se completamente impossível prever os valores desses sistema. O único jeito de obter o valor na centésima iteração é calcular todas as noventa e nove anteriores. Veja como fica nosso gráfico para $r=3,7$.

avila_4E talvez nisso surja uma das perguntas mais interessantes de caos, fractalidade e sistemas dinâmicos: como pode uma regra tão simples gerar um resultado tão complicado e imprevisível? Como pode tanta complexidade emergir de uma única lei? O caráter matemático dessas perguntas é profundo, e as implicações são maiores do que imaginamos olhando pela primeira vez.

Escolhi esse exemplo porque ele é muito próximo do trabalho de alguns físicos, complexidade é algo onipresente na natureza e na realidade. Não gosto de partir para o esoterismo, mas não são poucos os cientistas que estudam sistemas caóticos, como a equação logística, para tentar responder questões sobre livre-arbítrio e consciência. O argumento de “se somos apenas átomos, está tudo definido e não temos escolha” não precisa nem da mecânica quântica para ser extinto, a equação logística cuida dele. Fenômenos simples podem gerar complexidade o suficiente para que a previsibilidade seja destruída; determinístico não é determinado e, como vemos acima, para todos os efeitos de medida, se a equação logística fosse uma pessoa ela pareceria ter bastante livre arbítrio sobre o próximo valor da sequência.

Ávila fez contribuições fundamentais para o estudo de sistemas dinâmicos reais e complexos, uni e multidimensionais, discretos e contínuos. Nos sistemas dinâmicos unidimensionais, Ávila praticamente “terminou” o assunto, após seu último artigo no tema poderiam passar os créditos e baixar a cortina. Estudando profundamente o caráter matemático de objetos pontudos como a equação logística, Ávila nos aproximou um pouco mais do que há por detrás da cortina da complexidade. Domando o caos, Ávila mereceu e ganhou o mais alto prêmio que um cientista brasileiro já conquistou. Que abra caminho para os próximos, que seja o primeiro de muitos, que, como na equação logística, o intervalo entre a primeira dessas e a próxima seja bem menor que o tempo que a primeira demorou para chegar.

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.

Epidemias, parte II

Hardcore

Em um post anterior, comentei sobre a evolução de epidemias em seres humanos e sobre a noção de threshold, um valor mínimo de eficácia da doença para que ela tenha algum futuro. Hoje vamos falar de vírus de internet e sobre como sua propagação ocorre de maneira diferente, porque sites e seres humanos não são a mesma coisa. Se o post anterior já era hardcore, esse não deixa barato, em alguns sentidos é mais intrincado que o primeiro, mas sua conclusão é bonita. Coragem, respire e me acompanhe.

O sistema descrito no post anterior não é um bom modelo para a internet. Os sites possuem um fenômeno conhecido como preferential attachment, ou, como no Brasil chamamos, o rico cada vez fica mais rico e o pobre, mais pobre. Um novo usuário tende a acessar sites que são mais famosos quando entra no sistema. Claro que há diversos fatores, desde idade do site à sua capacidade de inovação, mas em um modelo simples podemos imaginar que um usuário que deseja criar uma rede social tem uma tendência maior a abrir uma conta no Facebook a uma no Uolkut (que acabo de ficar sabendo que foi desligado esse mês, paciência, segue como exemplo).

Podemos representar isso em um grafo como no post anterior. Um modelo simples de preferential attachment é conhecido como Barabási-Albert, consiste em começar com um número de pontos (digamos 2) e, a cada ponto inserido no grafo, esse ponto fará um número de conexões (digamos também 2) com os pontos já existentes. Isso representa um número de sites que possuem links entre si e um novo entrando na roda, formando links com os já existentes. Mas em um momento haverá mais pontos disponíveis que links a serem feitos pelos novos ingressantes, então um novo membro deve escolher os pontos com que quer formar links, e essa escolha se dará de forma aleatória, sendo a probabilidade de se conectar a um ponto proporcional ao número de links que o ponto já possui. Vamos supor um caso inicial de dois pontos, sem vínculos. O primeiro que entra deve fazer duas conexões, então ele escolhe os dois já existentes. O próximo a entrar terá que escolher dois dentre aqueles três: um possui duas conexões e outros dois possuem apenas uma, então a primeira conexão entra com probabilidade 1/2 no link com mais conexões e 1/4 nos outros. E a segunda será análoga, dependendo da que ele já escolheu (não pode formar duas conexões com o mesmo ponto). Represento um dos resultados possíveis desse modelo com um belo gif, tirado sem escrúpulos da Wikipédia.

Tentando repetir o raciocínio do primeiro post sobre epidemias, temos um problema na equação mestra, aquela que nos diz a evolução temporal da probabilidade. Não mais sabemos o número médio de contatos de cara ponto, não possuímos mais a relação $\langle r \rangle=2m$. Estamos vamos fazer por partes: escrevamos a equação mestra supondo que o ponto tem um número $k$ de contatos e depois eu faço uma soma ponderada disso tudo.

A chance de um ponto com que fazemos contato estar infectado depende de $\lambda$, vamos então o denotar $\Theta(\lambda)$. Nossa equação mestra, supondo um $k$ específico, nos dará a densidade de infectados supondo esse $k$ específico, ou seja, $\rho_k$. Ela será:

\[\partial_t\rho_k(t)=-\underbrace{\rho_k(t)}_{\text{cura}}+\lambda \underbrace{k(1-\rho_k(t))\Theta(\lambda)}_{\text{contato sadio-doente}}\]

Os que se interessam nos meandros das contas, escrevo a expressão de $\Theta$, que representa a chance de, estando em contato, está-lo com um infectado. Ela deixa de ser evidente, mas pode ser calculada da forma:

\[ \Theta(\lambda)=\sum_k\rho_k\overbrace{\frac{kP(k)}{\sum_ssP(s)}}^{\text{probabilidade de ter k}}\]

E depois, para achar a densidade total de infectados, basta somar de forma ponderada com $k$:

\[\rho(t)=\sum_k P(k)\rho_k(t)\]

É aqui que paro com a tortura das equações. Misturamos essas acima e chegamos a uma conclusão um pouco perturbadora sobre a densidade de persistência, aquela obtida igualando a sua derivada temporal a zero:

\[\rho\propto e^{-\frac{1}{m\lambda}}\]

Não encontramos nenhuma maneira de obter o que antes chamávamos de threshold, os vírus de internet não possuem uma eficácia mínima para funcionarem , eles se propagam e adquirem uma população constantemente infectada a qualquer taxa de infecção. Mando aqui o gráfico da densidade de persistência:

Ainda que temamos essa propagação sem threshold, podemos ficar tranquilos, o decaimento da densidade de persistência é exponencial para pequenas taxas de infecção e ela se torna rapidamente desprezível, como percebemos no gráfico. Ainda, esse modelo é capaz de explicar a propagação desenfreada de ameaças tidas como bem estúpidas, links evidentemente falsos e infecções cuja eficácia seria baixa ($\lambda$ baixo), não fosse o grande número de conexões dos infectados. Terminando esse exemplo, elogio a graça e simplicidade desse toy-model, capaz de explicar doenças, epidemias e talvez até aquele seu tio (ou tia) chato, aquele que na sua adolescência perguntava de suas namoradinhas, e agora manda tantos supostos vídeos exclusivos de celebridades nuas; todos conhecemos um desses, tendo, como teorema, que todos têm um tio chato. Se você não tem, cuidado, ele provavelmente é seu pai.

A pior forma de governo

Rookie

As eleições na França tiveram há pouco sua conclusão, com a vitória do socialista François Hollande, e logo as eleições americanas começarão. Eu conversava com um amigo francês a respeito, ele, em um não raro surto nacionalista, dizia ser raro encontrar um país com uma democracia tão funcional quanto a francesa, em que candidatos em igualdade de condições (mesmo tempo de propaganda eleitoral, por exemplo) são avaliados de forma justa e o escolhido é o favorito da população. Comparava esse sistema ao confuso método americano de eleições indiretas, que pode gerar aberrações estatísticas como a estranha eleição de Bush sem a maioria absoluta da população. Ainda, argumentei que o escrutínio francês não é perfeito, o método de eleição em dois turnos não é ideal. Ele perguntou qual seria, então; e a resposta é simples, e longe de intuitiva: nenhum método é justo.

Se Churchill disse que a democracia é a pior forma de governo, exceto todas as outras que já foram tentadas, o post de hoje é para convencê-los de que até em um caso bem simples a democracia não possui resposta fácil, a justiça nem sempre é evidente e uma eleição possui fatores que vão além de músicas contagiantes, propagandas elaboradas e discursos violentos.

Somos confrontados diversas vezes com situações em que uma eleição deve ser realizada, não damos a devida atenção ao método do escrutínio. Digo que não apenas ele amplifica ou ajuda um resultado, muitas vezes a forma de escrutínio determina o vencedor. Para não forçar meu argumento, vou listar os métodos mais tradicionais de escrutínio, todos baseados em sistemas existentes:

1º Método: eleições em um único turno. Inspirados em sistemas de democracia pequena, como a eleição para “chefe do grupo” ou para o diretório de estudantes de uma universidade, podemos apenas contar, em uma votação com uma opção apenas, quem tem mais votos e decidir que ele será o escolhido.

2º Método: eleições em dois turnos. Inspirados nas eleições francesas e brasileiras, podemos realizar uma primeira votação e, selecionados os dois melhores, podemos realizar um segundo turno e eleger vencedor o que obtiver então mais votos.

3º Método: atribuição de pontos. Inspirados nas eleições legislativas australianas, podemos atribuir pontos a suas preferências: 5 pontos ao favorito, 3 ao segundo favorito, 1 ao terceiro lugar e 0 ao que não querem de jeito nenhum. O candidato que ganhar mais pontos é eleito.

4º Método: contagem de confrontos. Inspirados nas eleições americanas, com um sistema um pouco diferente, podemos pensar em um sistema de “confronto” entre candidatos. Quantas vezes o A é preferido em relação ao B? E ao C? E ao D? Após todas essas comparações, ou confrontos, somamos o “placar” de cada candidato e o que tiver vencido mais confrontos é o eleito. Em outras palavras, é como simular todos os “segundos turnos” possíveis e eleger o candidato que vencer mais segundos turnos.

Todos esses métodos são usados em algum sistema democrático de comparação na vida real, não inventei nada. Ainda, digo a vocês que é impossível estabelecer um vencedor único, aliás, consigo situações em que é impossível encontrar um vencedor “justo” da eleição. Se você considera esses quatro métodos válidos, sigo contando a história de um país bem pequeno.

Apresento a vocês Pequenolândia, um país de dez habitantes que quer eleger seu presidente (não confundir com Pequenópolis, oficialmente cidade natal de Clark Kent). Quatro candidatos se apresentam, A, B, C e D. Cada cidadão possui para si uma ordem de prioridade na escolha dos candidatos, e eu apresento essa ordem em forma de tabela:

Eleitor 1 2 3 4 5 6 7 8 9 10
A A A A B B B C C D
D C D D C C C D D C
B D B B D D D B B B
C B C C A A A A A A

A constituição de Pequenolândia, contudo, não está escrita, eles precisam de um presidente para isso. Sem saber como realizar as votações, os habitantes de Pequenolândia se inspiram nas diferentes formas de classificação eleitoral pelo mundo, e, decididos a exercerem plenamente a democracia, realizam as eleições com os quatro métodos acima, e comparam resultados.

O primeiro método dá vitória ao A, preferido de quatro habitantes, vence os demais, cujas preferências são três, dois e um. O segundo método selecionaria o A e o B para um segundo turno, e podemos ver que o B vence o A na preferência dos eleitores que não votariam inicialmente neles, o que daria a vitória ao B em uma eleição a dois turnos.

Contando os pontos pelo terceiro método, teríamos o A com 20 pontos, o B com 21 pontos, o C com 25 pontos e o D com 24 pontos, sendo a vitória por pontos corridos claramente do candidato C. Se contarmos os confrontos, o A vence apenas 12 confrontos (4 vezes cada candidato), o B vence 15 (6 vezes o A, 6 vezes o C e 3 vezes o D), o C vence 16 (6 o A, 4 o B, 6 o D) e o candidato D vence 17 (6 o A, 7 o B e 4 o C) confrontos, sendo claro que a vitória pertence ao candidato D. Pequenolândia terá, como resultado de sua eleição, anarquia completa.

Esse pequeno exemplo ilustra como métodos reconhecidos e consagrados pelo uso na democracia não apenas geram resultados diferentes, eles determinam o vencedor. Cada método elegeu um candidato, e nenhum deles pode ser acusado de ser injusto, todos são usados em eleições, campeonatos e torneios.

Uma resposta otimista seria admitir que existe um método correto e justo, apenas que não é um desses que listei; mas os matemáticos já se encarregaram de arrasar esse otimismo com um sonoro não. O teorema da impossibilidade de Arrow afirma que quaisquer critérios justos que sejam escolhidos, com hipóteses matemáticas exatas de o que ele chama de justiça (todos os critérios acima satisfazem as hipóteses de Arrow), sempre é possível encontrar uma lista de preferências que eleja dois candidatos diferentes com métodos justos. De forma simplificada, nenhuma eleição é justa, Pequenolândia terá que escolher um método antes de escolher um presidente (diferentemente do Brasil em 1988). Em outras palavras, é impossível, de uma lista genérica de preferências, obter de forma inequívoca quem será o presidente.

Em um exemplo atual, e mais concreto, este artigo (agradecimentos a Guilherme Mazanti pelo link), infelizmente em francês, atesta um fato surpreendente. Nessas eleições francesas, o candidato François Bayrou, quinto colocado no primeiro turno, ganharia de qualquer oponente em um combate direito (4˚ método); se participasse, ele ganharia qualquer segundo turno! Ora, como pode um candidato preferido por toda a população a qualquer outra opção não apenas não ser o presidente, mas ser quinto lugar nas pesquisas? Eis um dos resultados impressionantes do teorema de Arrow, colocando em uma perspectiva diferente a afirmação de meu amigo, até que não deve ser tão difícil encontrar eleições mais justas que aquelas que não elegem o favorito da população frente a qualquer outra opção.

Ainda, quanto a meu amigo francês, ele pode ficar tranquilo. Diz-se que eleições justas são pleonasmo, pois se não fosse justa não seria eleição; Arrow nos garante, nada de pleonasmo, eleições justas são, na realidade, um paradoxo.

Propagating randomness

Hardcore

Ricardo: O post de hoje é em inglês, e de um convidado muito especial. Alexander Dobrinevski, autor do blog inordinatum.wordpress.com, é meu grande amigo bielo-russo que, após sua graduação na Universidade Ludwig-Maximilians de Munique, seguiu para dois anos de mestrado em estudos avançados em matemática na Universidade de Cambridge e deu-me o privilégio de sua companhia no Laboratório de Física Teórica da École Normale Supérieure, onde dividimos sala durante alguns meses de trabalho enquanto ele fazia seu doutorado e eu, o mestrado. Viciado em cafés, filmes não tão mainstream e transformadas de Laplace. O post de hoje é bem hardcore, vale aos especialistas da área, e a mim, que aprendi e aprendo bastante a cada vez que nos falamos.

Ricardo: This post will be in english, for we have a very special guest today. Alexander Dobrinevski, author of the blog inordinatum.wordpress.com, is a good friend of mine from Belarus. Having finished his graduation at LMU, he followed the Advanced Studies in Mathematics program from Cambridge University to end up his doctoral thesis at the École Normale, where I had the pleasure to share with him the office for a few months. He is addicted to coffee, exotic movies and Laplace transforms. Today’s post is also very hardcore, to the benefit of our dear specialist in the field, and to mine, I who have learned so much and still do every time I get to talk to this dearest friend of mine.


Introduction

I guess anybody doing statistical physics or probability theory has played around with Brownian Motion (by which I mean, here and in the following, the Wiener process, and not the physical phenomenon) at some time or another. It is used e.g. for modelling the price of a stock, the position of a particle diffusing in a gas or liquid, or the pinning force on an elastic interface in a disordered medium.

Being Markovian, time evolution of Brownian motion is completely determined by its propagator, i.e. the probability (density) to arrive at $x_1$ at time $ t_1$ starting from $ x_0$ at time $ t_0$. This is, of course, known to be a Gaussian. However, for practical applications, one often needs to restrict the Wiener process (in general, with drift) to a half-line or an interval, with some imposed boundary conditions (absorbing or reflecting). In the example of a stock price, these would describe call or put options on the stock. In this post I will derive, hopefully in a pedagogical way, the propagator of Brownian motion with drift and linear boundaries.

Propagators without drift

Let us first consider standard Brownian motion $ W(t)$ without drift. Without loss of generality, let us assume it starts at $W(0)=0$. It satisfies the Langevin equation

\[\dot{W}(t) = \xi(t)\]

where $ \xi(t)$ is Gaussian white noise with correlation

\[\overline{\xi(t)\xi(t’)} = 2\sigma \delta(t-t’).\]

With these conventions, the free propagator (i.e. the propagator without any boundaries) $ P(x,t)$ is given by the solution of the Fokker-Planck equation

\[ \partial_t P(x,t) = \sigma \partial_x^2 P(x,t)\]

with initial condition $ P(x,0) = \delta(x)$. This PDE, also known as the heat equation, is easily solved by taking a Fourier transform. The solution is given by

\[ P(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{x^2}{4\sigma t}}.\]

Now, let us determine the propagator with an absorbing boundary at $ x=b > 0$. In the Fokker-Planck equation, this is equivalent to the boundary condition $ P(b,t)=0$, which makes applying Fourier transforms difficult. However, we can use the method of images to find the solution: $ P(b,t)=0$ is enforced automatically if we add a negative source at $ x=2b$ (the position of the original source, reflected at $ b$), i.e. take the initial condition $ P(x,0) = \delta(x)-\delta(x-2b)$. The final propagator with an absorbing boundary at $ x=b$ is thus

\[P^{(b)}(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}\left[e^{-\frac{x^2}{4\sigma t}}-e^{-\frac{(x-2b)^2}{4\sigma t}}\right].\]

Similarly one can treat the case of two absorbing boundaries, one at $ x=b>0$, one at $ x=a<0$. One then needs an infinite series of images, and obtains the propagator as a series which can be rewritten in terms of Jacobi Theta functions.

Propagators with drift

Now let us generalize to the Brownian motion with drift $ \mu$. Then the Langevin equation for $ W(t)$ becomes

\[ \dot{W}(t) =\ mu + \xi(t).\]

The free propagator is obtained from the Fokker-Planck equation just as above:

\[P(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{(x-\mu t)^2}{4\sigma t}}.\]

Let us now introduce again a constant absorbing boundary at $ x=b$. Applying the method of images is not so straightforward anymore. Due to the drift, a path which goes from $ x=0$ to the boundary $ x=b$ will not have the same weight as the reflected path which goes from $ x=2b$ to the boundary $ x=b$. However, for the case of constant drift considered here, the weights of Brownian paths with and without drift have a simple relationship. In my view, the easiest way to see it is using path integrals. The propagator is given by

\[ P(x_f,t) = \int_{x(0)=0}^{x(t)=x_f} \mathcal{D}[x]e^{-\int_0^t \mathrm{d}s, \frac{1}{4\sigma}\left(\dot{x}(s)-\mu\right)^2}\]

Now, expanding the “action” in the exponent, using the fact that our drift $ \mu$ is constant, and using our boundary conditions, this is equal to

\[ P(x_f,t) = e^{-\frac{\mu}{2\sigma}x_f+ \frac{\mu^2}{4\sigma}t}\int_{x(0)=0}^{x(t)=x} \mathcal{D}[x]e^{-\int_0^t \mathrm{d}s, \frac{1}{2\sigma}\left(\dot{x}(s)\right)^2}.\]

We thus get a simple weight depending on the final position, but the remaining path integral is taken over a drift-less Brownian motion, and there we know the solution already, both with and without the boundary! In mathematical literature, you will often find this manipulation under the name of the Cameron-Martin-Girsanov theorem, but I find the path integral explanation much clearer for somebody coming from physics. Note that in the case where the drift $ \mu$ is a function of time, we cannot pull the weight out of the path integral, because it involves the whole trajectory and not just the final point. This shows why non-constant drift with absorbing boundaries is a much more complicated problem (although the free propagator is still trivial to write down!).

The final formula for the propagator of the Brownian motion with drift $ \mu$ and an absorbing boundary at $ x=b$ (also known as Bachelier-Levy formula) is thus

\[P^{(b,mu)}(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{mu}{2\sigma}x+ \frac{mu^2}{4\sigma}t}\left[e^{-\frac{x^2}{4\sigma t}}-e^{-\frac{(x-2b)^2}{4\sigma t}}\right]\]

This is now all that is required to compute things like first-passage times, survival probabilities, etc. The generalization to two absorbing boundaries follows from the solution in the driftless case by multiplying with the same weight as here.

I hope you see that with the right tools, obtaining these propagators is nothing miraculous. If you have any questions or comments, I’d be glad to hear them! If people are interested, at some point I may write a continuation of this blog post, possibly on generalizations of the methods discussed here to Ornstein-Uhlenbeck processes, Bessel Processes, or more complicated boundaries.

Have fun, and thanks for reading!

Ricardo: This post will be in english, for we have a very special guest today. Alexander Dobrinevski, author of the blog inordinatum.wordpress.com, is a good friend of mine from Belarus. Having finished his graduation at LMU, he followed the Advanced Studies in Mathematics program from Cambridge University to end up his doctoral thesis at the École Normale, where I had the pleasure to share with him the office for a few months. He is addicted to coffee, exotic movies and Laplace transforms. Today’s post is also very hardcore, to the benefit of our dear specialist in the field, and to mine, I who have learned so much and still do every time I get to talk to this dearest friend of mine.


Introduction

I guess anybody doing statistical physics or probability theory has played around with Brownian Motion (by which I mean, here and in the following, the Wiener process, and not the physical phenomenon) at some time or another. It is used e.g. for modelling the price of a stock, the position of a particle diffusing in a gas or liquid, or the pinning force on an elastic interface in a disordered medium.

Being Markovian, time evolution of Brownian motion is completely determined by its propagator, i.e. the probability (density) to arrive at $x_1$ at time $ t_1$ starting from $ x_0$ at time $ t_0$. This is, of course, known to be a Gaussian. However, for practical applications, one often needs to restrict the Wiener process (in general, with drift) to a half-line or an interval, with some imposed boundary conditions (absorbing or reflecting). In the example of a stock price, these would describe call or put options on the stock. In this post I will derive, hopefully in a pedagogical way, the propagator of Brownian motion with drift and linear boundaries.

Propagators without drift

Let us first consider standard Brownian motion $ W(t)$ without drift. Without loss of generality, let us assume it starts at $W(0)=0$. It satisfies the Langevin equation

\[\dot{W}(t) = \xi(t)\]

where $ \xi(t)$ is Gaussian white noise with correlation

\[\overline{\xi(t)\xi(t’)} = 2\sigma \delta(t-t’).\]

With these conventions, the free propagator (i.e. the propagator without any boundaries) $ P(x,t)$ is given by the solution of the Fokker-Planck equation

\[ \partial_t P(x,t) = \sigma \partial_x^2 P(x,t)\]

with initial condition $ P(x,0) = \delta(x)$. This PDE, also known as the heat equation, is easily solved by taking a Fourier transform. The solution is given by

\[ P(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{x^2}{4\sigma t}}.\]

Now, let us determine the propagator with an absorbing boundary at $ x=b > 0$. In the Fokker-Planck equation, this is equivalent to the boundary condition $ P(b,t)=0$, which makes applying Fourier transforms difficult. However, we can use the method of images to find the solution: $ P(b,t)=0$ is enforced automatically if we add a negative source at $ x=2b$ (the position of the original source, reflected at $ b$), i.e. take the initial condition $ P(x,0) = \delta(x)-\delta(x-2b)$. The final propagator with an absorbing boundary at $ x=b$ is thus

\[P^{(b)}(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}\left[e^{-\frac{x^2}{4\sigma t}}-e^{-\frac{(x-2b)^2}{4\sigma t}}\right].\]

Similarly one can treat the case of two absorbing boundaries, one at $ x=b>0$, one at $ x=a<0$. One then needs an infinite series of images, and obtains the propagator as a series which can be rewritten in terms of Jacobi Theta functions.

Propagators with drift

Now let us generalize to the Brownian motion with drift $ \mu$. Then the Langevin equation for $ W(t)$ becomes

\[ \dot{W}(t) =\ mu + \xi(t).\]

The free propagator is obtained from the Fokker-Planck equation just as above:

\[P(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{(x-\mu t)^2}{4\sigma t}}.\]

Let us now introduce again a constant absorbing boundary at $ x=b$. Applying the method of images is not so straightforward anymore. Due to the drift, a path which goes from $ x=0$ to the boundary $ x=b$ will not have the same weight as the reflected path which goes from $ x=2b$ to the boundary $ x=b$. However, for the case of constant drift considered here, the weights of Brownian paths with and without drift have a simple relationship. In my view, the easiest way to see it is using path integrals. The propagator is given by

\[ P(x_f,t) = \int_{x(0)=0}^{x(t)=x_f} \mathcal{D}[x]e^{-\int_0^t \mathrm{d}s, \frac{1}{4\sigma}\left(\dot{x}(s)-\mu\right)^2}\]

Now, expanding the “action” in the exponent, using the fact that our drift $ \mu$ is constant, and using our boundary conditions, this is equal to

\[ P(x_f,t) = e^{-\frac{\mu}{2\sigma}x_f+ \frac{\mu^2}{4\sigma}t}\int_{x(0)=0}^{x(t)=x} \mathcal{D}[x]e^{-\int_0^t \mathrm{d}s, \frac{1}{2\sigma}\left(\dot{x}(s)\right)^2}.\]

We thus get a simple weight depending on the final position, but the remaining path integral is taken over a drift-less Brownian motion, and there we know the solution already, both with and without the boundary! In mathematical literature, you will often find this manipulation under the name of the Cameron-Martin-Girsanov theorem, but I find the path integral explanation much clearer for somebody coming from physics. Note that in the case where the drift $ \mu$ is a function of time, we cannot pull the weight out of the path integral, because it involves the whole trajectory and not just the final point. This shows why non-constant drift with absorbing boundaries is a much more complicated problem (although the free propagator is still trivial to write down!).

The final formula for the propagator of the Brownian motion with drift $ \mu$ and an absorbing boundary at $ x=b$ (also known as Bachelier-Levy formula) is thus

\[P^{(b,mu)}(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{mu}{2\sigma}x+ \frac{mu^2}{4\sigma}t}\left[e^{-\frac{x^2}{4\sigma t}}-e^{-\frac{(x-2b)^2}{4\sigma t}}\right]\]

This is now all that is required to compute things like first-passage times, survival probabilities, etc. The generalization to two absorbing boundaries follows from the solution in the driftless case by multiplying with the same weight as here.

I hope you see that with the right tools, obtaining these propagators is nothing miraculous. If you have any questions or comments, I’d be glad to hear them! If people are interested, at some point I may write a continuation of this blog post, possibly on generalizations of the methods discussed here to Ornstein-Uhlenbeck processes, Bessel Processes, or more complicated boundaries.

Have fun, and thanks for reading!

Introduction

Quiconque ayant déjà pratiqué la physique statistique ou les probabilités a forcément eu affaire au mouvement Brownien (j’entends par là le processus de Wiener, et pas le phénomène physique). On l’utilise, par exemple, pour modéliser l’évolution des prix, la position des particules dans un liquide ou un gaz, ou la force d’ancrage sur l’interface élastique d’un milieu désordonné.

L’évolution temporelle du mouvement brownien est markovienne, et donc entièrement déterminée par son propagateur, c’est-à-dire la (densité de) probabilité d’atteindre $x_1$ à la date $ t_1$ en partant de $ x_0$ à la date $ t_0$. Il est bien connu que ce propagateur est gaussien. Cependant, pour des applications pratiques, il est souvent nécessaire de restreindre le processus de Wiener à une demi-droite ou un intervalle, avec des conditions aux bords imposées (absorption ou réflexion). Dans l’exemple du prix d’un stock, ces dernières décriront les options d’achat et de vente. Dans cet article, je vais obtenir le propagateur du mouvement brownien avec dérive et conditions aux bords linéaires, avec une approche que j’espère pédagogique.

Propagateurs sans dérive

Considérons d’abord le mouvement brownien standard $ W(t)$ sans dérive. Sans perte de généralité, supposons $W(0)=0$. $W$ vérifie l’équation de Langevin :

\[\dot{W}(t) = \xi(t)\]

où $ \xi(t)$ est un bruit blanc gaussien avec des corrélations

\[\overline{\xi(t)\xi(t’)} = 2\sigma \delta(t-t’).\]

Avec ces conventions, le propagateur libre (c’est-à-dire sans conditions aux bords) $ P(x,t)$ est donné par la solution de l’équation de Fokker-Planck

\[ \partial_t P(x,t) = \sigma \partial_x^2 P(x,t)\]

avec la condition initiale $ P(x,0) = \delta(x)$. Cette équation aux dérivées partielles, également connue sous le nom d’équation de la chaleur, se résout facilement en prenant une transformée de Fourier. On trouve

\[ P(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{x^2}{4\sigma t}}.\]

Maintenant, intéressons-nous au propagateur avec une frontière absorbante en $ x=b > 0$. Dans l’équation de Fokker-Planck, ceci se traduit par $ P(b,t)=0$, ce qui rend plus difficile la transformation de Fourier. Cependant, on peut utiliser la méthode des images pour trouver la position : $P(b,t)=0$ est automatique en ajoutant une source négative en $ x=2b$ (symétrique de la source initiale par rapport à la frontière en $ b$). Cela revient à prendre la condition initiale $ P(x,0) = \delta(x)-\delta(x-2b)$. Finalement, le propagateur avec frontière absorbante en  $x=b$ est

\[P^{(b)}(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}\left[e^{-\frac{x^2}{4\sigma t}}-e^{-\frac{(x-2b)^2}{4\sigma t}}\right].\]

On traite le cas de deux frontières absorbantes en $ x=b>0$ et $ x=a<0$ de la même façon, mais il faut maintenant une infinité d’images, et le propagateur s’écrit sous forme d’une série qui peut être exprimée en termes des fonctions $\vartheta$ de Jacobi.

Propagateurs avec dérive

Généralisons maintenant au mouvement brownien avec une dérive $ \mu$. L’équation de Langevin pour $ W(t)$ devient

\[ \dot{W}(t) =\ mu + \xi(t).\]

Comme ci-dessus, le propagateur libre se déduit de l’équation de Fokker-Planck :

\[P(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{(x-\mu t)^2}{4\sigma t}}.\]

Introduisons maintenant une frontière absorbante en $ x=b$. La méthode des images n’est plus évidente à appliquer ! A cause de la dérive, le poids d’une trajectoire partant de $ x=0$ vers la frontière en $ x=b$ ne sera pas le même que celui de son image, de $ x=2b$ à $ x=b$. Cependant, dans le cas d’une dérive constante, une relation simple lie les poids avec et sans dérive. Il me semble que la façon la plus simple de s’en rendre compte est l’utilisation des intégrales de chemin. Le propagateur est donné par

\[ P(x_f,t) = \int_{x(0)=0}^{x(t)=x_f} \mathcal{D}[x]e^{-\int_0^t \mathrm{d}s, \frac{1}{4\sigma}\left(\dot{x}(s)-\mu\right)^2}\]

En développant maintenant “l’action” dans l’exponentielle, et en utilisant le fait que $ \mu$est constant, ainsi que les conditions aux bords, on trouve

\[ P(x_f,t) = e^{-\frac{\mu}{2\sigma}x_f+ \frac{\mu^2}{4\sigma}t}\int_{x(0)=0}^{x(t)=x} \mathcal{D}[x]e^{-\int_0^t \mathrm{d}s, \frac{1}{2\sigma}\left(\dot{x}(s)\right)^2}.\]

On obtient alors un poids qui ne dépend que de la position finale (hors de l’intégrale), et l’intégrale restante ne présente plus de dérive, ce qui signifie que nous connaissons déjà la solution, avec ou sans frontières ! Dans la littérature mathématique, vous trouverez fréquemment cette manipulation sous le nom de “Théorème de Cameron-Martin-Girsanov“, mais je trouve que l’approche via l’intégrale de chemin est beaucoup plus claire pour un physicien. Notons que si la dérive $ \mu$ dépend du temps, on ne peut pas sortir le poids de l’intégrale de chemin, car il dépend de toute la trajectoire, et pas seulement du point final. C’est pourquoi il s’agit d’un problème bien plus difficile, bien que le propagateur libre soit toujours trivial à écrire !

La formule finale pour le propagateur du mouvement brownien avec dérive $ \mu$ et une frontière absorbante en $ x=b$ (connu sous le nom de “formule de Bachelier-Levy”) est donc

\[P^{(b,mu)}(x,t) = \frac{1}{\sqrt{4\pi\sigma t}}e^{-\frac{mu}{2\sigma}x+ \frac{mu^2}{4\sigma}t}\left[e^{-\frac{x^2}{4\sigma t}}-e^{-\frac{(x-2b)^2}{4\sigma t}}\right]. \]

C’est tout ce dont nous avons besoin pour calculer des choses comme des temps de premier passage, des probabilités de survie, etc. La généralisation à deux frontières absorbantes peut être déduite de la solution sans dérive, en multipliant par le même poids.

J’espère vous avoir fait sentir qu’avec les bons outils, obtenir ces propagateurs n’a rien de miraculeux. Si vous avez des questions ou des commentaires, je serai ravi de les entendre ! Pour approfondir, diverses voies sont envisageables, comme des généralisations des méthodes exposées ici aux processus de Ornstein-Uhlenbeck, de Bessel, ou encore des conditions aux bords plus compliquées.

Merci de m’avoir lu !