O Paradoxo do Pokémon Twitch

A última moda da internet é o Pokémon Twitch. Como essas modas evaporam tão rapidamente quanto surgem, vale a pena explicar do que se trata:

O twitch é um site para livestreaming de videogames. Você conecta seu videogame no site, e as pessoas do mundo todo podem te assistir enquanto você joga. Ele tem também uma janela de chat, então as pessoas podem comentar enquanto assistem.

Mas algum gênio aprimorou a idéia original. Ele ligou o twitch em um emulador de Game Boy, e configurou o emulador para pegar o texto do chat e interpretar como se fosse o joystick. Com isso, qualquer um que tenha uma conta lá pode controlar o personagem do jogo (no caso, a versão original de Pokémon). E melhor ainda, como todos estão controlando o mesmo jogo, então o que ele fez foi criar uma espécie de crowdgaming, onde a sabedoria das massas escolhe o melhor caminho do personagem.

Quer dizer, na teoria. Na prática, a internet será a internet. Para cada um que tenta jogar sério, tem um trollzinho que fica mandando o comando oposto. No pico de popularidade, ele chegou a ter mais de cem mil pessoas jogando ao mesmo tempo. Imagine metade disso sacaneando ao invés de jogando, e dá pra ter uma idéia da loucura que é o Pokémon Twitch (ou então leia o FAQ para entender tudo que já aconteceu até agora).

Quando eu fiquei sabendo do Pokémon Twitch, eu fiz o que qualquer pessoa normal faria: criei um modelo matemático do jogo. No meu modelo simplificado, o personagem só anda na vertical, um passo por iteração. O número de jogadores e o número de trolls é o mesmo, então a cada passo ele tem 50% de chance de andar uma unidade para cima ou para baixo. Assuma que ele começa da origem. Nesse modelo, eu faço duas perguntas:

1. Depois de n iterações, onde você espera que o personagem esteja?
2. Depois de n iterações, qual você espera que seja a distância do jogador à origem?

Eu sei, eu sei: "Ricbit, deixa de ser bobo! As duas perguntas são iguais! Suponha que a resposta da primeira pergunta é y. Então a resposta da segunda é y menos 0, ou seja, o mesmo valor y".

Paradoxalmente, isso está errado! A resposta das duas perguntas é diferente! Probabilidade é um tópico que escapa facilmente da nossa intuição, então vale a pena fazer as contas com cuidado para entender a solução.

O valor esperado da posição

Para a resposta da primeira pergunta, vamos calcular qual é o valor esperado da posição. Na iteração 0 ele ainda não executou nenhum movimento, então sabemos a posição deterministicamente: ele está na origem.

E na iteração n+1? Depende de onde ele estava na iteração n. Tem 50% de chance de ter subido, e 50% de ter descido:

Com isso podemos calcular o valor esperado de y(n+1) direto da lei da expectativa total:

Ou seja, o valor esperado em qualquer iteração é sempre zero, na média nós esperamos que ele fique andando em círculos e nunca fique muito longe da origem.

Entretanto, note que só porque o valor esperado é zero não quer dizer que ele vai sempre terminar na origem: a média é zero, mas a variância não é. Um exercício bastante curioso é calcular qual a probabilidade exata do personagem estar na origem após n iterações. Isso é fácil e dá pra resolver com combinatória de colégio. Imagine que você tem n caixinhas:


Cada uma dessas caixinhas você pode preencher com +1 ou -1; se a soma de todas elas for zero, então o personagem termina na origem. De quantas maneiras podemos fazer isso? Note que nós só precisamos escolher as posições dos +1:

+1

+1

+1

+1

Sabendo onde estão os +1, a posição dos -1 restantes fica unicamente determinada. Precisamos então descobrir de quantas maneiras podemos encaixar n/2 números +1 em n caixinhas. Mas isso é a definição do binomial:

Agora é só dividir pelo total. Como cada caixinha tem duas opções possíveis, +1 e -1, então o número total de caixinhas é 2^n. Portanto, a probabilidade dele terminar na origem é:

Essa fórmula tem um problema: embora ela seja exata, é muito ruim de calcular quando o n é grande (tente calcular para n=1000, o número de dígitos da sua calculadora vai acabar rapidinho). Podemos achar um assintótico usando a aproximação do coeficiente binomial central:

