Arquivo da tag: Física Estatística

Posts sobre física-estatística e matéria condensada.

Abaixo de zero

Sempre fico feliz quando uma notícia da física atinge o grande público, quando a mídia decide que algum descoberta forma uma frase de efeito digna de manchete, e nessa semana não foi diferente. Um grupo de físicos do Instituto Max Planck conseguiu criar um gás a temperatura negativa, e isso provocou manchetes muitas vezes enganosas e, apesar de algumas matérias terem saído interessantes, a maior parte era apenas um agregado de traduções de versões americanas feitas por quem não entende do assunto.

Temperaturas negativas não são novidade na física, elas têm até página na Wikipédia, e pretendo hoje, nesse post, tentar explicar o que queremos dizer com isso, e tentar esclarecer confusões lançadas pelas matérias sensacionalistas de física de folhetim. Para isso, precisamos entender o que é temperatura.

No princípio hesitei se poderia explicar esse tópico sem antes falar de um conceito fundamental da termodinâmica, e de toda a física, a entropia. Temia descobrir, enquanto escrevia, que eu mesmo não entendia o assunto, pois é uma das noções mais escorregadias da ciência. De forma extremamente simplificada, entropia é a medida da desorganização de um sistema. Preciso de um exemplo tão simplificado quanto minha explicação, vou usar um sistema a dois níveis de energia. Dificilmente encontramos algo na vida real que seja isso, mas pouco importa, quero apenas explicar o conceito. Imagine um sistema com N partículas, sendo cada partícula capaz de estar em um estado de energia zero ou em um estado de energia \varepsilon.

dois_estados_2Se todas as bolinhas estiverem confinadas no estado zero, esse sistema tem entropia zero. Se todas estiverem confinadas no estado \varepsilon, o sistema também terá entropia zero. Mas se elas puderem se mexer, variar de um estado a outro, essa entropia será um valor maior, e positivo, indicando que o sistema não mais possui aquela ordem perfeita de antes e agora é uma mistura estranha de estados. A entropia indica quão bem feita é essa mistura, sendo máxima quando todas as configurações do sistema, todas as combinações de bolinhas em cima e embaixo, são possíveis e igualmente prováveis, ou seja, desordem completa, não posso afirmar nada sobre o estado atual do sistema, ele pode ser qualquer coisa.

A temperatura é a medida de quanto a entropia de um sistema varia quando damos energia a ele: quanto menor a temperatura, mais desorganizado um sistema fica com energia. Naturalmente, quanto maior for a temperatura, menos desordem um sistema ganha com a energia.

O fato da temperatura ser sempre positiva em nosso cotidiano é um reflexo da propriedade natural do aumento de entropia com o aumento de energia, como arrumar sua casa perfeitamente e lançar dentro dela uma ratazana raivosa, o equivalente da energia; dificilmente a casa ficará ainda mais organizada. Assim, apesar de sistemas com alta temperatura ganharem pouca entropia com energia, eles não perdem entropia.

Se deixamos nosso sistema de bolinhas a dois níveis interagir com o meio externo, ele poderá trocar energia com o meio e as bolinhas ganham ainda mais liberdade de subir e descer a ladeira. Se o sistema e o meio externo são muito diferentes quando entram em contato, eles vão trocar energia até que o quanto um sistema é desordenado pelo ganho de energia seja igual ao quanto o outro também é, ou seja, até que as temperaturas sejam iguais.

Isso é reflexo do princípio de máxima entropia, uma noção física que vai além das bolinhas e partículas, ligada profundamente a teoria da informação e probabilidades. Mais uma vez de forma bem simplificada, ele diz que, se você não tem uma boa razão para proibir um estado, o sistema atingirá esse estado e, se não tem uma boa razão para diferenciar dois estados, o sistema atingirá os dois com a mesma probabilidade. Em nosso problema das bolinhas, o sistema trocará energia com o meio externo até que o quanto ele causaria de desordem cedendo energia seja igual ao quanto ele ganharia de desordem ganhando energia, porque dessa maneira a entropia do processo todo (sistema + meio externo) será a máxima possível. Dessa forma, quando as temperaturas são iguais, isso significa que tanto o conjunto sistema + meio externo pode ocupar o maior número de estados possíveis de energia.

