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….

3 thoughts on “Large deviations and random graphs”

  1. Gi, fiquei de boca aberta – não entendi nada tecnicamente falando(e nem deveria entender, pois nunca estudei nada a esse respeito). Mas tenho algo a dizer: em todas as ciências que eu tive a chance de conhecer um pouquinho, a distância entre o laboratório (teoria) e a clínica (prática) é enoooooorme. E isso me leva a pensar que as pessoas que vivem essencialmente da prática são imediatistas, querem apertar um botão aqui para acender uma luzinha ali. E se esquecem do caminho que a energia tem que percorrer (seja wireless ou não :p. E esse trajeto é que é o grande salto – você já está enxergando isso. Acho que ainda deve demorar um tempo para essa filosofia pegar – talvez isso seja para a sua geração. E fico feliz por você estar tendo esta visão 25 anos mais nova que eu. Bjo.

  2. P = NP, caramba, foi minha aula favorita da faculdade. Grafos e Teoria da Complexidade (mas na verdade a parte de Grafos q era que me interessava mais). Com relação ao parágrafo 4, a repetição do experimento gera uma média aproximada do resultado real. Acho que já conversamos um pouco disso. A teoria de algoritmos genéticos é baseada nesta premissa e junto com elementos evolutivos e uma pitada de mutações, sempre chega no resultado correto (nem que o custo disso seja o de força bruta hehehe). Mas Darwin estava certo. Muito legal seu post. Um pouco técnico pra um cara enferrujado como eu, mas pelo que entendi, a aplicação mais prática seria realmente identificar o comportamento futuro de um indivíduo.
    Só uma coisa… altera a configuração do Blogspot pra ele mostrar o post completo via RSS!? Valeu, beijos

  3. Lá vou eu falar do que mais gosto: daquilo q ñ entendo!…hehe
    Acho que a relação entre teoria e prática fica muito prejudicada e reduzida quando a teoria é vista apenas como uma caixa de ferramentas a serem utilizadas: um objeto externo à "realidade".
    Um olhar pragmático não precisa necessariamente ser imediatista, e a pergunta impaciente "o q eu faço com isso" pode indicar um sujeito mais voltado para a Circunstância (que é uma ocorrência de determinado problema) e incapaz de enxergar o Problema mesmo.
    A teoria tem um papel fundamental na delimitação e na compreensão dos Problemas…acho que ela serve mais para isso do que para resolvê-los. A solução é sempre um processo, no qual incide até mesmo o acaso, o imprevisto, a intuição…
    Um conceito que pode ampliar essa questão, é o de praxis, que indica a integração da teoria e da ação.

Comments are closed.