Mais fácil né? Agora podemos calcular facilmente que, para n=1000, a chance de terminar na origem é aproximadamente 2.5%.

Se você tem o olho bom, deve ter percebido uma pegadinha na derivação da fórmula acima. Ela só funciona quando n é par! De fato, quando n é ímpar, não tem como o número de +1 e -1 serem iguais, e portanto a chance dele terminar na origem é zero. Olha que curioso: quando o n é ímpar, ele nunca termina em zero, apesar do valor esperado ser zero!

O valor esperado da distância

Vamos agora à segunda pergunta, que é o valor esperado da distância. Por que afinal esse valor é diferente do anterior?

Para exemplificar, vamos supor que n=2. Em uma das amostras, digamos que os jogadores ganharam e ele andou 2 unidades para cima, então a distância para a origem é 2. Em outra amostra, suponha que os trolls ganharam, então ele andou 2 unidades para baixo. Qual a distância da origem? É 2 também! Distâncias são sempre positivas!

Em outras palavras, o valor esperado da distância é o valor esperado do módulo da posição! E quanto é esse valor? As contas aqui são um pouco mais complicadas, então vou precisar da caixa azul:

Dessa vez nós vamos ter que calcular o valor esperado pela definição:

Quando k=0 o somando vale zero também. Vamos então supor k positivo e usar a mesma idéia das caixinhas. A soma era zero quando a quantidade de +1 e de -1 era igual. Dessa vez, nós queremos que a soma seja k, então precisamos ter k números +1 a mais que o número de -1. Portanto, a chance dele terminar em um valor k positivo é:

Quando k é negativo, a fórmula é exatamente a mesma! Afinal, é só trocar todos os +1 por -1 e vice versa. Portanto, o valor esperado da distância é:

Essa fórmula é difícil de manipular, para deixar mais fácil vamos supor que n é par. Se n é par, podemos escrevê-lo como n=2m. Mas olha só, se n for par, então você nunca vai terminar numa distância k que seja ímpar. Se você tirar k ímpar de n par, o que sobra é ímpar, então não tem como ter soma zero. Portanto podemos supor k par, e fazer k=2q. Substituindo:

A somatória é uma soma hipergeométrica, então você pode resolvê-la com o algoritmo de Gosper, chegando assim na forma fechada. Mas se você não souber usar o algoritmo de Gosper, não tem problema, é só provar a identidade abaixo por indução finita:

Substituindo a fórmula temos:

Agora é só usar a aproximação do binomial central:

Chegamos então no resultado final, o valor esperado da distância, que é raiz de 2n sobre pi.

A matemática experimental

Probabilidade tem uma vantagem grande sobre outros ramos da matemática: é muito fácil conferir as contas. Basta escrever uma simulação computacional com uma quantidade razoável de amostras!

Eu escrevi um script em python (o código está no github), e os resultados para n=1000 e cem mil amostras foram os seguintes:

• Posição: calculado 0.00, medido 0.05
• Distância: calculado 25.23, medido 25.27
• Término na origem: calculado 2.52%, medido 2.53%

Ou seja, a matemática experimental concordou com a matemática teórica.

A lição que fica dessa brincadeira é tomar muito cuidado com suas intuições sobre probabilidade, porque ela tem uma tendência a nos enganar bem facilmente :)

Como Provar um Axioma

Eu sei o que você está pensando: "Tá maluco Ricbit? Não dá pra provar um axioma! Eles são proposições tão simples que sua verdade é auto-evidente, não necessitando de prova! Se eu pudesse prová-lo, então não seria um axioma, seria um teorema!"

No fundo, essa é a essência do segundo teorema da incompletude de Gödel: um sistema formal não pode provar sua auto-consistência. Mas tem uma pegadinha aqui. Embora um sistema não possa provar sua auto-consistência, nada impede que você use um sistema mais forte para provar outro sistema mais fraco. Para mostrar como isso pode ser feito, vamos usar como exemplo o mais antigo de todos os axiomas.

O primeiro axioma de Euclides

O primeiro sistema axiomático foi aquele publicado nos Elementos de Euclides: os cinco postulados que definem as regras da geometria. O axioma que abre a lista não poderia ser mais simples:

Axioma 1: "Entre dois pontos é sempre possível traçar uma reta".