Como um gás lançado em uma sala vazia tende a se dispersar, não a se concentrar, porque eu não tenho uma boa razão para impedi-lo de ir para qualquer lugar da sala. Ele tende a ocupar todo o espaço e a chance de encontrar uma partícula em qualquer lugar é a mesma: isso é o princípio da máxima entropia. Se você conectar essa sala a uma outra vazia, pouco a pouco o gás vai ocupando também a outra sala até que todos os estados possíveis sejam ocupados com a mesma probabilidade.

Pelo princípio da máxima entropia, o gás tende a invadir a segunda sala e ocupar todo o espaço. A probabilidade de que ele fique todo na primeira sala é infinitamente pequena.

Se deixamos o sistema acoplado ao meio externo em uma temperatura fixa, ele trocará energia com o meio externo, e a temperatura será o quanto de desordem ele vai ganhar quando ganha energia. Se essa temperatura é baixa, o sistema ganha muita entropia com um pouco de energia. Isso acontece em situações como a de haver todas as bolinhas paradas na posição 0. Dar um pouco de energia significa permitir alguns saltos para o andar de cima, isso bagunçaria o sistema dando bastante entropia a ele. Se o sistema está em alta temperatura, como no caso de um gás quente, dar ainda mais energia não bagunçaria tanto o sistema.

Podemos escrever isso com alguma matemática. A chance de uma daquelas bolinhas estar em um estado de energia E é dada por \frac{e^{-E/T}}{Z}, onde e é um número especial entre 2 e 3 e Z é alguém que multiplicamos para que a probabilidade não seja maior que 1 (para quem começou a ver física estatística, essa é a distribuição de Boltzmann!). É fácil ver que a chance de estar no estado de energia 0 é 1/Z, enquanto a chance de estar no estado \varepsilon é \frac{e^{-\varepsilon /T}}{Z}. Isso representa um fato físico famoso: é mais fácil estar em um estado de baixa energia que em um de alta energia. Quanto menor a temperatura, mais difícil é encontrar alguém em um estado de energia alta. Quanto maior a temperatura, mais ambos os estados ficam com probabilidades parecidas. A maior parte dos sistemas físicos funciona dessa exata maneira.

No entanto, se você conseguir ser malandro, como os físicos do Instituto Max Planck, e criar um sistema físico bem patológico tal que estados de energia mais alta são mais prováveis, como você explica usando esse formalismo? Ora, basta dizer que são estados a temperatura negativa. Dessa forma, \frac{e^{-\varepsilon /T}}{Z}>1/Z e você consegue continuar a trabalhar com esses sistemas usando sua matemática favorita.

É porque associamos temperatura a essa taxa de ganho de desordem que podemos interpretar desse jeito estranho. Temperatura não é mais o movimento das partículas, isso ficou com os gases ideais no colegial, ela agora é a medida do ganho da desordem em função da energia. E se um sistema começa a privilegiar estados de energia alta, interpretamos isso como uma temperatura negativa.

Ouvi muito a respeito, inclusive da Wikipédia, sobre a temperatura negativa ser o limite de uma temperatura tão positiva que ela “dá a volta” e vira negativa. Como dizer que os reais são um corpo cíclico me causa urticária, tento explicar o que isso significa. Uma temperatura muito baixa favorece muito estados de baixa energia. Uma temperatura alta não favorece ninguém, e quanto mais alta, menos favorecimento possui. Se atingíssemos a temperatura +\infty, teríamos passado de uma situação de favorecimento das energia baixas a não favorecer ninguém. Se fôssemos “além” do +\infty, teríamos uma situação que privilegia as altas energias, e é isso que aquela explicação estranha quer dizer. Não gosto dela, e paro a explicação da explicação por aqui.

