Arquivos da categoria: Hardcore

Para matemáticos e físicos que passarem por aqui.

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.

Meu trabalho

Hardcore Rookie

Tirei férias, viajei a trabalho e abandonei o blog, confesso. Peço desculpas pela ausência de aviso, já que avisei ano passado, mas até durante a viagem esqueci meu carregador e meu notebook era apenas um peso de papel tecnologicamente avançado. Nesse último mês, coloquei meu primeiro artigo no arXiv, um grande site que abriga artigos científicos e os disponibiliza gratuitamente. Você pode conferir meu trabalho aqui, mas dificilmente ele será muito compreensível, então aproveito esse post para me fazer entender, e tentar explicar o que foi meu trabalho desses últimos meses.

Transporte de elétrons é algo bem importante na física, compreender e dominar essa arte é fundamental para construir qualquer aparelho eletrônico que se preze. Não domino nada de eletrônica, mas gosto de elétrons, e imagino um sistema da seguinte forma: elétrons podem entrar em uma “caixa” com propriedades praticamente desconhecidas, e podem sair dela. Dentro, fazem o que quiserem, e eu tenho pouquíssimo controle do que acontece nessa caixa. A pergunta é: sem saber praticamente nada sobre essa caixa, qual a melhor estimativa que posso fazer do fluxo de elétrons nesse sistema?

quantum_dot_1

Eu honestamente prefiro elétrons em amarelo, mas em azul fica mais fácil ver, e é a preferência da física de partículas com que divido o apartamento. Essa pergunta sobre o fluxo de elétrons não é fácil, e é importante, esse tipo de sistema existe na vida real e a eletrônica de seu celular é cheia deles. Conhecido como “ponto quântico”, quantum dot, esse é um dos modelos mais simples de transmissão de elétrons em meios desconhecidos. Na vida real, isso é mais próximo dessa imagem:

quantumdot Essa questão vem sendo respondida desde os anos 80, sempre com um modelo “ideal” em mente. Neste modelo, a caixa e os conectores são perfeitamente acoplados, não há chance de um elétron não entrar ou de não sair, ou seja, não há reflexão de elétrons no contato entre a caixa e os conectores. Esse modelo é extremamente bem sucedido, mas longe da realidade, e meu artigo é sobre aproximar esse modelo da realidade.

Em 2007, Kanzieper e Vidal deduziram como é esse fluxo para o caso em que há impurezas entre os conectores e a caixa. A fórmula que eles obtiveram é horrível, impraticável, ainda que não exatamente feia. Tanto é difícil que os autores só conseguiram estudar o caso de conectores muito pequenos, deixando passar apenas elétrons em uma dada velocidade, um modelo bem limitado. Nesses últimos quatro meses, tratei essa fórmula com muito carinho, e consegui resultados para um modelo um pouco diferente: podemos agora deixar passar quantos elétrons quisermos, e podemos calcular esse fluxo em qualquer precisão, mas minhas fórmulas funcionam melhor para pequenas impurezas. Quanto maiores as impurezas, mais conta você vai ter que fazer. Não é um modelo ruim, porque em geral o número de impurezas é pequeno. Ora, se o caso ideal já era bem sucedido, o caso “impurezas pequenas” será ainda melhor.

E esse foi meu trabalho. Não parece muito emocionante, não parece explicar a origem dos átomos, ou não revela uma verdade fundamental da natureza, mas isso é fazer ciência. O que aprendemos na escola, e a maior parte do que você encontra por aí, é ciência pronta, tudo acabado, bonitinho, ciência que já tem décadas, ou séculos, de idade. Fazer ciência, ser cientista, é como abrir caminho na floresta com um facão, não sabemos o que vamos encontrar, é difícil atravessar obstáculos e podemos muito bem não chegar a lugar nenhum. Se encontramos, no entanto, uma descoberta fascinante; logo esse caminho será alargado, asfaltado, iluminado e a descoberta receberá o tratamento que merece, só então ela vai parar nas escolas ou na divulgação científica.

A partir daqui, o post se torna Hardcore. Continue por sua conta em risco.

Eu não poderia encerrar esse post sem comentar algumas coisas específicas do meu artigo. Como vocês são gente grande na ciência, posso colocar uma imagem mais adequada do quantum dot:

quantum_dot_2Temos uma função de onda dos elétrons que entra e uma que sai. Os conectores desse tipo de sistema costumam ser projetados para deixarem passar funções de onda com um número de onda específico, ou seja, se decompusermos \Psi em ondas planas, o conector vai transmitir apenas N modos de onda. Analogamente, o conector de saída pode deixar passar M modos. Esses valores são importantes, pois se são muito grandes a onda passa praticamente inteira.