Mas essa simplicidade é traiçoeira! Na verdade, essa afirmação só faz sentido se você souber de antemão o que é um ponto e o que é uma reta. O Euclides sabia desse problema, por isso, antes de apresentar seus cinco axiomas, ele começa o livro com uma série de 23 definições. Para nós, as definições importantes são as 1, 2 e 4:

Definição 1: "Um ponto é aquilo que não tem parte".

Isso faz sentido. O ponto é o elemento indivisível, o que não pode ser quebrado em pedaços, o átomo. Em linguagem moderna, o ponto é um elemento de dimensão 0.

Definição 2: "Uma linha é um comprimento sem largura".

Isso também faz sentido. A linha é uma coisa comprida e infinitamente fina. Hoje em dia, diríamos que a linha é um elemento de dimensão 1.

Definição 4: "Uma reta é uma linha que se põe igualmente com seus pontos".

E aqui, my friends, é onde a porca torce o rabo. O que raios o Euclides quis dizer com isso? Eu fiquei um tempão tentando interpretar essa frase e não tive sucesso. No desespero, tentei até achar o original em grego, mas mesmo no original a frase é ambígua.

Sem outra alternativa, o jeito foi apelar para alguém que entenda mais que eu. No caso, o grego Proclus, que viveu no século 5 AD, e publicou uma versão comentada dos Elementos. Segundo Proclus, Euclides queria dizer que "de todas as linhas, somente a linha reta ocupa uma distância igual àquela entre seus pontos. Pois a distância de dois pontos entre si é a mesma que o comprimento da linha reta que os tem como extremidades; e esse é o sentido de se pôr igualmente com os seus pontos".

Ou seja, pela interpretação de Proclus, a quarta definição é equivalente a dizer que, de todas as linhas que ligam dois pontos, a reta é a menor delas!

Estritamente falando, essa definição só joga a sujeira debaixo do tapete, porque agora você precisa definir o que é distância. Mas isso já é suficiente para nosso propósito! Nós temos um sistema que define o que é distância: o tensor métrico de Riemann! Se eu assumir que o cálculo sobre os números reais existe, então eu posso usá-los para demonstrar o primeiro axioma de Euclides (ou seja, vou usar um sistema formal mais forte para provar um mais fraco).

Embora o axioma seja simples, as contas para demonstrá-lo não são. Se você fica assustado facilmente com equações diferenciais parciais, pule a caixa azul:

Vamos começar com o tensor métrico de Riemann. Na geometria euclideana, ele é o próprio teorema de Pitágoras:

Nós podemos multiplicar e dividir por dx^2 (sim, eu sei), e depois tirar a raiz quadrada dos dois lados:

Vamos supor que a função final será y=f(x). Então dy/dx é a derivada de f(x). E nesse ponto podemos integrar dos dois lados:

Se a linha entre A e B é descrita pela função f(x), então seu comprimento será S. O nosso objetivo é achar a função f(x) que minimiza S.

Quem já estudou cálculo deve estar pensando "é só derivar e igualar a zero!". A intuição é essa mesmo, mas os detalhes são diferentes. Nós não queremos achar um ponto que minimiza uma função, queremos achar uma função que minimiza uma integral.