Resumindo: os cientistas do Instituto Max Planck conseguiram criar um sistema patológico o suficiente para deixar os estados de alta energia mais prováveis que os de baixa energia. Na matemática da física estatística, isso é interpretado como uma temperatura negativa, pois temperatura é o que mede essa preferência por estados de baixa energia. Isso não é nada chocante ou escandaloso, é interessante que eles tenham conseguido isso para um sistema quântico bem complicado, o artigo original está aqui, mas, infelizmente, é mais uma manchete para vender jornal que um grande avanço para a termodinâmica.

Assumo que o post ficou confuso, mas é um tema complicado. Um dia sento e escrevo algo mais claro sobre entropia, no mesmo dia em que tomar coragem para ler a montanha de textos a respeito da interpretação física dela. Precisaria selecionar, ler, escrever, revisar tanta coisa que, em matéria de desordem, deixo exatamente como está.

Anúncios

Crime e castigo

Há algum tempo, inspirado em um comentário desse blog, queria escrever algo sobre o fenômeno estatístico conhecido como regressão à média. Desde pequeno fui fascinado pela análise teórica do sermão que recebia de meus pais a cada travessura que aprontava. Quebrei janelas, copos, sujei-me, sujei a casa, nada voluntário, coisa de criança; mas recebia, a cada evento, a devida repreensão de pai ou mãe (ou dos dois, não eram excludentes). Também levava broncas por notas mais baixas, não tantos elogios pelas altas, que eram, afinal, minha obrigação. Achava que as coisas eram daquele jeito, que não poderia ser de outro jeito, até, entrando na faculdade, conversar com um amigo que cursava administração de empresas. Segundo ele, muito mais eficaz que esse método era o inverso, o tal do positive reinforcement, elogiar o que é bom e trabalhar no que está ruim, mostrar ao time vídeos com seus acertos ao invés de erros, meu amigo citava experiências sociológicas e psicológicas bem interessantes para provar seu ponto, mas eu custava a acreditar.

Dizer que a recompensa é o melhor caminho choca nossa experiência. Estamos habituados a ver resultados melhorarem após a repreensão, e muitos dizem que, após o elogio, o elogiado tende a piorar e a decepcionar, como se elogiar estragasse, como se ficar feliz e orgulhoso o tornasse relaxado. O post de hoje serve para desarmar esse argumento, e nossa ideia de que alguém “aprendeu a lição” após uma bronca bem tomada. Vou argumentar que esse fenômeno de fato existe, a piora em relação ao elogio e a melhora em relação à bronca, mas que ele reflete muito mais uma verdade estatística que uma mudança de comportamento.

Vamos imaginar uma criança, Denis, o pimentinha, que, ao decorrer do ano letivo, fará 20 provas. Ele não é o melhor da sala, nem o pior, e estuda um pouco para cada prova, mas não muito. Denis estuda suas matérias para tirar um 7,0, que é uma nota boa em sua opinião. No entanto, algumas vezes a prova é mais fácil, ou mais difícil, então sua nota varia; sua média é constante, mas as flutuações são aproximadamente de dois pontos em sua nota. Ou seja, vamos tratar a nota de Denis como uma variável aleatória de média 7,0 e distribuição normal com variância 1. Dessa forma, a chance de ele tirar acima de 9,0 é de 2,2%, e a chance de tirar abaixo de 5,0 também é de 2,2%, sendo 68,2% a probabilidade de ele tirar entre 6,0 e 8,0.

Esses números podem parecer estranhos, mas esse modelo é um dos mais adequados para representar tarefas humanas, a chamada distribuição gaussiana, ou distribuição normal. Ela diz que teremos um valor esperado (no caso de Denis, 7,0), mas que teremos dias bons e ruins. A maior parte dos dias (68,2%) não será muito longe do valor esperado (entre 6,0 e 8,0), mas alguns, excepcionais (2,2%), podem ser muito bons (acima de 9,0, caiu exatamente o que ele havia estudado!) ou muito ruins (abaixo de 5,0, não caiu quase nada do que ele sabia).

