Large deviations and random graphs

Talvez os leitores que não estejam interessados em assuntos técnicos devam pular os parágrafos 2 a 5 (este é o parágrafo 0). Ou talvez ir pro próximo post =D

Hoje teve uma palestra aqui do professor S.R.S. Varadhan. Eu não sabia quem era ele antes, mas dei uma olhada na sua biografia no Wikipedia e achei que podia ser interessante. Bom, assim que eu consegui uma cadeira no auditório super lotado, eles colocaram os slides da apresentação do cara e o título era “Random Graphs” o.O Já começou bem. A partir daí eu já fiquei interessada no assunto. E foi legal que ele deu uma palestra super técnica! Cheia de fórmulas matemáticas, e integrais e topologia, e grafos e cliques e tal. Eu me senti na universidade de novo =) Ele veio dar a palestra na Infosys porque é o chair do júri do prêmio de matemática (eu nem sabia que a Infosys dava esse prêmio…) Basicamente a palestra foi a apresentação de um artigo dele (que ele gentilmente me enviou – junto com os slides – depois que eu pedi no final da palestra, mas ele pode ser encontrado aqui).

Vou tentar falar o que eu entendi da palestra, apesar de eu ter saido de lá com um monte de perguntas. A primeira coisa importante que eu aprendi é o conceito de “large deviations” (com o cara que ajudou a desenvolver a teoria =). Imagina que você tem um espaço de possibilidades (por exemplo, possíveis locais que uma pessoa pode estar as 3 da manhã de terça-feira). A probabilidade é alta para determinado local X (sua casa, por exemplo), e é baixa para outro conjunto de locais C. A teoria de “large deviations” estuda a taxa com que essa probabilidade diminui em um espaço (topológico).

Agora vamos aos grafos. Um grafo randômico com n vértices é um grafo em que cada possivel aresta tem uma propabilidade p de ocorrer. Dados esses grafos, qual é o número de vezes que um determinado grafo (por exemplo, o K3) aparece como subgrafo? Pela teoria dos grandes números (ver parágrafo seguinte) esse número se aproxima de um valor se você usar n suficientemente grande (a saber: p^3 / 6). Então esse valor é seu local X de alta probabilidade. Mas o que acontece com essa probabilidade quando nos aproximamos de outros valores? Essa teoria de “large deviations” se aplica a esse caso dadas algumas restrições do espaço topológico. (Mais detalhes quando eu conseguir entender o que são espaços topológicos fracos e fortes… e o resto do artigo.)

Uma coisa bacana que eu aprendi na palestra é a lei dos grandes numeros (“law of large numbers”) que diz que se um experimento for repetido uma grande quantidade de vezes, o valor médio dos seus resultados estará perto do valor esperado. E quanto mais vezes o experimento for feito, menor é a diferenca entre a média e o valor esperado. Eu sei, é uma ideia super intuitiva, mas eu não sabia que existia uma lei pra isso =) (e é claro que tem uma prova, realizada por um dos Bernoulli’s e por Poisson).

No final da palestra algumas pessoas fizeram perguntas, e um cara teve a coragem de perguntar se o professor acredita ou nao que P = NP foi provado! haha A resposta dele foi que a maioria dos seus colegas acredita que não foi provado e que a igualdade nao procede =P Mas isso é tudo uma questao de crenças.

As outras duas perguntas foram as famosas perguntas previsíveis: “Tá, e o que a gente faz com isso agora?”. Bom, eu achei bonitinho e não precisa ter aplicação nenhuma… só de ter me deixado curiosa pra pesquisar mais um tanto de assunto já foi suficiente. Mas não e assim com essas pessoas de empresas. Eles queriam que o professor Varadhan virasse pra eles e falasse assim: “Ah, agora vc faz um algoritmo com isso e aplica na rede social que vc quiser e ele vai te falar quais são as pessoas que podem comprar mais seu produto.”. Não né. Essa pergunta me faz pensar sempre que existe uma grande distância ainda entre quem estuda teoria e quem aplica. Uma coisa é desenvolver uma teoria, outra muito diferente e ainda muito difícil é saber como aplicar isso corretamente em algum problema concreto. Eu sempre tenho a impressão de que existem muitas teorias que podiam ser aplicadas se as pessoas realmente parassem e pensassem no seu problema como um elemento abstrato e conhecessem a teoria de verdade. É muito dificil saber qual abstração usar, e qual teoria vai te ajudar, mas a gente tem que conhecer o que existe lá fora o máximo, pra saber usar direitinho.

Acho que ja escrevi demais….