Esse tipo de problema é resolvido pelo Cálculo de Variações. A teoria em geral é bastante complicada, mas nesse caso em específico tem uma fórmula que resolve o problema sozinha, a equação de Euler-Lagrange. A sua forma é a seguinte: suponha que você tenha uma função L[x, f(x), f'(x)]. Então o extremo da integral abaixo...

.. é dado pela solução dessa equação diferencial:

No nosso caso, a função L[x, f(x), f'(x)] é dada por:

Agora eu vou fazer as contas em câmera lenta porque elas são levemente diferentes do cálculo normal que estamos acostumados. O primeiro termo da equação é zero, porque L é constante em relação a f(x). Confira: na expressão de L, aparece f'(x), mas não aparece f(x).

Para a segunda derivada parcial, é só aplicar a regra da cadeia. Esse passo tem uma pegadinha:

Peraí, ali na segunda linha não tinha que multiplicar pela derivada segunda de f? Teria, se você estivesse derivando em relação a x, mas você está derivando em relação a f'(x)! Podemos fazer a última derivada agora:

Agora é só plugar na equação original:

Opa, o denominador é sempre positivo, então dá pra jogar fora!

Tcharam! A menor linha que liga dois pontos realmente é uma reta! Mas ainda não acabou, falta provar que a reta é única. Isso vem direto das condições de contorno:

Pronto, C1 e C2 são unicamente definidos pelos pontos nas extremidades, então a reta que os une é única. QED.

 
Minha telepatia anda forte ultimamente, então eu ainda sei o que você está pensando: "Pra que isso Ricbit? Você pegou uma proposição da geometria que era intuitiva, e a transformou em um monte de contas horrendas!"

Sim, é verdade. Eu fiz isso de propósito, para ilustrar um ponto importante: pra que você quer se limitar ao que sua intuição alcança? Nós temos à disposição cinco milênios de matemática, eles nos permitem trabalhar com coisas muito além do que nossa intuição consegue visualizar!

Nessas contas da caixa azul nós usamos o tensor métrico para achar o que é uma reta no espaço euclideano. Mas o mesmo raciocínio pode ser usado para achar retas em qualquer tipo de métrica. E sabe quem mais anda em linha reta? A luz!

Mesmo quando o tensor métrico está muito além da minha intuição, como nas proximidades de um buraco negro (onde vale a métrica de Schwarzschild), eu ainda assim sei fazer as contas que me mostram como a luz se comporta por ali. Às vezes até a matemática feia tem sua utilidade :)

A Redação de Riemann

Dia desses a Giseli me pediu para escrever alguma coisa sobre o Riemann. Naturalmente eu topei, até porque eu e o Riemann temos uma anedota em comum! Georg Riemann nasceu em 1826, em uma linhagem de pastores luteranos: seu pai, avô e bisavô eram pastores. Desde cedo ele sempre ia muito bem na escola, a ponto do pai dele ter que contratar um professor particular, porque só a escola comum não era o suficiente para ele. Mas isso também não ajudou muito, em certo ponto o tutor disse que estava aprendendo com o Riemann mais do que estava ensinando para ele. A solução foi achar uma escola melhor.

Aos quatorze anos, o Riemann saiu de casa para ir morar com a avó, ficando assim muito mais perto do respeitável Gymnasium de Hannover, o melhor da região. E é aqui que as nossas histórias se interceptam, eu também saí de casa aos quatorze para ir morar com a avó, mas no meu caso foi para estudar na respeitável ETFSP (que hoje em dia chama IFSP).

Quando completou o ginásio, a idéia original do Riemann era estudar Teologia para ser pastor, como mandava a tradição familiar. Mas nesse meio tempo ele teve uma experiência transformadora: ele assistiu a uma palestra do Gauss, onde ele apresentava pela primeira vez o método dos mínimos quadrados. A palestra deve ter sido muito boa, já que, desse momento em diante, o Riemann decidiu que iria seguir a carreira de Matemática.

Depois de conseguir seu doutorado, o Riemann tentou uma posição de professor na mesma universidade do Gauss. Como teste de admissão, o Gauss pediu para que ele escrevesse uma redação. Mas teria que ser sobre um tema que ambos gostassem, então a proposta foi a seguinte: o Riemann iria sugerir três tópicos, e dos três o Gauss escolheria qual seria o tema da redação. Os temas que o Riemann escolheu foram:

• Séries de Fourier
• Sistemas de Equações Quadráticas
• Fundamentos da Geometria

O Gauss acabou escolhendo o terceiro tema, e essa escolha é bem clara quando você conhece o espírito da época. Para explicar por que o Gauss escolheu esse tema, temos que rebobinar até a Grécia antiga.

Os Elementos de Euclides

Pelo menos até metade do século 20, Elementos de Euclides era o segundo livro mais publicado no mundo, perdendo só para a Bíblia (mas hoje em dia ele deve ter perdido para o Harry Potter e o Crepúsculo).

  Um dos motivos de ser um livro tão publicado é que trata-se de um livro muito didático, começando de princípios bem simples, e construindo em cima deles teoremas cada vez mais complexos. Tem um motivo para o livro ser assim: Euclides era professor, e os Elementos são a apostila com notas de aula! Provavelmente poucos teoremas do livro são de autoria dele, o mérito do Euclides foi reunir todos os trabalhos da época e colocar em notação consistente. Infelizmente, os originais de onde o Euclides tirou os teoremas foram todos destruídos nos muitos incêndios da Grande Biblioteca de Alexandria.

Pois bem, quais são os princípios básicos usados por Euclides? O livro começa com cinco deles:

• Por dois pontos você sempre pode traçar uma reta.
• Um segmento de reta sempre pode ser estendido indefinidamente.
• Dado um centro e um raio, você sempre pode construir um círculo.
• Todos os ângulos retos são congruentes.
• Se você desenhar duas retas que intersectam uma terceira, de maneira que o ângulo interno em um dos lados seja menor que dois ângulos retos, então as duas linhas originais necessariamente se intersectam nesse lado, se você as estender o suficiente.

Você não precisa entender de geometria para ver que tem algo errado aqui. Os quatro primeiros princípios são curtinhos, mas o quinto é enorme. Por que isso acontece? O problema é que o Euclides não conseguiu provar esse fato usando só os princípios anteriores, então ele simplesmente assumiu que era verdade sem provar. Por dois milênios, um monte de matemáticos tentou consertar esse buraco nos Elementos, mas ninguém conseguia. Foi só no século 19 que tivemos algum progresso.

Lobachevsky e Bolyai

Como você tentaria provar a quinta proposição? A maneira mais natural é tentar um ataque por contradição: você assume o contrário do que quer provar, e tenta chegar numa contradição. Assumindo a negação da proposição, você conclui um monte de fatos que são intuitivamente absurdos. Por exemplo, que dado uma reta, existem infinitas retas paralelas a ela passando por um ponto dado, que o teorema de Pitágoras é falso, que a soma dos ângulos internos de um triângulo é menor que 180 graus.

Mas apesar de serem absurdos, nenhum desses fatos é uma contradição de verdade. Para a demonstração funcionar, você precisa de algum fato que contradiga os quatro princípios iniciais dos Elementos. Contradizer o que vem depois no livro não serve! Foi nesse ponto que, de maneira independente, o russo Lobachesvsky e o húngaro Bolyai tiveram um insight: e se na verdade a quinta proposição fosse independente das demais? Ou seja, tanto faz se você usa ela do jeito original ou a sua negação, o sistema continua consistente do mesmo jeito?

Isso é a base do que hoje chamamos de geometrias não-Euclideanas. Essa era uma idéia chocante para a época, de que podem existir geometrias que funcionam apesar de não seguirem todas as regras dos Elementos. O pai do Bolyai ficou tão orgulhoso com o resultado do filho que mandou uma carta pro Gauss avisando da descoberta. O Gauss respondeu "olha, eu não posso elogiar seu filho, porque eu tive a mesma idéia 30 anos atrás, e seria indelicado elogiar a mim mesmo."

A Curvatura de Gauss

Tecnicamente falando, era verdade. O Gauss realmente tinha pensado nisso, mas ele nunca publicou o resultado porque achou que era uma bobagem. Eu não tenho como saber o que se passava na cabeça dele, mas imagino que foi algo assim: "Essa geometria é perversa, se eu assumir que ela existe, então a soma dos ângulos internos do triângulo dá menos de 180 graus, e isso só seria verdade se o plano fosse curvo, o que é um absurdo. Por outro lado, eu posso usar isso para definir o que é curvatura de uma superfície! Eu defino então a curvatura intrínseca de uma superfície como sendo uma função de quanto a soma dos ângulos desvia de 180 graus."

Depois de definir o que é curvatura intrínseca, o Gauss provou uma proposição tão legal que ele chamou de Theorema Egregium (em português é Teorema Incrível, e se o Gauss chamou de incrível é porque a coisa é quente mesmo). O enunciado é assim:

"A curvatura intrínseca de uma superfície depende só das distâncias entre os pontos, e não de suas posições".

Isso parece... óbvio? Quer dizer, imagine que recorto um triângulo de papel reciclado como o abaixo:

Se eu mudar a posição dos pontos, por exemplo, fazendo uma translação, obviamente a soma dos ângulos do triângulo não muda:

Mas a sacada do Gauss é que você pode torcer o triângulo sem mudar a soma de seus ângulos! Torcer o triângulo sem esticar é a mesma coisa que transladar cada ponto para um lugar diferente.

Mas peraí, se você torceu o triângulo, então você mudou as distâncias entre os pontos! Por exemplo, nessa imagem, fica claro que o caminho entre os vértices indicados é menor que do seria se o triângulo não estivesse torcido!

Mas para o Gauss, o que importa é a distância que uma formiga faria se estivesse andando no seu triângulo. Formiga não voa, ela precisa andar pelo papel, e por isso a distância que ela percorre é a mesma.

Com isso, você consegue mostrar que a curvatura do plano é diferente da curvatura da esfera. Eu tentei colocar o meu triângulo numa bolinha roubada da gata Luvinha, e olhe o que acontece: se eu tento forçar um dos lados do triângulo a ficar na esfera, o outro vértice vai para fora.

E se eu tento forçar todos os vértices a ficarem na bola, o papel amassa. Claramente, a distância de formiga entre dois pontos na esfera é sempre menor ou igual à distância de formiga sobre o plano, não importando como eu tento encaixar o plano.

Mas a parte menos intuitiva é que eu posso colocar o triângulo sobre uma latinha de Schweppes sem amassar o papel! A lateral do cilindro tem curvatura igual à do plano, então os ângulos dos triângulos sobre o cilindro somam sempre 180 graus.

Isso tem uma conseqüência prática interessante. Como a curvatura intrínseca do cilindro é igual à do plano, eu posso colocar um rótulo de Coca Zero na mesa sem amassar.

Mas não dá para fazer isso com a superfície de um globo! Por isso, todo mapa-mundi necessariamente introduz algum tipo de distorção, como a projeção de Mercator, que distorce horrivelmente a Antártica e a Groenlândia:

A Redação de Riemann

Agora já temos como entender o que o Riemann escreveu na sua redação. O título era "Über die Hypothesen welche der Geometrie zu Grunde liegen" (Sobre as hipóteses que formam a base da geometria), e tem uma tradução online para quem quiser ler. Note que não é um paper, é uma redação mesmo! Tem só uma fórmula e o resto é praticamente só texto.

A idéia principal do Riemann é a seguinte: segundo o Lobachevsky e o Bolyai, existem geometrias não-Euclideanas onde o espaço é curvo. Já segundo o Gauss, a curvatura do espaço depende da distância entre os pontos. Então podemos usar a função que mede distâncias para definir a geometria usada.

Por exemplo, na geometria clássica de Euclides, a distância entre dois pontos é dada pelo teorema de Pitágoras, cuja versão diferencial é a abaixo:

Mas eu posso extrapolar essa fórmula, por exemplo, adicionando outros tipos de dependências:

Cada um dos g_ij pode ser um número qualquer, ou até uma função qualquer! Quando escrito em forma tensorial, essa equação acima define o tensor métrico de Riemann. E a partir dele podemos derivar todas as outras características da geometria, incluindo a curvatura intrínseca em cada ponto.

Quando o Gauss leu a redação, quase esboçou um meio sorriso! (Diz a lenda que essa foi a única vez que Gauss elogiou um aluno em público. Era marrento esse Gauss). O Riemann foi admitido como professor, e trabalhou em diversas áreas, incluindo teoria dos números, onde enunciou a lendária hipótese de Riemann, um problema que está em aberto até hoje (e paga um milhão de dólares para quem resolver).

Mas, para mim, a parte mais profética da redação do Riemann são os parágrafos finais. Eu vou traduzir esse trecho final:

"Supondo que os corpos existem independentemente da posição, então a curvatura é constante em todo ponto, e segue pelas medidas astronômicas que não pode ser diferente de zero, ou ao menos que seu inverso seja uma área tal que o alcance de nossos telescópios seja desprezível. Mas se essa independência dos corpos da posição não existe, então não podemos tirar conclusões das relações métricas entre distâncias grandes e infinitamente pequenas; nesse caso a curvatura em cada ponto pode ter um valor arbitrário em três dimensões, desde que a curvatura total de cada porção mensurável do espaço não seja muito diferente de zero."

É isso. Em 1854, o Riemann cantou a bola da Relatividade Geral. Só faltou o Einstein deduzir, sessenta anos depois, que a tal curvatura variável em cada ponto era uma função da massa, e daí segue naturalmente que a gravidade é uma deformação do espaço-tempo. Nada mal para o menino que saiu aos 14 anos de casa para estudar!