Sua mãe se preocupa com sua educação, e o disciplina como sua mãe a disciplinou. Ela dá um presente a Denis cada vez que ele tira uma nota acima de 9,0, e o castiga cada vez que ele tira uma nota abaixo de 5,0. Vejamos como seriam as notas de Denis em um ano:

O que a mãe de Denis entenderá desse gráfico? Note que toda vez que ela castiga Denis, suas notas tendem a subir, enquanto toda vez que ela o presenteia, ele tende a tirar notas piores! É importante notar que isso nada diz sobre o aprendizado de Denis, eu apenas tirei notas aleatoriamente, dizendo que Denis é um aluno nota 7,0 que tem dias bons e ruins.

Essa ilusão da eficácia do castigo ocorre porque é muito raro ter dois dias ruins seguidos, e a ilusão da ineficácia do elogio é pela também raridade de dois dias excepcionalmente bons. O valor seguinte ao de um dia excepcional tende a ser menos espetacular, ou, como dizemos, tende a regredir à média dos valores.

Note, eu não estou dizendo que o castigo tem eficácia zero no comportamento, ou que o presente também não tem efeito, estou apenas dizendo que o raciocínio de punir e melhorar e não elogiar para não estragar pode ser aplicado até a variáveis aleatórias. Certamente a maneira como uma pessoa é tratada influencia em sua performance, mas uma teoria de castigo e recompensa que pode ser explicada pelo mero acaso, pela estatística, não pode ser tida como uma grande verdade sobre o comportamento humano.

Em outras palavras, imagine-se alguém que considera tirar menos que 5 em um sorteio para o próximo número do bingo algo ruim, e que considera tirar mais que 95 um resultado bom. Você pode, por algum motivo, culpar aquela esfera engradeada que vomita os números pelo resultado, e eu garanto: se você der uma bronca nela após cada resultado menor que 5, ela vai muito provavelmente melhorar bastante na próxima vez. Se você elogiar a cada resultado acima de 95, ela provavelmente irá te decepcionar na próxima bola sorteada.

Não quero, nem pretendo, dizer que broncas são ineficazes, ou que a única resposta possível para educar ou ensinar são elogios, paz e amor. Lanço esse post na polêmica opinião que pede uma revisão de nossos conceitos da eficácia do castigo como aprendizagem. Para que você se pergunte quanto do que você aprendeu veio dos benefícios de um sermão, ou, ainda, quanto de cada melhora que viu após uma bronca foi resultado dessa bronca ou se foi, por puro acaso, um dia melhor que ontem.

Informação e demônios

Sorry, but you must be THIS hot to get in.

Uma das leis físicas mais mal citadas, em diversos contextos e por ser um pouco difícil de explicar, é a segunda lei da termodinâmica: a lei responsável por prever que, ao colocar sua panela no fogo, não é o fogo que esquenta e ela que esfria; mas o contrário. Ela tem uma formulação complicada, a definição de entropia, de desordem e de reversibilidade, não vou me meter nisso hoje. Uma consequência dela, no entanto, é a seguinte propriedade: um sistema em equilíbrio térmico (todo mundo à mesma temperatura) precisa gastar energia para criar uma diferença de temperatura, ou seja, um lado quente e um frio. E essa propriedade é bem evidente, não por menos sua geladeira é ligada na tomada: ela usa essa energia para criar um ambiente frio (o interior do refrigerador) e um quente (aquela parte atrás que você usa para secar roupas e não devia).