A caixa sendo desconhecida, uma maneira de tratar o problema é supor que os elétrons sofrem espalhamento quântico no interior. Sendo agora um problema de scattering, podemos deduzir a matriz S do problema (a matriz que torna a função de onda inicial na final: \Psi^\prime=S\Psi). O problema é que, para haver a S, precisamos no hamiltoniano da caixa, H. É um pouco complicado, mas possível, deduzir que, se a caixa é desconhecida, o hamiltoniano que maximiza a entropia e representa nossa melhor estimativa é um cujas entradas são gaussianas.

Um hamiltoniano gaussiano gera uma matriz S do tipo “Poisson”, que é uma matriz complicada. Se supusermos o caso ideal, apenas o hamiltoniano da caixa conta e não há hamiltoniano de acoplamento entre a caixa e os conectores, então essa matriz S será uma matriz uniformemente distribuída no espaço das matrizes unitárias. A partir dela, podemos estudar o que chamamos de autovalores de transmissão, que são os autovalores da parte de transmissão da matriz S. O trabalho de Kanzieper e Vidal deduz a densidade de probabilidade para esses autovalores, mas essa p.d.f. é horrenda. Neste artigo, descobrimos que se essa p.d.f. for expressa em termos de polinômios de Schur, ela fica muito mais bonita, e, além disso, podemos expressar a probabilidade do caso não-ideal como a do caso ideal vezes um fator de correção. Ele é feio, é verdade, mas essa informação é fundamental, porque podemos importar todos os cálculos de momentos e probabilidades do caso ideal (estudado desde os anos 80) para o não-ideal, bastando apenas multiplicar pelos fatores adequados. Se esse assunto interessar alguém, recomendo a excelente review de Beenakker.

Mudanças

Geek Hardcore Rookie

Como vocês devem ter percebido, o endereço do blog mudou. Espero que o redirecionamento esteja funcionando corretamente, não quero ninguém se perdendo no caminho. Transferi o blog para um domínio próprio, com hospedagem própria, ainda que continue usando a plataforma WordPress para escrever e, como vocês, para ler. Assim, não estarei mais usando o endereço ricardoamarino.wordpress.com.

As razões da transição são muitas, mas, se eu pudesse resumir, foi uma busca por liberdade. Antes eu não podia mexer no HTML ou no CSS do site, ou seja, minhas opções de personalização eram muito limitadas. Não podia instalar plugins, o que me obrigava ou a improvisar, ou a confiar em ferramentas nativas do WordPress que nem sempre eram as melhores. Assim, os leitores podem esperar, a partir de hoje, as seguintes mudanças:

  • Um LaTeX decente. Agora tenho um plugins capaz de escrever fórmulas matemáticas aceitáveis dentro e fora do corpo do texto. Antes, o WordPress criava uma imagem das fórmulas e colava bizarramente no texto, costurando tudo como o monstro do Frankenstein, deixando fórmulas abaixo da linha do texto, com tipografia fraca e nem sempre fácil de enxergar. Tudo isso é passado, como vocês podem ver por essa fórmula:

    = {1 \over r^2}{\partial \over \partial r} \left(r^2 {\partial f \over \partial r} \right)+ {1 \over r^2 \sin \theta} {\partial \over \partial \theta}\left(\sin \theta {\partial f \over \partial \theta} \right)+ {1 \over r^2\sin^2 \theta} {\partial^2 f \over \partial \phi^2}

  • Inclusão de notas de rodapé, que aparecem quando você coloca seu cursor sobre alguma delas.1.
  • Otimização para encontrar o blog em sistemas de busca e, com sorte, aumentar o número de leitores!
  • Incorporação de scripts do Mathematica, o que me permite até fazer gráficos manipuláveis por vocês.
  • Criação do modo “tela cheia” ao clicar no título de um post, deixando a leitura mais agradável e com menos distrações.

Naturalmente, isso acompanha uma série de mudanças no layout que venho considerando há um bom tempo, em especial a fonte, o tamanho da fonte, a divulgação da categoria do post logo no início, o jogo de cores e outras frescuras que minha neurose não deixaria passarem. Ainda deve haver links quebrados, fórmulas tortas e outros desalinhos, por favor, não hesitem em me avisar. Espero que gostem das mudanças, conto com a opinião de vocês para melhoras, e desejo uma boa leitura.

  1. Como esta. []

Férias

Geek Hardcore Rookie

Nesse post, declaro férias do blog por catorze dias. Depois de seis meses em uma frequência de mais de um post por semana, preciso de um tempo para respirar e colocar os posts em dia sem comprometer a qualidade. Estou de férias, e isso significa que a inspiração é fraca enquanto não estou estudando e trabalhando. Férias são férias, e isso inclui dos textos desse blog.

Aos que ficam, ou que passam por aqui pela primeira vez, deixo uma lista de meus quatro posts favoritos, caso ainda não os tenham visto:

No cassino de Parrondo.

A pior forma de governo.

Aniversários.

Informação e demônios.

Até dia 17.

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.