Quando esse princípio foi formulado, no meio do século XIX, foi um dos pais da termodinâmica, o gigante na física James C. Maxwell, o primeiro a elaborar uma tortuosa ideia em busca de uma melhor compreensão da lei. Um bom jeito de entender uma lei da física é tentar imaginar um sistema que a viola, e foi o que ele fez. Imagine uma caixa com um gás, dividida em dois compartimentos (esquerda e direita) separados por uma parede. Essa parede, contudo, possui uma pequena porta, e essa porta é controlada por um pequeno demônio que possui informações sobre cada partícula na caixa. Cada vez que uma partícula rápida do lado esquerdo se aproxima da porta, o demônio a deixa passar para o direito; e cada vez que uma partícula lenta no lado direito se aproxima da porta, o demônio a deixa passar para o lado esquerdo. Essa figura ajuda, tirada do site phys.com.

Como temperatura não é nada mais que a medida da agitação média das partículas, esse demônio acaba de separar o gás em um lado quente e um lado frio. Se essa porta for leve o suficiente, ou uma porta rolante de atrito zero, o trabalho de abrir a porta é nulo e o demônio, sem gastar energia, criou uma diferença de temperatura. Sem precisar ligar na tomada, o demônio criou uma geladeira. Essa ideia, que de fato é um pouco absurda, ainda assim tenta provar um ponto: alguém com bastante informação sobre o sistema pode violar a segunda lei da termodinâmica.

Gostamos de nossas leis, não queremos que elas sejam violadas tão facilmente. O demônio de Maxwell assombrou físicos por quase um século, demoramos para perceber onde estava a energia gasta pelo demônio para dividir o gás em quente e frio. Enquanto muitos tentaram atacar a parede no problema, ou a própria natureza irreal da situação, a resposta estava no cérebro do demônio.

Maxwell foi muito malandro na escolha de palavras, pois o problema logo no início tenta te enganar: ele usa um demônio, uma criatura imaterial, para fazer o serviço. Ele sabe tudo, ou ao menos sabe o que se passa em torno da porta, e decide abrir ou não a porta com essa informação. Mas precisamos imaginar que, se ele sabe, essa informação está armazenada em algum lugar. Surpreendentemente, a energia gasta pelo demônio de Maxwell está no fato de sobre-escrever a informação que possuía sobre a partícula levando em conta o fato de ter aberto a porta e tê-la deixado passar.

Essa resposta parece um pouco roubada, mas foi uma das grandes descobertas do meio do século XX, o nascimento da teoria da informação. Quando os computadores começaram a surgir, muita gente se colocou a tentar estabelecer os limites de cálculo de uma máquina daquelas, e quanta energia ela gastaria para realizar operações. No início, acreditava-se que toda operação feita pelo computador possuía uma energia mínima para ser realizada, o valor k_BT\log 2, onde k_B é a constante de Boltzmann e T é a temperatura. Esse limite, proposto por von Neumann, não está correto, mas quase. Se estivesse correto, seria impossível criar computadores funcionais, a quantidade de energia necessária para fazê-los rodar seria alta demais e resfriá-los seria quase impossível. Apenas em 1961 Laudauer explicaria o limite corretamente: apenas uma operação do computador precisa de gasto de energia: a operação de apagar uma memória.

O argumento de Laudauer é simples e bonito. Vamos pensar na forma mais simples de se armazenar uma informação: o bit. Essa variável vale 0 ou 1, e deve ser armazenada de alguma forma, seja uma alavanca para um lado e não para outro, seja um aparato que permite ou não passar corrente. De forma bem geral, representamos o bit da seguinte forma:

Essa figura é um potencial, que podemos deformar à vontade, mantendo uma pequena bolinha de um lado e não do outro, representando o bit 1, enquanto no lado esquerdo seria o 0. Vamos supor que a temperatura da bolinha seja baixa o suficiente para que a chance de mudar de lado nesse potencial seja desprezível, como uma colina alta demais para que a bolinha vermelha, na velocidade em que está, possa atravessar e chegar ao outro lado.

Queremos operar esse bit, transformá-lo de 1 em 0, ou seja, fazer a bolinha passar da direita para a esquerda. Esse processo é o equivalente a sobre-escrever uma informação: devemos primeiro esquecer o que havia e depois forçar a bolinha a ficar do lado que queremos. A primeira coisa que precisamos fazer, portanto, é descer a barreira e “apagar” a informação:

Agora a bolinha passeia livremente entre os dois bits. Esse gif não é muito honesto, a bolinha, para ser coerente com a física, precisa ir e voltar muitas vezes, esse processo de descer a barreira deve ser feito de forma quasi-estacionária, ou seja, devemos descer a barreira levando um tempo muito maior que o tempo característico da bolinha de ir de um lado para o outro. Assim, a bolinha faria o caminho de ida e voltas muitas vezes antes de ver a barreira descer. Logo mais discutiremos se isso é realmente possível.

O próximo passo, escrever a informação, consiste em levantar a barreira de potencial de forma a forçar pouco a pouco a bolinha a ir para o lado que queremos. Enquanto ela vai e vem, vamos aumentando a barreira da direita. Isso forçará a bolinha a ficar confinada na esquerda. Em seguida, descemos a barreira da direita e temos a bolinha confinada do lado que queremos. O processo todo é resumido no seguinte gif, feito com algum esforço e uma tarde livre:

Vamos conversar agora sobre cada etapa desse processo, e as energias envolvidas. Queremos saber se precisamos gastar energia para sobre-escrever a memória e, se precisamos, em qual etapa exatamente. Para tal, vamos dar nomes às etapas:

Para entender o que está acontecendo, precisamos de algumas noções de termodinânica. Dizemos que um processo é reversível quando não há aumento de entropia, o caminho inverso pode acontecer.  É importante notar que todo processo reversível deve ser quasi-estacionário: é necessário que cada ponto desse processo seja um estado de equilíbrio, o equivalente a dizer, de maneira grosseira, que não podemos mexer o sistema muito rapidamente se temos a pretensão de seguir o caminho inverso. A ideia é mover um pouco, bem pouco, esperar o equilíbrio chegar, mover mais um pouquinho, esperar o equilíbrio chegar, e continuar dessa maneira. Em uma situação idealizada, podemos dizer que as mudanças são infinitesimais e que o processo, a cada instante, está em equilíbrio.

Note que esse raciocínio não é de todo desonesto, pois estamos buscando o limite mínimo de gasto de energia. Na busca do limite, trabalhamos com a situação mais idealizada possível, e concluímos que melhor que isso não conseguiremos jamais.

Assim, as etapas são realizadas em um processo quasi-estacionário, de forma a estar constantemente no estado de equilíbrio. Queremos um pouco mais que quasi-estacionário, queremos fazer todas essas etapas em processos reversíveis. Se conseguíssemos, como não aplicamos nenhum trabalho na bolinha (ela não ganhou energia nenhuma, não mudou sua altura máxima atingida no poço), não teremos gasto energia nenhuma e teremos trocado a bolinha de poço. É então que Landauer nos diz: isso não é possível. Para ser mais exato, todos os processos podem ser feitos sem gastar energia, exceto passar de A para B.

Apagar uma memória é a única operação que gasta energia. Nosso raciocínio do “quasi-estacionário” não se aplica ao processo AB, e é por isso que nossa ideia falha. Quando dizemos “um processo lento”, queremos dizer lento em relação ao tempo que o estado leva para estar em equilíbrio. Mas conforme vamos descendo o poço, notamos que, se o poço é muito alto, o tempo característico para que a bolinha mude de poço é muito alto. Ora, na situação A o tempo que a bolinha leva para mudar de poço é infinito, e na situação B ele é finito, é, portanto, impossível realizar o processo AB de forma quasi-estacionária, porque você, em algum momento, terá o tempo característico de mudança de poço igual ao tempo característico de descer o poço. Em outras palavras, é impossível realizar um processo mais lento que um processo cujo tempo característico para atingir o equilíbrio é infinito!

Todos os outros processos, se feitos de forma bem devagar, podem ser realizados de forma completamente reversível. O que pega é o processo de apagar a memória, de deixar o bit indeciso, e é aí que o demônio perde. Em seu cérebro, ou em seu supercomputador, ele deve, a cada vez que deixa uma partícula passar, reescrever sua informação sobre a trajetória da partícula, porque, pela vontade dele, ela mudou de lugar e não será mais a mesma. O demônio gasta energia, uma forma de “energia mental”, para reajustar seu conhecimento à nova configuração.

Isso resolve o problema do demônio de Maxwell, que deve gastar energia para criar essa geladeira microscópica. Por mais conhecimento que tenha, ele deve apagar e sobre-escrever bits no momento em que decide que a partícula mudará de lado. Para o demônio, nessas condições, o maior esforço não é lembrar, analisar ou mudar a partícula; seu maior esforço é, de forma quase poética, esquecê-la.

Epidemias, parte II

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á:

\displaystyle\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:

\displaystyle\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.

Propagating randomness

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

\displaystyle \dot{W}(t) = \xi(t),

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

\displaystyle \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

\displaystyle \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

\displaystyle 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

\displaystyle 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

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

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

\displaystyle 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

\displaystyle 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

\displaystyle 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

\displaystyle 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!

No cassino de Parrondo

A estatística possui alguns resultados não muito intuitivos, e muito divertidos. Um deles, proposto pelo físico espanhol Juan Parrondo, é um de meus favoritos. Para contar esse aparente paradoxo, convido-os a jogarem um jogo no cassino de Parrondo.

Esse cassino possui duas mesas, uma com um jogo A, outra com um jogo B, que possuem regras diferentes. Em ambos os jogos você só pode apostar uma ficha por vez, digamos, valendo R$100,00. Se você ganhar, leva mais uma ficha consigo. Se perder, perde sua ficha.

No jogo A você deve tirar uma carta de um baralho muito bem embaralhado. Se a carta for preta, você ganha. Se for vermelha, você perde. Neste maço de baralho, contudo, há um curinga; e você perde se tirar o curinga.

No jogo B, as regras mudam um pouco. Se seu número atual de fichas não for um múltiplo de três, suas chances são ótimas: você tira uma carta e perde apenas se ela for de copas ou o curinga. No entanto, se seu número de fichas for múltiplo de três, você deve tirar um às ou o curinga para ganhar, perdendo em todos os outros casos.

Não é surpresa nenhuma se eu te contar que o jogo A é falência na certa. A chance de você perder é maior que a de ganhar, e o ganho é igual à perda; jogar diversas vezes seguidas o jogo A fará você sair do cassino de mãos vazias. E apesar de o jogo B parecer um grande negócio, ele não é, podemos provar com diversas simulações numéricas, o que é o equivalente a jogar várias vezes, que a tendência é perder mais e mais dinheiro jogando o jogo B várias vezes. Assim, nas mesas do cassino de Parrondo a casa sempre vence.

Mas suponha que você pode caminhar de uma mesa à outra. Ora, certamente você só iria ao jogo B quando tem certeza de que suas fichas não são um múltiplo de três; o cassino jamais permitira algo parecido. Então você pode mudar de uma mesa para outra, mas com uma regra: você não pode contar suas fichas. Para deixar ainda mais justo, você não sabe, a cada aposta, se ganha ou perde, fica apenas sabendo o resultado final de suas aventuras ao sair do cassino. Assim, você até pode alternar os jogos, mas, sem contar as fichas e sem saber quando ganha ou perde, não consegue tirar muita vantagem disso. De certa forma, é como se você fosse obrigado a, na entrada, dizer quantas vezes irá apostar em cada jogo e em qual ordem. Assim, nunca sabendo em qual você ganha e qual perde, não poderá mudar de estratégia no meio da noite.

E eis a parte surpreendente. O jogo A é perda certa para você, o B também se jogado continuamente; mas alternar os jogos te leva a ganhar muito dinheiro. Esse fenômeno é o paradoxo aparente de Parrondo, duas táticas fracassadas que, combinadas, resultam em um ganho certeiro. Aos que não acreditam em mim, escrevi um pequeno código de computador para simular esses jogos todos. Claro, um exemplo não prova nada, coloco o resultado apenas para que sua confiança em mim aumente. O jogo A+B consiste em escolher, antes de cada jogada, aleatoriamente um dos jogos, ambos com a mesma probabilidade, como se tirasse no cara-ou-coroa a mesa escolhida para apostar. Eis os resultados, começando com uma fortuna de 47 fichas e permitindo ficar no negativo:

E esse aparente paradoxo nada mais é que um fenômeno estatístico fascinante usado abundantemente em diversos sistemas biológicos, o que inclui suas células. Temos, no caso de Parrondo, um jogo que apenas “bagunça” seu dinheiro (o jogo A, cuja chance é quase 1/2 para cada lado) e outro que te permite ganhar bastante, até atingir um valor (o múltiplo de três) bem difícil de atravessar, tão difícil que é mais fácil o jogo te fazer perder dinheiro a atravessar aquele valor e, perdendo, ele encontrará outro múltiplo de três, e será mais uma vez difícil de subir. No entanto, esse combo “bagunça+tendência” torna-se uma tática interessante, pois a bagunça pode te permitir “saltar” os múltiplos de três e, fora deles, você escala mais fácil a escada da fortuna.

 A partir desse ponto, esse post torna-se geek. Continue por sua conta em risco.

Parrondo não estudava teoria dos jogos, estudava os chamados “motores moleculares”, a base do funcionamento de diversos processos biológicos no nível celular. Suponha uma partícula submetida a um potencial da forma “dente de serra”:

E suponha essa partícula com uma temperatura suficientemente baixa (ou seja, suficientemente lenta) para que fique confinada no poço. Na figura, o roxo representa a densidade de probabilidade da posição dela, note que é bem difícil ela sair daquele lugar.

Mas suponha agora que eu aumente bastante a temperatura, bastante mesmo. Ora, a partícula se comportará como se ignorando o potencial, e as chances de ir para a esquerda e para a direita tornam-se as mesmas. Mas algo é diferente, se pensarmos em qual poço é mais provável que ela caia. Veja como é a evolução desse sistema, nessa figura descaradamente tirada daqui:

Note que, no momento de alta temperatura, é mais provável que ela tombe no poço da direita (área verde) que no poço da esquerda (área azul). Ao resfriarmos o sistema, que é representado pelo terceiro quadro, percebemos que a partícula tende a andar pela serra para a direita. Por causa da assimetria do potencial, o sistema adquire uma direção preferencial.

A relação disso com o cassino é simples, o jogo B é a situação de temperatura baixa e o jogo A é a alta temperatura, andar para a direita significa ganhar dinheiro e perder dinheiro é andar para a esquerda. Mas o cassino de Parrondo é malandro, nele os picos de potencial não são iguais e o jogo B tende a te empurrar para a esquerda, e o jogo A também (o que seria equivalente a uma gaussiana levemente assimétrica). No entanto, pela diferença na inclinação do potencial, passar ao jogo A e voltar ao B torna o sistema mais propenso a te mandar para a direita, a direção de maior fortuna!

Esse jogo de aumento e diminuição de temperatura é a base dos motores moleculares, ele é a razão pela qual a proteína é sintetizada pelo ribossomo em um sentido e não decide, aleatoriamente, seguir o sentido oposto e ir se desfazendo. E a célula funciona, vive, produz e sintetiza proteína dessa maneira: aumento de temperatura, diminuição, aumento (o que deve explicar aquele monte de ATP sendo desfeito para fazer esse sistema andar), em um intrincado maquinário de potenciais assimétricos que nos permite andar, pensar, respirar e jogar cartas em um cassino.